二叉排序演算法

⑴ 二叉排序樹定義

二叉排序樹（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;
}
}