一映企、定義
有且只有1個(gè)稱為根的節(jié)點(diǎn)悟狱；
有若干個(gè)互不相交的子樹，這些子樹本身也是一棵樹堰氓。
樹由節(jié)點(diǎn)和邊（指針域）組成挤渐。
每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，但可以有多個(gè)子節(jié)點(diǎn)双絮；
但有一個(gè)節(jié)點(diǎn)例外浴麻，該節(jié)點(diǎn)沒有父節(jié)點(diǎn)，此節(jié)點(diǎn)稱為根節(jié)點(diǎn)囤攀。
二软免、專業(yè)術(shù)語
1、節(jié)點(diǎn)
2抚岗、父節(jié)點(diǎn)
3或杠、子節(jié)點(diǎn)
4、子孫
5宣蔚、堂兄弟
6、深度：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)认境。
根節(jié)點(diǎn)是第1層胚委。
7、葉子節(jié)點(diǎn)：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)叉信。
8亩冬、非終端節(jié)點(diǎn)/非葉子節(jié)點(diǎn)：有子節(jié)點(diǎn)的節(jié)點(diǎn)。
根節(jié)點(diǎn)既可以是葉子節(jié)點(diǎn)，也可以是非葉子節(jié)點(diǎn)硅急。
9覆享、節(jié)點(diǎn)的度：子節(jié)點(diǎn)的個(gè)數(shù)。
樹的度：節(jié)點(diǎn)的度中最大的度稱為樹的度营袜。
三撒顿、樹的分類
一般樹：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)都不受限制。
二叉樹：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)最多2個(gè)荚板，且子節(jié)點(diǎn)的位置不可更改凤壁。
二叉樹的分類：
- 一般二叉樹
- 滿二叉樹：在不增加樹的層數(shù)的前提下，無法再多添加一個(gè)節(jié)點(diǎn)的二叉樹是滿二叉樹跪另。
- 完全二叉樹：如果只是刪除了滿二叉樹最底層拧抖、最右邊的連續(xù)若干個(gè)節(jié)點(diǎn)，這樣形成的二叉樹就是完全二叉樹免绿。
完全二叉樹的優(yōu)點(diǎn)：
查找某個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有沒有子節(jié)點(diǎn)）的速度很快唧席；
滿二叉樹是完全二叉樹的一個(gè)特例；完全二叉樹包含滿二叉樹嘲驾。
森林：n個(gè)互不相交的樹的集合袱吆。
四、樹的存儲(chǔ)
1距淫、二叉樹的存儲(chǔ)：
連續(xù)存儲(chǔ)[完全二叉樹]：
要以數(shù)組方式來存绞绒，必須先轉(zhuǎn)化成完全二叉樹才能存儲(chǔ)。因?yàn)殚畔荆槐４嬗行У狞c(diǎn)蓬衡，而不轉(zhuǎn)化的話，是無法知道以前的樹是怎么構(gòu)造出來的彤枢。
這樣存儲(chǔ)狰晚，耗用內(nèi)存空間過大。
鏈?zhǔn)酱鎯?chǔ)：相對(duì)比較簡(jiǎn)單缴啡，耗用內(nèi)存空間也比較小壁晒。
2、一般樹的存儲(chǔ)
（1）雙親表示法：求父節(jié)點(diǎn)方便业栅。
（2）孩子表示法：求子節(jié)點(diǎn)方便秒咐。
（3）雙親孩子表示法：求父節(jié)點(diǎn)和子節(jié)點(diǎn)都方便。
（4）二叉樹表示法（孩子兄弟鏈表表示法）：一般樹轉(zhuǎn)化成二叉樹來存儲(chǔ)碘裕。
具體轉(zhuǎn)換方法：設(shè)法保證任意一個(gè)節(jié)點(diǎn)的左指針域指向它的第一個(gè)孩子携取，右指針域指向它的下一個(gè)兄弟。
只要能滿足此條件帮孔，就可以把一個(gè)普通樹轉(zhuǎn)化為二叉樹雷滋。
一般樹轉(zhuǎn)化成的二叉樹，一定沒有右子樹。
3晤斩、森林的存儲(chǔ)
森林轉(zhuǎn)化成二叉樹來存儲(chǔ)焕檬。
五、二叉樹的遍歷
1烹俗、先序遍歷
先訪問根節(jié)點(diǎn)爆侣，再先序遍歷左子樹，再先序遍歷右子樹幢妄。
ABDCEFG
2兔仰、中序遍歷
中序遍歷左子樹，再訪問根節(jié)點(diǎn)蕉鸳，再中序遍歷右子樹乎赴。
DBAECGF
3、后序遍歷
中序遍歷左子樹潮尝，再中序遍歷右子樹榕吼，再訪問根節(jié)點(diǎn)。
DBEGFCA
4勉失、已知兩種遍歷序列求原始二叉樹
通過先序和中序羹蚣，或者中序和后序，我們可以還原出原始的二叉樹乱凿。但是顽素，通過先序和后序是無法還原出原始的二叉樹的。
只有通過先序和中序徒蟆，或者中序和后序胁出，才可以唯一地確定一個(gè)二叉樹。
5段审、已知先序和中序全蝶，求后序
先序：ABCDEFGH
中序：BDCEAFHG
求后序？
后序序列為：DECBHGFA
6寺枉、已知中序和后序抑淫，求先序
中序：BDCEAFHG
后序：DECBHGFA
求先序？
先序：ABCDEFGH
7型凳、鏈?zhǔn)蕉鏄浔闅v-程序
#include <stdio.h>
#include <malloc.h>
struct BTNode
{
char data;
struct BTNode * pLchild;
struct BTNode * pRchild;
};
struct BTNode * CreateBTree(void);
void PreTraverseBTree(struct BTNode * pT);
void InTraverseBTree(struct BTNode * pT);
void PostTraverseBTree(struct BTNode * pT);
int main(void)
{
struct BTNode * pT = CreateBTree(); // pT保存根節(jié)點(diǎn)的地址
printf("先序：\n");
PreTraverseBTree(pT); // 先序遍歷
printf("中序：\n");
InTraverseBTree(pT); // 中序遍歷
printf("后序：\n");
PostTraverseBTree(pT); // 后序遍歷
return 0;
}
void PreTraverseBTree(struct BTNode * pT)
{
if(NULL != pT)
{
printf("%c\n", pT->data); // 先訪問根節(jié)點(diǎn)
if(NULL != pT->pLchild)
{
PreTraverseBTree(pT->pLchild); // 先序遍歷左子樹丈冬。pT->pLchild 代表整個(gè)左子樹
}
if(NULL != pT->pRchild)
{
PreTraverseBTree(pT->pRchild); // 先序遍歷右子樹。pT->pRchild 代表整個(gè)右子樹
}
}
}
void InTraverseBTree(struct BTNode *pT)
{
if(NULL != pT)
{
if(NULL != pT->pLchild)
{
InTraverseBTree(pT->pLchild); // 中序遍歷左子樹甘畅。pT->pLchild 代表整個(gè)左子樹
}
printf("%c\n", pT->data); // 訪問根節(jié)點(diǎn)
if(NULL != pT->pRchild)
{
InTraverseBTree(pT->pRchild); // 中序遍歷右子樹。pT->pRchild 代表整個(gè)右子樹
}
}
}
void PostTraverseBTree(struct BTNode *pT)
{
if(NULL != pT)
{
if(NULL != pT->pLchild)
{
PostTraverseBTree(pT->pLchild); // 后序遍歷左子樹。pT->pLchild 代表整個(gè)左子樹
}
if(NULL != pT->pRchild)
{
PostTraverseBTree(pT->pRchild); // 后序遍歷右子樹疏唾。pT->pRchild 代表整個(gè)右子樹
}
printf("%c\n", pT->data); // 訪問根節(jié)點(diǎn)
}
}
// 靜態(tài)創(chuàng)建一個(gè)鏈?zhǔn)蕉鏄?
// 返回根節(jié)點(diǎn)的地址
struct BTNode * CreateBTree(void)
{
struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';
pA->pLchild = pB;
pA->pRchild = pC;
pB->pLchild = pB->pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = pE->pRchild = NULL;
return pA;
};
六蓄氧、樹的應(yīng)用
樹是數(shù)據(jù)庫中數(shù)據(jù)組織的一種重要形式。
操作系統(tǒng)父子進(jìn)程的關(guān)系本身就是一棵樹槐脏。
面向?qū)ο笳Z言中類的繼承關(guān)系本身就是一棵樹喉童。
赫夫曼樹。
