二叉樹的定義和基本術語
二叉樹的基本概念
二叉樹是n（n>=0）個結點的有限集合
①或者為空的二叉樹，即n=0
②或者由一個根結點和兩個互不相交的被稱為根的左子樹和右子樹組成，左子樹和右子樹又分別是一顆二叉樹
特點：
1、每一個結點至多只有兩棵子樹
2、左右子樹不能顛倒（二叉樹是有序樹）
注意區(qū)別：度為2的有序樹與二叉樹的區(qū)別
度為2的樹：肯定是非空樹，所有結點的度<=2，至少有一個結點的度為2
二叉樹：可以為空樹，所有的結點只要<=2就可
特殊的二叉樹
滿二叉樹
定義：一顆高度為n，且有 2?-1 個結點的二叉樹
特點：
1、只有最后一層有葉子結點
2、不存在度為1的結點（只存在度為0或者2的結點）
3、按層序從1開始編號，結點 i 的左孩子為 2i，右孩子為 2i+1，結點 i 的父節(jié)點為 ? i/2 ?；
完全二叉樹
定義：當且僅當其每個結點都與高度為 h 的滿二叉樹中的編號為 1~n 的結點一一對應時，稱為完全二叉樹
特點：
1、只有最后兩層有葉子結點
2、最多只有一個度為1的結點
3、按層序從1開始編號，結點 i 的左孩子為 2i，右孩子為 2i+1，結點 i 的父節(jié)點為 ? i/2 ?；（如果有的話）
4、i <= ? n/2 ? 為分支結點，i > ? n/2 ? 為葉子結點
如果某結點只有一個孩子，那么這個孩子一定是左孩子
二叉排序樹
定義：一顆二叉樹或者空二叉樹具有如下性質的稱為二叉排序樹
1、左子樹上所有結點的關鍵字均小于根結點的關鍵字
2、右子樹上所有結點的關鍵字均大于根結點的關鍵字
3、左子樹和右子樹又各是一棵二叉排序樹
二叉排序樹可用于元素的排序和搜索
平衡二叉樹
定義：樹上任一結點的左子樹和右子樹的深度之差不超過1
平衡二叉樹能有更高的搜索效率
二叉樹的?？夹再|
考點一：設非空二叉樹中度為0、1、2的結點個數分別為n0、n1、n2，則 n0 = n2 + 1; ( 葉子結點比二分支結點多一個 )
假設樹中結點總數為n，則
① n = n0 + n1 +n2
② n = n1 + 2*n2 + 1 （樹的結點數 = 總度數 + 1）
②-①得 n0 = n2 + 1
考點二：二叉樹第 i 層至多有 2??1 個結點（i>=1）
源于: m 叉樹第 i 層至多有 m??1 個結點（i>=1）
考點三：高度為 n 的二叉樹至多有 2? - 1 個結點（滿二叉樹）
源于: 高度為 n 的 m 叉樹至多有 m? - 1/m-1 個結點
完全二叉樹的常考性質
?？伎键c2：對于完全二叉樹，可以由結點數 n 推出度為0、1、2的結點個數為n0、n1、n2
完全二叉樹最多只有一個度為1的結點，所以
n1 = 0或1
n0 = n2 + 1 ----> n0 + n2 = 2*n2 + 1 一定是奇數
若完全二叉樹有 2k 個（偶數）個結點，則 n = n1 + n2 + n3，由上面得 n0 + n2 一定是奇數，所以只有 n1 = 1 時， n 才會是偶數
所以 n1 = 1，n0 = k，n2 = k-1
若完全二叉樹有 2k-1 個（奇數）個結點，則 n = n1 + n2 + n3，由上面得 n0 + n2 一定是奇數，所以只有 n1 = 0 時， n 才會是奇數
所以 n1 = 0，n0 = k，n2 = k-1
二叉樹的存儲結構
順序存儲
定義一個長度為 MaxSize 的數組t，按照從上至下，從左至右的順序依次存儲完全二叉樹中的各個結點
#define MaxSize 100
struct TreeNode{
ElemType value; // 結點中的數據元素
bool isEmpty; // 結點是否為空
}
// 初始化時所有結點標記為空
for(int i = 0; i < MaxSize; i++){
t[i].isEmpty = true;
}
TreeNode t[MaxSize]
幾個重要的?？嫉幕静僮?/strong>
i 的左孩子 ———— 2i
i 的右孩子 ———— 2i+1
i 的父節(jié)點 ———— ? i/2 ?
i 所在的層次 ————
若完全二叉樹中共有n個結點，則
判斷 i 是否有左孩子？ ———— 2i <= n
判斷 i 是否有右孩子？ ———— 2i+1 <= n
判斷 i 是否是葉子/分支結點？ ———— i > ? n/2 ?
注意：如果不是完全二叉樹，依然按照層序將各個結點順序存儲，那么無法從結點編號反映出以上這些邏輯關系，所以一定要把二叉樹的結點編號與完全二叉樹對應起來，但是會導致出現很多空值的存儲單元
最壞情況：高度為 n 且只有 n 個結點的單支樹（所有結點只有右孩子），也至少需要 2? - 1 個存儲單元
結論：二叉樹的順序存儲結構，只適合存儲完全二叉樹
鏈式存儲
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild; // 左右孩子指針
}BiTNode,*BiTree;
假設有n個結點，則有2n個指針域，除了根結點，每一個結點頭上都會連接一個指針域，那么就有n-1個有值的指針域，得出就會有n+1個空指針域
n個結點的二叉鏈表共有n+1個空鏈域
根據實際需求決定要不要加父結點指針（三叉鏈表——方便找父結點）
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild; // 左右孩子指針
struct BiTNode *parent; // 父結點指針
}BiTNode,*BiTree;
二叉樹的先中后序遍歷
- 先序遍歷：根左右
- 中序遍歷：左根右
- 后序遍歷：左右根
其中這三種遍歷方式與前中后綴表達式的關系
先序遍歷——>前綴表達式
中序遍歷——>中綴表達式（需要加界限符）
后序遍歷——>后綴表達式
先序遍歷（空間復雜度：O（h））
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //訪問根結點
PreOrder(T->lchild); // 遞歸遍歷左子樹
PreOrder(T->rchild); // 遞歸遍歷右子樹
}
}
中序遍歷
void PreOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild); // 遞歸遍歷左子樹
visit(T); //訪問根結點
PreOrder(T->rchild); // 遞歸遍歷右子樹
}
}
后序遍歷
void PreOrder(BiTree T){
if(T!=NULL){
PreOrder(T->lchild); // 遞歸遍歷左子樹
PreOrder(T->rchild); // 遞歸遍歷右子樹
visit(T); //訪問根結點
}
}
應用
求樹的深度
int treeDepth(BiTree T){
if(T == NULL)
return 0;
else{
int l = treeDepth(T->lchild);
int r = treeDepth(T->rchild);
// 樹的深度=Max(左子樹深度，右子樹深度) + 1
return l>r ? l+1 : r+1;
}
}
二叉樹的層序遍歷
算法思想：
①初始化一個輔助隊列
②根結點入隊
③若隊列非空，則隊頭結點出隊，訪問該結點，并將其左、右孩子插入隊尾（如果有的話）
④重復③直至隊列為空
// 二叉樹的結點（鏈式存儲）
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
// 鏈式隊列結點
typedef struct LinkNode{
BiTNode *data; // 存指針，而不是結點
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear; // 隊頭隊尾
}LinkQueue;
// 層序遍歷
void LevelOrder(BiTree T){
LinkQueue(Q);
InitQueue(Q); // 初始化輔助隊列
BiTree p;
EnQueue(Q,T); // 將根結點入隊
while(!IsEmpty(Q)){
DeQueue(Q,p); // 隊頭結點出隊
visit(p); // 訪問出隊結點
if(p->lchild!=NULL)
EnQueue(Q,(p->lchild); // 左孩子入隊
if(p->rchild!=NULL)
EnQueue(Q,(p->rchild); // 右孩子入隊
}
}
由遍歷序列構造二叉樹
若只給出一顆二叉樹的前中后序遍歷序列中的一種，不能唯一確定一棵二叉樹
能構造二叉樹的遍歷序列組合
1、前序+中序
2、后序+中序
3、層序+中序
線索二叉樹
問題1：如何找到指定結點在中序遍歷序列中的前驅？
問題2：如何找到結點的中序后繼？
找前驅和后繼很不方便，遍歷操作必須從根開始
還記得之前學到的，n個結點的二叉樹，有n+1個空鏈域，可以用來記錄前驅、后繼的信息
線索二叉樹的存儲結構
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左右線索標志
}ThreadNode,*ThreadTree;
// tag=0 表示指針指向孩子
// tag=1 表示指針是線索
二叉樹的線索化
中序線索化
// 線索二叉樹結點
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左右線索標志
}ThreadNode,*ThreadTree;
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子樹為空，建立前驅線索
q->lchild=pre;
q->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){ //前驅結點的右孩子為空，建立前驅結點的后驅線索
pre->rchild=q;
pre->rtag=1;
}
pre=q;
}
//中序遍歷二叉樹，一邊遍歷一邊線索化
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild); // 中序遍歷左子樹
visit(T); // 訪問根結點
InThread(T->rchild); // 中序遍歷右子樹
}
}
// 全局變量 pre，指向當前訪問結點的前驅
ThreadNode *pre=NULL;
// 中序線索化二叉樹T
void CreateInThread(ThreadTree T){
pre=NULL; // pre初始化為NULL
if(T!=NULL){
InThread(T) //中序線索化二叉樹
if(pre->rchild==NULL)
pre->rtag=1; // 處理遍歷的最后一個點
}
}
先序線索化（與中序遍歷有一點不一樣：為了防止重復指向，需要判斷l(xiāng)child不是前驅線索）
// 線索二叉樹結點
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左右線索標志
}ThreadNode,*ThreadTree;
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子樹為空，建立前驅線索
q->lchild=pre;
q->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){ //前驅結點的右孩子為空，建立前驅結點的后驅線索
pre->rchild=q;
pre->rtag=1;
}
pre=q;
}
//先序遍歷二叉樹，一邊遍歷一邊線索化
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T); // 訪問根結點
if(T->ltag==0){ // 與中序遍歷不一樣的地方，為了防止重復指向，需要判斷l(xiāng)child不是前驅線索
PreThread(T->lchild); // 與中序遍歷不一樣的地方，為了防止重復指向，需要判斷l(xiāng)child不是前驅線索
PreThread(T->rchild);
}
}
// 全局變量 pre，指向當前訪問結點的前驅
ThreadNode *pre=NULL;
// 先序線索化二叉樹T
void CreateInThread(ThreadTree T){
pre=NULL; // pre初始化為NULL
if(T!=NULL){
InThread(T) //先序線索化二叉樹
if(pre->rchild==NULL)
pre->rtag=1; // 處理遍歷的最后一個點
}
}
后序線索化（和中序差不多）
// 線索二叉樹結點
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag; // 左右線索標志
}ThreadNode,*ThreadTree;
void visit(ThreadNode *q){
if(q->lchild==NULL){ //左子樹為空，建立前驅線索
q->lchild=pre;
q->ltag=1;
}
if(pre!=NULL&&pre->rchild==NULL){ //前驅結點的右孩子為空，建立前驅結點的后驅線索
pre->rchild=q;
pre->rtag=1;
}
pre=q;
}
//后序遍歷二叉樹，一邊遍歷一邊線索化
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild); // 后序遍歷左子樹
InThread(T->rchild); // 后序遍歷右子樹
visit(T); // 訪問根結點
}
}
// 全局變量 pre，指向當前訪問結點的前驅
ThreadNode *pre=NULL;
// 后序線索化二叉樹T
void CreateInThread(ThreadTree T){
pre=NULL; // pre初始化為NULL
if(T!=NULL){
InThread(T) //后序線索化二叉樹
if(pre->rchild==NULL)
pre->rtag=1; // 處理遍歷的最后一個點
}
}
二叉樹的線索化
中序線索二叉樹中找到指定結點*p的中序后繼next
① 若 p->rtag=1, 則 next = p->rchild
② 若 p->rtag=0, 則 next = p的右子樹中最左下結點
// 找到以p為根的子樹中，第一個被中序遍歷的結點
ThreadNode *Firstnode(ThreadNode *p){
// 循環(huán)找到最左下結點（不一定是葉結點）
while(p->ltag==0) p=p->lchild;
return p;
}
// 在中序線索二叉樹中找到結點p的后繼結點
ThreadNode *Nextnode(ThreadNode *p){
// 右子樹下最左的結點
if(p->rtag==0) return Firstnode(p->rchild);
esle return p->rchild; // rtag ==1 直接返回后繼線索
}
// 對中序線索二叉樹進行中序遍歷（利用線索實現的非遞歸算法）空間復雜O（1）
void Inorder(TreadNode *T){
for(ThreadNode *p=Firstnode(T);p!=NULL;p=Nextnode(p)){
visit(p);
}
}
中序線索二叉樹中找到指定結點*p的中序前驅pre
① 若 p->ltag=1, 則 pre= p->rchild
② 若 p->rlag=0, 則 pre= p的左子樹中最右下結點
// 找到以p為根的子樹中，最后一個被中序遍歷的結點
ThreadNode *Lastnode(ThreadNode *p){
// 循環(huán)找到最左下結點（不一定是葉結點）
while(p->rtag==0) p=p->rchild;
return p;
}
// 在中序線索二叉樹中找到結點p的前驅結點
ThreadNode *Prenode(ThreadNode *p){
// 左子樹中最右下結點
if(p->ltag==0) return Lastnode(p->lchild);
esle return p->lchild; // ltag ==1 直接返回前驅線索
}
// 對中序線索二叉樹進行逆向中序遍歷
void RevInorder(TreadNode *T){
for(ThreadNode *p=Lastnode(T);p!=NULL;p=Prenode(p)){
visit(p);
}
}
在先序線索二叉樹中找到指定結點*p的先序后繼next
① 若 p->rtag=1, 則 next = p->rchild
② 若 p->rtag=0,
1、若p有左孩子，則先序后繼為左孩子
2、若p沒有左孩子，則先序后繼為右孩子
在先序線索二叉樹中找到指定結點*p的先序前驅pre
① 若 p->ltag=1, 則 next = p->lchild
② 若 p->ltag=0, 需要從頭開始遍歷
在后序線索二叉樹中找到指定結點*p的后序前驅pre
① 若 p->ltag=1, 則 pre= p->lchild
② 若 p->ltag=0,
1、若p有右孩子，則后序前驅為右孩子
2、若p沒有右孩子，則后序前驅為左孩子文章來源：http://www.zghlxwxcb.cn/news/detail-739224.html
在后序線索二叉樹中找到指定結點*p的后序后繼next
① 若 p->rtag=1, 則 next = p->rchild
② 若 p->rtag=0, 需要從頭開始遍歷文章來源地址http://www.zghlxwxcb.cn/news/detail-739224.html
到了這里，關于數據結構詳細筆記——二叉樹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
