定義：是一種樹型結(jié)構(gòu)剧辐，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)至多只有兩顆子樹道媚，并且二叉樹的子樹有左右之分军浆，并且其次序不能任意顛倒
二叉樹的性質(zhì)：
1.二叉樹的第i層上至多有2 i-1次方個(gè)結(jié)點(diǎn)
2.深度為k的二叉樹至多有2 k次方-1個(gè)結(jié)點(diǎn)
3.對(duì)于任何一顆二叉樹T夫植，如果其終端結(jié)點(diǎn)數(shù)為n0泊业，度為2的結(jié)點(diǎn)數(shù)為n2（度：結(jié)點(diǎn)擁有的子樹數(shù)）且叁，那么n0 = n2+1
4.有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為long 2 n + 1都哭；
滿二叉樹：
一棵深度為k且有2的k次方-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹
完全二叉樹：
一棵深度為k且小于2的k次方-1個(gè)結(jié)點(diǎn)的二叉樹，但是結(jié)點(diǎn)按順序來(lái)的二叉樹被稱為安全二叉樹
上圖a為滿二叉樹，b為完全二叉樹(滿二叉樹自上而下欺矫，自左向右進(jìn)行編號(hào)纱新，完全二叉樹是按照編號(hào)進(jìn)行排列)
二叉樹的存儲(chǔ)結(jié)構(gòu)：
typedef struct BiTNode{
? ? int data;
? ? struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;
二叉樹的遍歷：
二叉樹遍歷分為三種：前序、中序穆趴、后序脸爱，其中序遍歷最為重要。為啥叫這個(gè)名字未妹？是根據(jù)根節(jié)點(diǎn)的順序命名的阅羹。
前序順序是ABC（根節(jié)點(diǎn)排最先，然后同級(jí)先左后右）教寂；中序順序是BAC(先左后根最后右）捏鱼；后序順序是BCA（先左后右最后根）。
BiTNode* createBinaryTree(){ //創(chuàng)建二叉樹酪耕，按照根節(jié)點(diǎn)->左子樹->右子樹的順序創(chuàng)建節(jié)點(diǎn)
? ? BiTNode*p;
? ? int ch;
? ? std::cin>>ch;
? ? if(ch == 0)? ? //如果到了葉子節(jié)點(diǎn)导梆，接下來(lái)的左、右子樹分別賦值為0 {
? ? ? ? p =NULL;
? ? }
? ? else {
? ? ? ? p = (BiTNode*)malloc(sizeof(BiTNode));
? ? ? ? p->data= ch;
? ? ? ? p->lchild? =createBinaryTree();? //遞歸創(chuàng)建左子樹
? ? ? ? p->rchild=createBinaryTree();? //遞歸創(chuàng)建右子樹
? ? }
? ? return p;
}
int main(int argc,const char* argv[]) {
? ? std::cout<<"hello world"<<"\n";
? ? BiTNode*root =NULL;
? ? root =createBinaryTree(); //輸入6210043000800 創(chuàng)建效果如下圖
? ? printf("二叉樹建立成功");
? ? return 0;
}
