二叉排序算法

⑴ 二叉排序树定义

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

定义一：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

定义二：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树。

定义三：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行进行选择。

插入删除：
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

⑵ 急急急，求将两颗二叉排序树合并成一棵二叉排序树的算法，谢谢好心人！

提供个思路：遍历第二棵树，把其中每个元素依次插入到第一个二叉树，从而达到合并的目的。
二叉排序树的插入算法如下：
//在二叉排序树中插入关键字key
void InsertBST(t, key)
{
if(t==NULL)
{
t=new BiTree;
t->lchild=t->rchild=NULL;
t->data=key;
return;
}
if(key<t->data ) InsertBST(t->lchild,key);
else InsertBST (t->rchild, key );
}

⑶ 二叉排序树怎么构造

假设二叉排序树T为空，则创建一个keyword为k的结点。将其作为根结点。

否则将k和根结点的keyword进行比较，假设相等则返回，假设k小于根结点的keyword则尘拿插入根结点的左子树中，否则插入根结点的右升兄昌子树中。

int InsertBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k<p->key)
return InsertBST(p->lchild, k);
else
return InsertBST(p->rchild, k);
}
二叉排序树的生成算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InsertBST(bt, A[i]);
i++;
}
return bt;
}

(3)二叉排序算法扩展阅读：

在一般情况下，设 P（n，i）为它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉吵扒分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。平均查找长度= 每个结点的深度的总和 / 总结点数。

⑷ 二叉排序树的应用

树的应用：二叉排序树
排序是一种十分重要的运算。所谓排序就是把一堆杂乱无章的元素按照某种次序排列起来，形成一个线性有序的序列。二叉排序树是利用二叉树的结构特点来实现对元素排序空绝的。

一、二叉排序树的定义

二叉排序树或者是空树，或者是具有如下性质的二叉树：
1、左子树上所有结点的数据值均小于根结点的数据值；
2、右子树上所有结点的数据值均大于或等于根结点的数据值；
3、左子树、右子树本身又各是一棵二叉排序树。

由此可见，二叉排序树是一种特殊结构的二叉树。（18（10（3，15（12，15）），21（20，21（，37））））就是一棵二叉排序树。

思考题1：试将上述括号表示法表示的二叉排序树用图形表示法表示出来。图
思考题2：试用中序遍历二叉树的方法写出遍历二叉排序树的结果，并思考二叉排序树究竟有什么作用？。

二、二叉排序树的构造

二叉排序树的构造过程实质上就是排序的过程，它是二叉排序树作媒介，将一个任意的数据序列变成一个有序序列。二叉排序树的构造一般是采用陆续插入结点的办法逐步构成的。具体构造的思路是：
1、以待排序的数据的第一个数据构成根结点；
2、对以后的各个数据，逐个插入结点，而且规定：在插入过程的仿亏缓每一步，原有树结点位置不再变动，只是将新数据的结点作为一个叶子结点插入到合适的位置，使树中任何结点的数据与其左、右子树结点数据之间的关系仍然符合对二叉排序树的要求。

思考题3：试根据上述构造二叉排序树的思路，画出待排序数据（50，54，71，23，48，55，79，32，21）的二叉排序树图。

总结：构造二叉排序树的算法思想如下：设A={a1,a2,...,an}为一组元素的集合，
1、令a1为二叉排序树的根；
2、在保持二叉排序树性质的前提下，依次把a2,a3,...,an插入到该树中。

二叉排序树的生成算法：

