二叉樹的定義
二叉樹是n（n>=0）個結點的有限集合，它或者是空樹（n=0），或者是由一個根結點及兩棵不相交的且分別稱為左，右子樹的二叉樹所組成，可見，二叉樹同樣具有遞回的性質，
需要注意的是，盡管二叉樹和樹有很多概念之間的聯系，但是他們是兩個不同的概念，樹和二叉樹之間最主要的區別是：二叉樹中的結點的子樹要區分左子樹和右子樹，即使在結點只有一棵子樹的情況下，也要分別出是左子樹和右子樹，另外，二叉樹結點的最大度為2，樹中無結點度數限制，如下圖所示，
二叉樹的性質
（1）二叉樹第i層（i>=1）上最多有2i-1個結點，此性質根據數學歸納法對層數i進行數學歸納即可證明，
（2）高度為k的二叉樹最多有2k-1個結點（k>=1），由性質1，每一層的結點數都取最大值2k-1即可，
（3）對于任何一棵二叉樹，若其終端結點數為n0，度為2的結點數為n2，則n0=n2+1，
（4）具有n個結點的完全二叉樹的深度為【log2n】+1，
若深度為k的二叉樹有2k-1個結點，則稱其為滿二叉樹，可以對滿二叉樹中的結點進行連續編號：約定編號從根結點起，自下而上，自左向右依次進行，深度為k，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱為完全二叉樹，滿二叉樹如圖a所示，高度為三的一個完全二叉樹如圖b所示，在一個高度為h的完全二叉樹中，除了第h層（最后一層）其余各層都是滿的，切h層結點必須從左至右放置，不能留空，圖c所示的二叉樹不是完全二叉樹，因為六號結點的左邊有空結點，
二叉樹的遍歷
二叉樹的遍歷是按某種策略訪問樹中的每個結點，切僅訪問一次的程序，由于二叉樹所具有的遞回性質，一棵非空的二叉樹是由根結點，左子樹，右子樹三部分構成的，因此若能遍歷這三部分，也就遍歷的整個二叉樹，按照先遍歷左子樹后遍歷右子樹的方式，可以得到二叉樹的先序，中序，后序遍歷三種遍歷方法，
1.先序遍歷
假設二叉樹如圖所示
先序遍歷的含義是先訪問根結點，再訪問左子樹，最后訪問右子樹，因此首先訪問根結點1，之后訪問左子樹，左子樹也同樣先訪問根結點2，在訪問2的左子樹，左子樹只有一個葉子4，所以左子樹訪問完成，之后訪問2的右子樹，右子樹只有一個葉子5，所以2的右子樹訪問完成，即1的左子樹訪問完成，之后訪問1的右子樹，同理先訪問根結點3，再訪問3的左子樹6，再訪問3的右子樹7，此時1的右子樹也訪問完成，此二叉樹的先序遍歷也完成了，得到的先序遍歷結果為1245367
訪問順序由圖所示
2.中序遍歷
假設也使用之前的樹圖，中序遍歷的含義是先訪問左子樹，再訪問根結點，最后訪問右子樹，因此首先訪問1的左子樹，1的左子樹根結點為2,2有左子樹，首先訪問2的左子樹，2的左子樹只有一個葉子4，即訪問4，再訪問根結點2，再訪問2的右子樹，2的右子樹只有一個葉子5，即訪問5，此時1的左子樹訪問完成，之后便訪問根結點1，再訪問1的右子樹，1的右子樹根結點為3,3的左子樹只有一個葉子6，所以訪問6,再訪問根3，再訪問3的右子樹，3的右子樹只有一個葉子7，即訪問7，所以訪問序列為4251637
訪問順序由圖所示
3.后序遍歷
假設也使用之前的樹圖，后序遍歷的含義是先訪問左子樹，再訪問右子樹，最后訪問根，因此首先訪問1的左子樹，1的左子樹根結點為2,2有左子樹，首先訪問2的左子樹，2的左子樹只有一個葉子4，即訪問4，再訪問2的右子樹，2的右子樹只有一個葉子5，即訪問5，再訪問根結點2，此時1的左子樹已經訪問完成，之后訪問1的右子樹，1的右子樹根結點為3,3的左子樹只有一個葉子6，所以訪問6，再訪問3的右子樹，3的右子樹只有一個葉子7，即訪問7，之后再訪問根結點3，最后訪問根結點1，由此訪問結束,得到的訪問序列為4526731，
訪問順序由圖所示
二叉樹遍歷演算法介紹
先序遍歷演算法
void Pre(Tree tree){
if(root!=NULL){
System.out.print(tree->data);
Pre(tree->lchild);
Pre(tree->rchild);
}
}
中序遍歷演算法
void Pre(Tree tree){
if(root!=NULL){
Pre(tree->lchild);
System.out.print(tree->data);
Pre(tree->rchild);
}
}
后序遍歷演算法
void Pre(Tree tree){
if(root!=NULL){
Pre(tree->lchild);
Pre(tree->rchild);
System.out.print(tree->data);
}
}
最優二叉樹
1.最優二叉樹
最優二叉樹又稱為哈夫曼樹，它是一類帶權路徑長度最短的樹，路徑是從樹中一個結點到另一個結點之間的通路，路徑上的分支數目稱為路徑長度，
樹的路徑長度是從樹根到每一個葉子之間的路徑長度和，結點的帶權路徑長度為從該結點到樹根之間的路徑長度與該結點權值的乘積，
樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和，記為：WPL=w1l1+w2l2+…+wk*lk，
其中，n為帶權葉子結點數目，wk為葉子結點的權值，lk為葉子結點到根路徑長度，
哈夫曼樹是指權值為w1，w2，w3，，，，wn的n個葉子結點的二叉樹中帶權路徑長度最小的二叉樹，
例如下圖，其中（WPL=35）是帶權路徑長度最小的二叉樹，
2.構造最優二叉樹
假設有一組二叉樹的結點資料為：1，2，5，9，12，15構造程序如圖所示
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60561.html
標籤：其他