樹，二叉樹的定義：
二叉樹是N個節(jié)點(diǎn)的有效集，二叉樹與無序數(shù)不同，二叉樹每個節(jié)點(diǎn)只有兩個子樹置谦。
二叉樹的性質(zhì)：
- 二叉樹的第i層最多有2的i-1次方個節(jié)點(diǎn)。
- 二叉樹最多有2的i次方減一個節(jié)點(diǎn)亿傅。
- 在任意一個二叉樹中，若葉子節(jié)點(diǎn)的個數(shù)為n瘟栖，有兩個子樹的節(jié)點(diǎn)為n0葵擎，則有n=n0+1。
二叉樹的兩種形式：滿二叉樹與完全二叉樹
- 滿二叉樹：
滿二叉樹的每一個節(jié)點(diǎn)都有兩個子樹半哟。除最下一層外不存在度數(shù)為一的節(jié)點(diǎn)酬滤。
n層的滿二叉樹，節(jié)點(diǎn)數(shù)為2的k次方減一寓涨。 - 完全二叉樹：
完全二叉樹的節(jié)點(diǎn)完全按照從上往下從左到右的順序填補(bǔ)盯串。
最后一層總是在右部分空缺的樹。
完全二叉樹是滿二叉樹戒良。滿二叉樹不一定是完全二叉樹体捏。
二叉樹的存儲結(jié)構(gòu)：
- 順序存儲結(jié)構(gòu)
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)
二叉樹的遍歷：
- 遍歷方案 ：(簡單的遞歸遍歷)
-
中序遍歷(InorderTraversal):
typedef node* BinTree； void LNR (BinTree t){ if (t) { LNR (t->left); printf ("%d",t->date); LNR (t->right); } } 前序遍歷(PreorderTraversal):
void NLR (BinTree t){
if (t) {
printf ("%d",t->date);
NLR (t->left);
NLR (t->right);
}
}后序遍歷(PostorderTraversal):
void LRN (BinTree t){
if (t) {
LRN (t->left);
LRN (t->right);
printf ("%d",t->date);
}
}
二叉樹鏈?zhǔn)酱鎯Φ臉?gòu)造：
-
構(gòu)造運(yùn)算：（前序構(gòu)造）
void creatBinTree (BinTree \*t) {//t為指向指針的指針糯崎，修改\*t既為修改指針 char temp;//定義一個存放數(shù)據(jù)的字符型數(shù)據(jù) temp=getchar(); if (temp == '') \*t = NULL; else \*t = (BinTree *)malloc(sizeof(BinTree)); //生成節(jié)點(diǎn) (\*t)->date = temp; creatBinTree (&(\*t)->left); creatBinTree (&(\*t)->right); } } //此函數(shù)的實(shí)參為根地址的地址
線索二叉樹：
- 定義:
具有 n 個結(jié)點(diǎn)的二叉鏈表中几缭，其二叉鏈表的 n 個結(jié)點(diǎn)中共有 2n 個指針域，在這 2n 個指針域中沃呢，真正用于指向后件（左子結(jié)點(diǎn)或右子結(jié)點(diǎn)）的指針域只有 n-1 個年栓，而另外的 n+1 個指針域都是空的。這樣就利用二叉鏈表中的空指針域薄霜，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針（這種附加的指針稱為 " 線索 " ）某抓，這種加上了線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹稱為線索二叉樹
根據(jù)線索性質(zhì)的不同惰瓜，線索二叉樹可分為前序線索二叉樹否副、中序線索二叉樹和后序線索二叉樹三種。- 注意：線索鏈表解決了二叉鏈表找左鸵熟、右孩子困難的問題副编，出現(xiàn)了無法直接找到該結(jié)點(diǎn)在某種遍歷序列中的前趨和后繼結(jié)點(diǎn)的問題。
部分內(nèi)容引自下列blog及網(wǎng)站：
http://student.zjzk.cn/course_ware/data_structure/web/main.htm
http://waret.iteye.com/blog/709779