Procere createbst(Var t:pointer);
{构造一棵以t指向根结点的二叉排序树，插入数据以‘#’结束}
Begin
t:=nil; {初始化}
read(x); {输入元素值x}
while (x<>'#') do
begin
new(s);s^.Lc:=nil;s^.Rc:=nil;
s^.data:=x;
insertnode(s,t);
read(x)
end;
end.

其中，插入一个结点的算法insertnode(s，t)如下：

Procere insertnode(s:pointer;Var t:pointer);
{s指向待插入结点，t是bst的根}
Begin
if t=nil then t:=s
else if s^.data < t^.data then insertnode(s,t^.Lc)
else insertnode(s,t^.Rc)
end.

注备模意该算法为尾递归算法。不用栈即可转为非递归。

思考题4：试用Pascal语言编写一个程序，实现对未排序数据的输入、排序和输出排序结果。（要求应用二叉排序树）标准程序 参考程序（黄硕）
思考题5：假设已经生成了一棵二叉树，试按照二叉排序树的思想设计一个算法，判断这棵二叉树是否为二叉排序树。

⑸ 结合二叉树的快速排序算法分析

对 3，9，1，6，5，4，8，2，10，7 进行从小到和悄迟大的快速排序

对于第一次遍历，如下图所示：

对应的二叉树结果是：

那么经过后几次遍历比较可以得到如下二叉树：

这运灶时我们可以计算一下我们的快速排序算法进行了多少次比较:

，即每个节点到根结点的距离之和。

由上例可知，快排可视为一个二叉树构建的过程，那么这个二叉树构建的速度就决定了我们快排的效率。可以确定的是，对于同样的数据元素在不同的原始排列条件下，构建的二叉树越矮，则排序效率越高。

通过这一理论，我们可以更具体的分析其不同情况下的时间复杂度：

完全二叉树满足如下公式：

对于深度为h的完全二叉树，若为满二叉树，比较次数为：

这里的叶子数量m与深度h的关系：

那么叶子到根的距离d为：

即， ，

由于 为整数，即可认为 ，

而对于完全二叉树来说，叶子数 ，与内点（带有叶子节点的顶点）数 的关系为 ，则顶点数

那么由上述公式可得：

即， ，时间复杂度为： 。

那么若节点数为n，则：

，即时间复杂度为： 。

由于分割标准的选取概率完全相同，那么可以得到平均比较次数为：

由于这里的 ，以及

由 ，以及 ，得：

令 ，得：

令 ，得：

令 ，得：

整理得：

由 ，故

则：唤李

即，

综合来看，快排的时间复杂度最理想状态与最糟糕状态分别为 、 ，但是对于一般随机情况而言时间复杂度仍为 。

⑹ 二叉排序树的插入算法

首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点。 //在二叉排序树中插入查找关键字keyvoidInsertBST(t，key){if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}//n个数据在数组d中，tree为二叉排序树根voidCreateBiTree(tree,d[],n){tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}最小值二叉树c例程： #include<stdio.h>#include<malloc.h>structpriorityqueue{intcapacity;intsize;structpriorityqueue*elements;}*tryit;structpriorityqueue*initialize(intmaxelements){structpriorityqueue*h;h=malloc(sizeof(structpriorityqueue));h->elements=malloc(sizeof(int)*(maxelements+1));h->capacity=maxelements;h->size=0;h->elements[0]=-23767;returnh;}voidinsert(intx,structpriorityqueue*h){inti;for(i=++h->size;h->elements[i/2]>x;i/=2)h->elements[i]=h->elements[i/2];h->elements[i]=x;}intdeletemin(structpriorityqueue*h){inti,child;intminelement,lastelement;minelement=h->elements[1];lastelement=h->elements[h->size--];for(i=1;i*2<=h->size;i=child){child=i*2;if(child!=h->size&&h->elements[child+1]<h->elements[child])child++;if(lastelement>h->elements[child])h->elements[i]=h->elements[child];elsebreak;}h->elements[i]=lastelement;returnminelement;}main(){tryit=initialize(10);insert(4,tryit);insert(5,tryit);insert(10,tryit);insert(3,tryit);printf(%d ,deletemin(tryit));printf(%d deletemin(tryit));printf(%d ,deletemin(tryit));printf(%d ,deletemin(tryit));getchar();}

⑺ 数据结构课程设计（C版语言）二叉排序树算法

下面的程序包含了树二叉树的所有操作
在二叉树的应用中有二叉排序树。
都是C语言，只不过用了C++的cin(输入)和cout（输出）,因为这两个不需要格式控制符。
//建一个工程：包含头文件：bittree.h Cpp文件：bittree.cpp main函数:main.cpp
编译运行就可以了。

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//头文件 bittree.h
#ifndef _DEF
#define _DEF
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
using namespace std;
#define TURE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define INFEASIBLE -1//不可实行的
#define OVERFLOW -2
typedef int stas;
typedef char Telemtype;
//typedef int Telemtype2;//为了二叉排序树的创建
typedef char ElemType;
#define STACK_SIZE 100;
#define STACKINCREMENT 10;

//二叉树
typedef struct bitnode{
Telemtype data;
struct bitnode *lchild,*rchild;
}BitNode,*BitTree;
extern stas CreateBitTree(BitTree &T);
extern stas PreOrderTraverse(BitTree T);
extern stas InOrderTraverse(BitTree T);
extern stas PostOrderTraverse(BitTree T);

typedef BitNode selemtypechar;
typedef BitTree selemtypechar2;

// 栈
typedef struct SqStack{
selemtypechar2 *base;
selemtypechar2 *top;
int stacksize;
}sqstack;
extern stas initstackC(sqstack &S);
extern stas gettopC(sqstack S,selemtypechar2 &e);
extern stas pushC(sqstack &S,selemtypechar2 e);
extern stas popC(sqstack &S,selemtypechar2 &e);
extern stas destroyC(sqstack &S);//销毁
extern stas clearC(sqstack &S);//置空
extern stas stackempty(sqstack S);

//栈实现二叉树的输出
extern stas PreOrderTraverse2(BitTree T);
extern stas InOrderTraverse2(BitTree T);
extern stas PostOrderTraverse2(BitTree T);
//二叉树的应用
extern stas Depth(BitTree T);
extern stas Single(BitTree T);
extern stas Double(BitTree T);
extern stas CountLeaf(BitTree T);
extern void Change_Left_Right(BitTree T);
//二叉层次遍历用到队列
typedef BitTree Qelemtype;
typedef struct QNode{
Qelemtype data;
struct QNode *next;
}qnode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
extern stas InitQueue(LinkQueue &Q);
extern stas DestroyQueue(LinkQueue &Q);
extern stas EnterQueue(LinkQueue &Q,Qelemtype e);
extern stas DeQueue(LinkQueue &Q,Qelemtype &e);
//二叉层次遍历
extern stas LevelOrder(BitTree T);
//二叉排序树
extern void insert(BitTree &T,ElemType x);
extern void CreateBiTree2(BitTree &root);

#endif
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//cpp文件 bittree.cpp
#include "bittree.h"
#include <stdlib.h>

stas initstackC (sqstack &s)
{
s.base=(selemtypechar2 *)malloc(100*sizeof(selemtypechar));//用STACKINCREMENT会报错？？？
if (!s.base) exit(OVERFLOW);
s.top=s.base;
s.stacksize=100;
return OK;
}
stas gettopC(sqstack s,selemtypechar2 &e)
{
if(s.base==s.top) return ERROR;
e=*(s.top-1);
return OK;
}
stas pushC(sqstack &s,selemtypechar2 e)
{
if ((s.top-s.base)>=s.stacksize)
{
s.base=(selemtypechar2 *)realloc(s.base,((s.stacksize+10)*(sizeof(selemtypechar))));
if(!s.base) exit(OVERFLOW);
s.top=s.base+s.stacksize;
s.stacksize+=10;
}
*(s.top++)=e;
//s.top++;
return OK;
}
stas popC(sqstack &s,selemtypechar2 &e)
{
if(s.top==s.base) return ERROR;
--s.top;
e=*(s.top);
return OK;
}
stas destroyC(sqstack &s)
{
free(s.base); s.base=NULL;s.top=NULL;
return OK;
}
stas clearC(sqstack &s)
{
s.top=s.base;
return OK;
}
stas stackempty(sqstack s)
{
if(s.top!=s.base) return ERROR;
else
return OK;
}

//二叉树
stas CreateBitTree(BitTree &T)//创建
{
Telemtype ch;
cin>>ch;
if(ch=='#') T=NULL;
else{
T=(BitTree)malloc(sizeof(BitNode));
if (!T) exit (OVERFLOW);
T->data=ch;
CreateBitTree(T->lchild);
CreateBitTree(T->rchild);
}
return OK;
}
stas PreOrderTraverse(BitTree T)//先序访问
{
if(!T) return ERROR;
else if (T)
{
cout<<T->data<<" ";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
stas InOrderTraverse(BitTree T)//中序
{
if(!T) return ERROR;
else if (T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<" ";
InOrderTraverse(T->rchild);
}
return OK;
}
stas PostOrderTraverse(BitTree T)//后序
{
if(!T) return ERROR;
else if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<" ";
}
return OK;
}

//栈实现二叉树的访问
stas PreOrderTraverse2(BitTree T)//先序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
//pushC(s,p);
while (p||!stackempty(s))
{
//popC(s,p);
if (p)
{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p1=p;
p=p->lchild;
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);

}
else {
popC(s,p);
popC(s,p);
p=p->rchild;
if (p==NULL)
{
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
p=p->rchild;
}
}
else{
pushC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->lchild;//左空不压栈
if (p==NULL)
{
popC(s,p);
p=p->rchild;
}
else
pushC(s,p);
}
}
}
destroyC(s);
return OK;
}
stas InOrderTraverse2(BitTree T)//中序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
}
else {
popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
p=p->rchild;
}
}
destroyC(s);
return OK;
}

