數(shù)據(jù)結(jié)構(gòu)第11講 二叉樹及其創(chuàng)建
二叉樹（Binary Tree）是n（n≥0）個結(jié)點所構(gòu)成的集合片迅，它或為空樹（n=?0）；或為非空樹渣窜，對于非空樹T：
（1）有且僅有一個稱之為根的結(jié)點铺根；
（2）除根結(jié)點以外的其余結(jié)點分為兩個互不相交的子集T1和T2宪躯，分別稱為T的左子樹和右子樹乔宿，且T1和T2本身又都是二叉樹。
也就是說访雪，二叉樹最多有兩個"叉"详瑞，即最多有兩個子樹掂林。如圖1所示：
二叉樹一般采用鏈?zhǔn)酱鎯Ψ绞剑好總€結(jié)點包含兩個指針域，指向兩個孩子結(jié)點坝橡，還包含一個數(shù)據(jù)域泻帮，存儲結(jié)點信息。如圖2所示计寇。
結(jié)點結(jié)構(gòu)體的定義：
那么圖1中的二叉樹就可以存儲為二叉鏈表的形式锣杂，如圖3所示：
如何創(chuàng)建一棵二叉樹呢？
我們從二叉樹的定義就可以看出番宁，它是遞歸的方式定義的（除了根之外元莫，左/右子樹也是一棵二叉樹），因此也可以用遞歸程序來創(chuàng)建二叉樹蝶押。
（1）輸入結(jié)點信息踱蠢，創(chuàng)建一個結(jié)點T；
（2）詢問是否創(chuàng)建T的左子樹棋电，如果是茎截，則創(chuàng)建其左子樹，否則其左子樹為NULL赶盔；
（3）詢問是否創(chuàng)建T的右子樹企锌，如果是，則創(chuàng)建其右子樹于未，否則其右子樹為NULL霎俩。
下面展示圖1二叉樹的創(chuàng)建過程：
請輸入結(jié)點信息:
A
是否添加A的左孩子? (Y/N)
Y
請輸入結(jié)點信息:
B
是否添加B的左孩子? (Y/N)
Y
請輸入結(jié)點信息:
D
是否添加D的左孩子? (Y/N)
N
是否添加D的右孩子? (Y/N)
N
是否添加B的右孩子? (Y/N)
Y
請輸入結(jié)點信息:
E
是否添加E的左孩子? (Y/N)
N
是否添加E的右孩子? (Y/N)
N
是否添加A的右孩子? (Y/N)
Y
請輸入結(jié)點信息:
C
是否添加C的左孩子? (Y/N)
Y
請輸入結(jié)點信息:
F
是否添加F的左孩子? (Y/N)
N
是否添加F的右孩子? (Y/N)
Y
請輸入結(jié)點信息:
G
輸入后F的左孩子為空，右孩子創(chuàng)建了一個結(jié)點G如圖12所示沉眶。
是否添加G的左孩子? (Y/N)
N
是否添加G的右孩子? (Y/N)
N
輸入后G左右孩子均為空如圖13所示打却。
是否添加C的右孩子? (Y/N)
N
輸入后G左右孩子均為空如圖14所示。
#include<iostream>
using namespace std;
typedef struct Bnode/*定義二叉樹存儲結(jié)構(gòu)*/
{ char data;
? ?struct Bnode*lchild,*rchild;
}Bnode,*Btree;
void createtree(Btree &T)/*創(chuàng)建二叉樹函數(shù)*/
{
? ? char check;/*判斷是否創(chuàng)建左右孩子*/
? ? T=new Bnode;
? ? cout<<"請輸入結(jié)點信息:"<<endl;
????cin>>T->data;
????cout<<"是否添加"<data<<"的左孩子? (Y/N)"<<endl;
????cin>>check;
????if(check=='Y')
????????createtree(T->lchild);
????else
????????T->lchild=NULL;
????cout<<"是否添加"<data<<"的右孩子? (Y/N)"<<endl;
????cin>>check;
????if(check=='Y')
????????createtree(T->rchild);
????else
????????T->rchild=NULL;
????return;
}
int main()
{
????Btree mytree;
????createtree(mytree);/*創(chuàng)建二叉樹*/
????return 0;
}
本文來自本人博客：http://blog.csdn.net/rainchxy
