一平酿、樹
1断凶、 樹的定義：
樹(tree)是n(n>0)個節(jié)點的有限集，在任意一棵樹中报腔，(1)有且僅有一個特定的稱為根(root)的節(jié)點株搔，(2)當n>1時，其余節(jié)點可分為m(m>0)個互不相交的有限集纯蛾，而每個集合本身又是一棵樹纤房，稱為根的子樹(subtree)。
從上面樹的定義中可以看到翻诉，這是一個遞歸的定義炮姨，即樹的定義中又用到了樹的概念捌刮。
2、 樹結構中的基本術語：
樹的結點包含一個數(shù)據(jù)元素及若干只指向其子樹的分支剑令。
結點擁有的子樹數(shù)稱為結點的度(degree)糊啡。
如圖6.1(b)中，A的度為3吁津，C的度為1棚蓄，F(xiàn)的度為0。度為0的結點稱為葉子(leaf)或終端結點碍脏。如圖6.1(b)中梭依，結點K, L, F, G, M, I, J度都為0，都是葉子典尾。
度不為0的結點為非終端結點或分支結點役拴，除根結點之外，分支結點也稱內部結點钾埂。
樹的度是數(shù)內各結點的度的最大值河闰，如圖6.1(b)中，樹的度為3褥紫。
結點的子樹的根稱為該結點的孩子(Child)姜性，該結點稱為孩子的雙親(parent)，如圖6.1(b)中髓考，D為A的孩子部念，A是D的雙親，同一個雙親的孩子之間稱為兄弟(sibling)氨菇，如H, I, J互為兄弟儡炼。
結點的層次(level)從跟開始定義，根為第一次查蓉，根的孩子為第二層乌询，雙親在同一層的結點互為堂兄弟，如圖6.1(b)中豌研，結點G, E, F, H, I, J互為堂兄弟楣责。
樹種結點的最大層次為樹的深度(depth)或高度，如圖6.1(b)中聂沙，樹的深度為4。
如果樹中結點的各子樹是有次序的不能互換的初嘹，此樹為有序樹及汉，否則稱為無序樹。
森林(forest)是m(m≥0)棵互不相交的樹的集合屯烦。
二坷随、二叉樹
1房铭、二叉樹的定義：
二叉樹(binary tree)的特點：每個結點至多只有2棵子樹，且子樹有左右之分温眉，次序不能顛倒缸匪。
3、 二叉樹的性質：
(1) 在二叉樹的第i層上至多有2i-1個結點(i≥1)
(2) 深度為k的二叉樹至多有2k-1個結點(k≥1)
(3) 對任意一棵二叉樹T类溢，如果其終端結點數(shù)為n0凌蔬，度為2的結點數(shù)為n2，則n0=n2+1
4闯冷、 完全二叉樹和滿二叉樹：
這是兩種特殊形態(tài)的二叉樹砂心。
一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹，每一層上的結點數(shù)都是最大蛇耀。
對滿二叉樹的結點進行連續(xù)編號辩诞，當二叉樹的每個結點都與相同深度的滿二叉樹中編號從1~n的結點一一對應時，此二叉樹稱為完全二叉樹纺涤。
非完全二叉樹：
5译暂、 二叉樹的存儲結構：
(1) 順序存儲結構：
使用數(shù)組存儲，如上面的完全二叉樹撩炊，可以使用數(shù)組bt[12]外永，將編號為i的結點的數(shù)據(jù)元素存放在bt[i]中。
根據(jù)完全二叉樹的特性衰抑，結點在向量中的相對位置蘊含著結點之間的關系象迎，如bt[5]的雙親在bt[2]，他的左右孩子在bt[10]呛踊，bt[11]砾淌。但這種順序存儲結構僅適合于完全二叉樹。如果一般的二叉樹也按照這種方式存儲谭网，不存在的結點也需要占位汪厨。如對于下面的二叉樹：
他的順序存儲結構如下：
這樣非常浪費空間。
(2) 鏈式存儲結構：
表示二叉樹的鏈表至少包含三個域：數(shù)據(jù)域和左愉择、右指針域（二叉鏈表）劫乱，有時為了便于找到結點的雙親，還可以在結點結構中增加一個指向其雙親結點的指針域（三叉鏈表）锥涕。
//二叉樹的二叉鏈表結構衷戈，也就是二叉樹的存儲結構，1個數(shù)據(jù)域层坠，2個指針域（分別指向左右孩子）
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
三殖妇、遍歷二叉樹
1、 遍歷的概念
二叉樹是由三個基本單元組成：根結點破花，左子樹谦趣，右子樹疲吸，因此依次遍歷這三部分，就遍歷了整個二叉樹前鹅，按遍歷的順序可劃分為：前(根)序遍歷（根->左子樹->右子樹）摘悴，中(根)序遍歷（左子樹->根->右子樹），后(根)序遍歷（左子樹->右子樹->根）舰绘。
如圖所示的二叉樹：
前序遍歷：A B D H I E J C F K G
中序遍歷：H D I B E J A F K C G
后序遍歷：H I D J E B K F G C A
前序遍歷二叉樹遞歸算法：
void PreOrderTraverse(BiTree T, int level)
{
if (T == NULL)
return;
PreOrderTraverse(T->lchild, level + 1);
PreOrderTraverse(T->rchild, level + 1);
}
2蹂喻、 遍歷的考題
(1) 根據(jù)前序、中序遍歷的結果除盏，求后序遍歷
例：
前序遍歷：G D A F E M H Z
中序遍歷：A D E F G H M Z
A． 根據(jù)前序遍歷的特點叉橱，我們知道根結點為G
B． 觀察中序遍歷A D E F G H M Z。其中根節(jié)點G左側的A D E F必然是根結點的左子樹者蠕，G右側的H M Z必然是根結點的右子樹窃祝。
C． 觀察左子樹A D E F，左子樹中的根節(jié)點必然是根的左孩子踱侣。在前序遍歷中粪小，根結點的左孩子位于根結點G之后，所以左子樹的根節(jié)點為D抡句，根據(jù)中序遍歷的結果D的左側A是左子樹探膊，D的右側E F是右子樹，以此類推待榔。
D． 同樣的道理逞壁，根結點的右子樹節(jié)點H M Z中的根節(jié)點也可以通過前序遍歷求得。在前序遍歷中锐锣，一定是先把根結點和根結點的所有左子樹節(jié)點遍歷完之后才會遍歷右子樹腌闯，并且遍歷的右子樹的第一個節(jié)點就是右子樹的根節(jié)點。所以根據(jù)前序遍歷的結果雕憔，右子樹節(jié)點H M Z的排序是M H Z姿骏，因此M是右子樹的根結點，按照中序遍歷的結果M的左側H是左子樹斤彼，M的右側Z是右子樹分瘦，以此類推。
E． 觀察發(fā)現(xiàn)琉苇，上面的過程是遞歸的嘲玫。先找到當前樹的根節(jié)點，然后劃分為左子樹并扇，右子樹趁冈，然后進入左子樹重復上面的過程，然后進入右子樹重復上面的過程。最后就可以還原一棵樹了渗勘。
F． 那么這棵樹就是這樣的
(2) 根據(jù)中序、后序遍歷的結果俩莽，求前序遍歷
例：
中序遍歷：A D E F G H M Z
后序遍歷：A E F D H Z M G
A. 根據(jù)后序遍歷的特點旺坠，我們知道后序遍歷最后一個結點即為根結點，即根結點為G.
B. 觀察中序遍歷A D E F G H M Z扮超。其中根結點G左側的ADEF必然是根結點的左子樹取刃， G右側的H M Z必然是根結點的右子樹。
C. 觀察左子樹A D E F出刷，左子樹的根節(jié)點必然是根結點的左孩子璧疗。在后序遍歷中，根結點是最后一個遍歷的馁龟，根據(jù)后續(xù)遍歷的結果崩侠，D是左子樹最后一個遍歷的結點，因此D就是左子樹的根節(jié)點坷檩，按照中序遍歷的結果D的左側A是左子樹却音，D的右側E F是右子樹，以此類推矢炼。
D. 同樣的道理系瓢，根結點的右子樹H M Z中的根節(jié)點也可以通過后序遍歷求得。在后序遍歷中句灌，一定是最后才遍歷根結點夷陋，根據(jù)后續(xù)遍歷的結果，M是右子樹的根結點胰锌，按照中序遍歷的結果M的左側H是左子樹骗绕，M的右側Z是右子樹，以此類推匕荸。
E. 上面的過程是遞歸的爹谭。先找到當前樹的根節(jié)點，然后劃分為左子樹榛搔，右子樹诺凡，然后進入左子樹重復上面的過程，然后進入右子樹重復上面的過程践惑。最后就可以還原一棵樹了