stas PostOrderTraverse2(BitTree T)//后序
{
sqstack s;
BitTree p;
initstackC(s);
p=T;
while (p||!stackempty(s))
{
if (p)
{
pushC(s,p);
p=p->lchild;
if (p==NULL)
{
popC(s,p);
//p=p->rchild;
if (p->rchild==NULL)
{
if(!p->data)return ERROR;
cout<<p->data<<" ";
//p=p->rchild;
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);//???右结点重复压栈？？？
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
else
{
p=p->rchild;
}
}
else
continue ;
}
else
{
//popC(s,p);
if(!p->data)return ERROR;
cout<<p->data<<" ";
popC(s,p);
if (p==NULL)
{
return OK;
}
else
{
//pushC(s,p);
//p1=p;
p=p->rchild;
//p->rchild=NULL;
}
}
}
destroyC(s);
return OK;
}
//二叉树的应用

//二叉树的深度
stas Depth(BitTree T)
{
int depthval,depthLeft,depthRight;
if (!T) depthval=0;
else{
depthLeft=Depth(T->lchild);
depthRight=Depth(T->rchild);
depthval=1+(depthLeft>depthRight?depthLeft:depthRight);
}
return depthval;
}
//二叉树的单分支结点数
stas Single(BitTree T)
{
if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Single(T->rchild)+1;//只有左单分支
if (T->lchild && !T->rchild) return Single(T->lchild)+1;//只有右单分支
if(T->lchild && T->rchild) return Single(T->lchild)+Single(T->rchild);//双分支结点
}
}
//二叉树的多分支结点数
stas Double(BitTree T)
{

if (T==NULL) return 0; //空树
else if (T->lchild==NULL && T->rchild==NULL) return 0; //叶子结点
else{
if (!T->lchild && T->rchild) return Double(T->rchild);//只有左单分支
if (T->lchild && !T->rchild) return Double(T->lchild);//只有右单分支
if(T->lchild && T->rchild) return Double(T->lchild)+Double(T->rchild)+1;//双分支结点
}
}
//叶子结点
stas CountLeaf(BitTree T)
{
int num,num1,num2;
if(T==NULL) num=0;
else if(T->lchild==NULL&&T->rchild==NULL)
num=1;
else
{
num1=CountLeaf(T->lchild);
num2=CountLeaf(T->rchild);
num=num1+num2;
}
return num;
}
//交换左右子树
void Change_Left_Right(BitTree T)
{
BitTree Temp;
if (T)
{
Change_Left_Right(T->lchild);
Change_Left_Right(T->rchild);
Temp=T->lchild;
T->lchild=T->rchild;
T->rchild=Temp;
}
}
//二叉层次遍历用到队列
stas InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(100*sizeof(qnode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
stas DestroyQueue(LinkQueue &Q)
{
while (Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}

stas EnterQueue(LinkQueue &Q,Qelemtype e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(qnode));
if(!p) return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
stas DeQueue(LinkQueue &Q,Qelemtype &e)
{ QueuePtr p;
if(Q.front==Q.rear) return ERROR;
p=Q.front->next;e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
}
//二叉层次遍历
stas LevelOrder(BitTree T)
{
LinkQueue Q;
BitTree B;
InitQueue(Q);
if (T!=NULL)
{
EnterQueue(Q,T);
while (!(Q.front==Q.rear))
{
DeQueue(Q,B);
cout<<B->data<<" ";
if(B->lchild!=NULL) EnterQueue(Q,B->lchild);
if(B->rchild!=NULL) EnterQueue(Q,B->rchild);
}
}
return OK;
}
//二叉排序树
void insert(BitTree &T,ElemType x)
{
if (T==NULL)
{
T=(BitTree)malloc(sizeof(BitNode));
T->data=x;
T->lchild=T->rchild=NULL;
}
else
{
if(x<T->data)insert(T->lchild,x);
if(x>=T->data)insert(T->rchild,x);
}
}
void CreateBiTree2(BitTree &root)
{
ElemType x;
root=NULL;
cout<<"二叉排序树的创建<以'#'结束!!!>"<<endl;
cout<<"<请输入字母，没写整型!!!>"<<endl;
cin>>x;
while (x!='#')
{
insert(root,x);
cin>>x;
}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//主函数 main.cpp
#include "bittree.h"
void main()
{
system("cls");
system("color f0");
BitTree T;
Create:
cout<<'\t'<<'\t'<<"先序创建二叉树<以'#'表示左右孩子为空!!!>："<<endl;
CreateBitTree(T);
BitTree T1(T);
select:
cout<<'\t'<<'\t'<<"----------------MAIN-MENU----------------"<<endl;
cout<<'\t'<<'\t'<<"&1、先序输出 2、中序输出 3、后序输出 &"<<endl;
cout<<'\t'<<'\t'<<"&4、栈实现输出 5、重新创建二叉树 0、退出&"<<endl;
cout<<'\t'<<'\t'<<"------------6、二叉树的应用-------------"<<endl;
char sel;
getchar();
cin>>sel;
switch (sel)//总
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T);
cout<<endl<<"---------------------------------"<<endl;
goto select;
case '4':
stackcout:
cout<<endl<<'\t'<<" -------------------SUB-MENU1---------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 4、返回 &"<<endl;
cout<<'\t'<<" ------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//栈关于树的输出
{
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse2(T1);//p->lchild==null,时 T 的值被修改！！！！！！！！
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse2(T);
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T1);//栈实现未写完
cout<<endl<<"---------------------------------"<<endl;
goto stackcout;
case '4':goto select;
default:cout<<"选择错误!!!"<<endl;
goto stackcout;
}
case '5':
goto Create;
case '6':
{
SUB_MENU2:
cout<<'\t'<<'\t'<<"-------------------------SUB-MENU2---------------------"<<endl;
cout<<'\t'<<'\t'<<"&1、二叉树的深度 2、二叉树的单分支结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&3、二叉树的多分支结点数 4、二叉树的叶子结点数 &"<<endl;
cout<<'\t'<<'\t'<<"&5、二叉层次遍历 6、二叉排序树 7、交换左右子树 &"<<endl;
cout<<'\t'<<'\t'<<"&------------------8、输出 0、返回--------------------&"<<endl;
cin>>sel;
switch (sel)//二叉树的应用
{
case '0':
goto select;
case '1':
{
int deepth=0;
deepth=Depth(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"树的深度为："<<deepth<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '2':
{
int cou_sig;
cou_sig=Single(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的单分支结点为数："<<cou_sig<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '3':
{
int cou_dou;
cou_dou=Double(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的双分支结点数为："<<cou_dou<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '4':
{
int cou_leaf;
cou_leaf=CountLeaf(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"此树的叶子结点数为："<<cou_leaf<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '5':
{
cout<<"二叉层次遍历的结果为："<<endl;
cout<<endl<<"---------------------------------"<<endl;
LevelOrder(T);
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '6':
{
BitTree T3;
CreateBiTree2(T3);
SUB3:
cout<<'\t'<<"-------------------------SUB-MENU2-------------------"<<endl;
cout<<'\t'<<" &1、先序输出 2、中序输出 3、后序输出 0、返回 &"<<endl;
cout<<'\t'<<"-----------------------------------------------------"<<endl;
cin>>sel;
switch (sel)//二叉树的层次遍历
{
case '0':
break;
case '1':cout<<endl<<"---------------------------------"<<endl;
PreOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '2':cout<<endl<<"---------------------------------"<<endl;
InOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
case '3':cout<<endl<<"---------------------------------"<<endl;
PostOrderTraverse(T3);
cout<<endl<<"---------------------------------"<<endl;
goto SUB3;
default:
cout<<"选择错误!!!"<<endl;
goto SUB3;
}
}
goto SUB_MENU2;
case '7':
{
Change_Left_Right(T);
cout<<endl<<"---------------------------------"<<endl;
cout<<"交换完成，请选择8输出查看!!!"<<endl;
cout<<endl<<"---------------------------------"<<endl;
}
goto SUB_MENU2;
case '8':
goto select;
default:
cout<<"选择错误!!!"<<endl;
goto SUB_MENU2;
}
}
break;
default :
cout<<endl<<"选择错误!!!"<<endl;
goto select;
}
}