本期是C++基礎語法分享的第十四節，今天給大家來梳理一下樹！

二叉樹

BinaryTree.cpp：

#include 《stdio.h》#include 《stdlib.h》

#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define SUCCESS 1#define UNSUCCESS 0#define dataNum 5int i = 0;int dep = 0;char data［dataNum］ = { ‘A’， ‘B’， ‘C’， ‘D’， ‘E’ };

typedef int Status;typedef char TElemType;

// 二叉樹結構typedef struct BiTNode{ TElemType data; struct BiTNode *lchild， *rchild;}BiTNode， *BiTree;

// 初始化一個空樹void InitBiTree（BiTree &T）{ T = NULL;}

// 構建二叉樹BiTree MakeBiTree（TElemType e， BiTree L， BiTree R）{ BiTree t; t = （BiTree）malloc（sizeof（BiTNode））; if （NULL == t） return NULL; t-》data = e; t-》lchild = L; t-》rchild = R; return t;}

// 訪問結點Status visit（TElemType e）{ printf（“%c”， e）; return OK;}

// 對二叉樹T求葉子結點數目int Leaves（BiTree T）{ int l = 0， r = 0; if （NULL == T） return 0; if （NULL == T-》lchild && NULL == T-》rchild） return 1;

// 求左子樹葉子數目 l = Leaves（T-》lchild）; // 求右子樹葉子數目 r = Leaves（T-》rchild）; // 組合 return r + l;}

// 層次遍歷：dep是個全局變量，高度int depTraverse（BiTree T）{ if （NULL == T） return ERROR;

dep = （depTraverse（T-》lchild） 》 depTraverse（T-》rchild）） ？ depTraverse（T-》lchild） ： depTraverse（T-》rchild）;

return dep + 1;}

// 高度遍歷：lev是局部變量，層次void levTraverse（BiTree T， Status（*visit）（TElemType e）， int lev）{ if （NULL == T） return; visit（T-》data）; printf（“的層次是%d

”， lev）;

levTraverse（T-》lchild， visit， ++lev）; levTraverse（T-》rchild， visit， lev）;}

// num是個全局變量void InOrderTraverse（BiTree T， Status（*visit）（TElemType e）， int &num）{ if （NULL == T） return; visit（T-》data）; if （NULL == T-》lchild && NULL == T-》rchild） { printf（“是葉子結點”）; num++; } else printf（“不是葉子結點”）; printf（“

”）; InOrderTraverse（T-》lchild， visit， num）; InOrderTraverse（T-》rchild， visit， num）;}

// 二叉樹判空Status BiTreeEmpty（BiTree T）{ if （NULL == T） return TRUE; return FALSE;}

// 打斷二叉樹：置空二叉樹的左右子樹Status BreakBiTree（BiTree &T， BiTree &L， BiTree &R）{ if （NULL == T） return ERROR; L = T-》lchild; R = T-》rchild; T-》lchild = NULL; T-》rchild = NULL; return OK;}

// 替換左子樹Status ReplaceLeft（BiTree &T， BiTree <）{ BiTree temp; if （NULL == T） return ERROR; temp = T-》lchild; T-》lchild = LT; LT = temp; return OK;}

// 替換右子樹Status ReplaceRight（BiTree &T， BiTree &RT）{ BiTree temp; if （NULL == T） return ERROR; temp = T-》rchild; T-》rchild = RT; RT = temp; return OK;}

// 合并二叉樹void UnionBiTree（BiTree &Ttemp）{ BiTree L = NULL， R = NULL; L = MakeBiTree（data［i++］， NULL， NULL）; R = MakeBiTree（data［i++］， NULL， NULL）; ReplaceLeft（Ttemp， L）; ReplaceRight（Ttemp， R）;}

int main（）{ BiTree T = NULL， Ttemp = NULL;

InitBiTree（T）; if （TRUE == BiTreeEmpty（T）） printf（“初始化T為空

”）; else printf（“初始化T不為空

”）;

T = MakeBiTree（data［i++］， NULL， NULL）;

Ttemp = T; UnionBiTree（Ttemp）;

Ttemp = T-》lchild; UnionBiTree（Ttemp）;

Status（*visit1）（TElemType）; visit1 = visit; int num = 0; InOrderTraverse（T， visit1， num）; printf（“葉子結點是 %d

”， num）;

printf（“葉子結點是 %d

”， Leaves（T））;

int lev = 1; levTraverse（T， visit1， lev）;

printf（“高度是 %d

”， depTraverse（T））;

getchar（）; return 0;}

性質

（1）非空二叉樹第 i 層最多 2（i-1） 個結點 （i 》= 1）

（2）深度為 k 的二叉樹最多 2k - 1 個結點 （k 》= 1）

（3）度為 0 的結點數為 n0，度為 2 的結點數為 n2，則 n0 = n2 + 1

（4）有 n 個結點的完全二叉樹深度 k = ? log2（n） ? + 1

（5）對于含 n 個結點的完全二叉樹中編號為 i （1 《= i 《= n） 的結點

a.若 i = 1，為根，否則雙親為 ? i / 2 ?

b.若 2i 》 n，則 i 結點沒有左孩子，否則孩子編號為 2i

c.若 2i + 1 》 n，則 i 結點沒有右孩子，否則孩子編號為 2i + 1

存儲結構

二叉樹數據結構

typedef struct BiTNode{ TElemType data; struct BiTNode *lchild， *rchild;}BiTNode， *BiTree;

順序存儲

二叉樹順序存儲圖片

鏈式存

二叉樹鏈式存儲圖片

遍歷方式

a.先序遍歷

b.中序遍歷

c.后續遍歷

d.層次遍歷

分類

（1）滿二叉樹

（2）完全二叉樹（堆）

大頂堆：根 》= 左 && 根 》= 右

小頂堆：根 《= 左 && 根 《= 右

（3）二叉查找樹（二叉排序樹）：左 《 根 《 右

（4）平衡二叉樹（AVL樹）：| 左子樹樹高 - 右子樹樹高 | 《= 1

（5）最小失衡樹：平衡二叉樹插入新結點導致失衡的子樹：調整：

LL型：根的左孩子右旋

RR型：根的右孩子左旋

LR型：根的左孩子左旋，再右旋

RL型：右孩子的左子樹，先右旋，再左旋

其他樹及森林

1、樹的存儲結構

（1）雙親表示法

（2）雙親孩子表示法

（3）孩子兄弟表示法

并查集

一種不相交的子集所構成的集合 S = {S1， S2， 。..， Sn}

2、平衡二叉樹（AVL樹）

性質

（1）| 左子樹樹高 - 右子樹樹高 | 《= 1

（2）平衡二叉樹必定是二叉搜索樹，反之則不一定

（3）最小二叉平衡樹的節點的公式：F（n）=F（n-1）+F（n-2）+1 （1 是根節點，F（n-1） 是左子樹的節點數量，F（n-2） 是右子樹的節點數量）

平衡二叉樹圖片

最小失衡樹

平衡二叉樹插入新結點導致失衡的子樹

調整：

LL 型：根的左孩子右旋

RR 型：根的右孩子左旋

LR 型：根的左孩子左旋，再右旋

RL 型：右孩子的左子樹，先右旋，再左旋

3、紅黑樹

RedBlackTree.cpp：

#define BLACK 1#define RED 0#include 《iostream》

using namespace std;

class bst {private：

struct Node { int value; bool color; Node *leftTree， *rightTree， *parent;

Node（） ： value（0）， color（RED）， leftTree（NULL）， rightTree（NULL）， parent（NULL） { }

Node* grandparent（） { if （parent == NULL） { return NULL; } return parent-》parent; }

Node* uncle（） { if （grandparent（） == NULL） { return NULL; } if （parent == grandparent（）-》rightTree） return grandparent（）-》leftTree; else return grandparent（）-》rightTree; }

Node* sibling（） { if （parent-》leftTree == this） return parent-》rightTree; else return parent-》leftTree; } };

void rotate_right（Node *p） { Node *gp = p-》grandparent（）; Node *fa = p-》parent; Node *y = p-》rightTree;

fa-》leftTree = y;

if （y ！= NIL） y-》parent = fa; p-》rightTree = fa; fa-》parent = p;

if （root == fa） root = p; p-》parent = gp;

if （gp ！= NULL） { if （gp-》leftTree == fa） gp-》leftTree = p; else gp-》rightTree = p; }

}

void rotate_left（Node *p） { if （p-》parent == NULL） { root = p; return; } Node *gp = p-》grandparent（）; Node *fa = p-》parent; Node *y = p-》leftTree;

fa-》rightTree = y;

if （y ！= NIL） y-》parent = fa; p-》leftTree = fa; fa-》parent = p;

if （root == fa） root = p; p-》parent = gp;

if （gp ！= NULL） { if （gp-》leftTree == fa） gp-》leftTree = p; else gp-》rightTree = p; } }

void inorder（Node *p） { if （p == NIL） return;

if （p-》leftTree） inorder（p-》leftTree）;

cout 《《 p-》value 《《 “ ”;

if （p-》rightTree） inorder（p-》rightTree）; }

string outputColor（bool color） { return color ？ “BLACK” ： “RED”; }

Node* getSmallestChild（Node *p） { if （p-》leftTree == NIL） return p; return getSmallestChild（p-》leftTree）; }

bool delete_child（Node *p， int data） { if （p-》value 》 data） { if （p-》leftTree == NIL） { return false; } return delete_child（p-》leftTree， data）; } else if （p-》value 《 data） { if （p-》rightTree == NIL） { return false; } return delete_child（p-》rightTree， data）; } else if （p-》value == data） { if （p-》rightTree == NIL） { delete_one_child（p）; return true; } Node *smallest = getSmallestChild（p-》rightTree）; swap（p-》value， smallest-》value）; delete_one_child（smallest）;

return true; } else { return false; } }

void delete_one_child（Node *p） { Node *child = p-》leftTree == NIL ？ p-》rightTree ： p-》leftTree; if （p-》parent == NULL && p-》leftTree == NIL && p-》rightTree == NIL） { p = NULL; root = p; return; }

if （p-》parent == NULL） { delete p; child-》parent = NULL; root = child; root-》color = BLACK; return; }

if （p-》parent-》leftTree == p） { p-》parent-》leftTree = child; } else { p-》parent-》rightTree = child; } child-》parent = p-》parent;

if （p-》color == BLACK） { if （child-》color == RED） { child-》color = BLACK; } else delete_case（child）; }

delete p; }

void delete_case（Node *p） { if （p-》parent == NULL） { p-》color = BLACK; return; } if （p-》sibling（）-》color == RED） { p-》parent-》color = RED; p-》sibling（）-》color = BLACK; if （p == p-》parent-》leftTree） rotate_left（p-》sibling（））; else rotate_right（p-》sibling（））; } if （p-》parent-》color == BLACK && p-》sibling（）-》color == BLACK && p-》sibling（）-》leftTree-》color == BLACK && p-》sibling（）-》rightTree-》color == BLACK） { p-》sibling（）-》color = RED; delete_case（p-》parent）; } else if （p-》parent-》color == RED && p-》sibling（）-》color == BLACK && p-》sibling（）-》leftTree-》color == BLACK && p-》sibling（）-》rightTree-》color == BLACK） { p-》sibling（）-》color = RED; p-》parent-》color = BLACK; } else { if （p-》sibling（）-》color == BLACK） { if （p == p-》parent-》leftTree && p-》sibling（）-》leftTree-》color == RED && p-》sibling（）-》rightTree-》color == BLACK） { p-》sibling（）-》color = RED; p-》sibling（）-》leftTree-》color = BLACK; rotate_right（p-》sibling（）-》leftTree）; } else if （p == p-》parent-》rightTree && p-》sibling（）-》leftTree-》color == BLACK && p-》sibling（）-》rightTree-》color == RED） { p-》sibling（）-》color = RED; p-》sibling（）-》rightTree-》color = BLACK; rotate_left（p-》sibling（）-》rightTree）; } } p-》sibling（）-》color = p-》parent-》color; p-》parent-》color = BLACK; if （p == p-》parent-》leftTree） { p-》sibling（）-》rightTree-》color = BLACK; rotate_left（p-》sibling（））; } else { p-》sibling（）-》leftTree-》color = BLACK; rotate_right（p-》sibling（））; } } }

void insert（Node *p， int data） { if （p-》value 》= data） { if （p-》leftTree ！= NIL） insert（p-》leftTree， data）; else { Node *tmp = new Node（）; tmp-》value = data; tmp-》leftTree = tmp-》rightTree = NIL; tmp-》parent = p; p-》leftTree = tmp; insert_case（tmp）; } } else { if （p-》rightTree ！= NIL） insert（p-》rightTree， data）; else { Node *tmp = new Node（）; tmp-》value = data; tmp-》leftTree = tmp-》rightTree = NIL; tmp-》parent = p; p-》rightTree = tmp; insert_case（tmp）; } } }

void insert_case（Node *p） { if （p-》parent == NULL） { root = p; p-》color = BLACK; return; } if （p-》parent-》color == RED） { if （p-》uncle（）-》color == RED） { p-》parent-》color = p-》uncle（）-》color = BLACK; p-》grandparent（）-》color = RED; insert_case（p-》grandparent（））; } else { if （p-》parent-》rightTree == p && p-》grandparent（）-》leftTree == p-》parent） { rotate_left（p）; rotate_right（p）; p-》color = BLACK; p-》leftTree-》color = p-》rightTree-》color = RED; } else if （p-》parent-》leftTree == p && p-》grandparent（）-》rightTree == p-》parent） { rotate_right（p）; rotate_left（p）; p-》color = BLACK; p-》leftTree-》color = p-》rightTree-》color = RED; } else if （p-》parent-》leftTree == p && p-》grandparent（）-》leftTree == p-》parent） { p-》parent-》color = BLACK; p-》grandparent（）-》color = RED; rotate_right（p-》parent）; } else if （p-》parent-》rightTree == p && p-》grandparent（）-》rightTree == p-》parent） { p-》parent-》color = BLACK; p-》grandparent（）-》color = RED; rotate_left（p-》parent）; } } } }

void DeleteTree（Node *p） { if （！p || p == NIL） { return; } DeleteTree（p-》leftTree）; DeleteTree（p-》rightTree）; delete p; }public：

bst（） { NIL = new Node（）; NIL-》color = BLACK; root = NULL; }

~bst（） { if （root） DeleteTree（root）; delete NIL; }

void inorder（） { if （root == NULL） return; inorder（root）; cout 《《 endl; }

void insert（int x） { if （root == NULL） { root = new Node（）; root-》color = BLACK; root-》leftTree = root-》rightTree = NIL; root-》value = x; } else { insert（root， x）; } }

bool delete_value（int data） { return delete_child（root， data）; }private： Node *root， *NIL;};

int main（）{ cout 《《 “---【紅黑樹】---” 《《 endl; // 創建紅黑樹 bst tree;

// 插入元素 tree.insert（2）; tree.insert（9）; tree.insert（-10）; tree.insert（0）; tree.insert（33）; tree.insert（-19）;

// 順序打印紅黑樹 cout 《《 “插入元素后的紅黑樹：” 《《 endl; tree.inorder（）;

// 刪除元素 tree.delete_value（2）;

// 順序打印紅黑樹 cout 《《 “刪除元素 2 后的紅黑樹：” 《《 endl; tree.inorder（）;

// 析構 tree.~bst（）;

getchar（）; return 0;}

紅黑樹的特征是什么？

（1）節點是紅色或黑色。

（2）根是黑色。

（3）所有葉子都是黑色（葉子是 NIL 節點）。

（4）每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）（新增節點的父節點必須相同）

（5）從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。（新增節點必須為紅）

調整

（1）變色

（2）左旋

（3）右旋

應用

關聯數組：如 STL 中的 map、set

紅黑樹、B 樹、B+ 樹的區別？

（1）紅黑樹的深度比較大，而 B 樹和 B+ 樹的深度則相對要小一些

（2）B+ 樹則將數據都保存在葉子節點，同時通過鏈表的形式將他們連接在一起。

B 樹（B-tree）、B+ 樹（B+-tree）

特點

一般化的二叉查找樹（binary search tree）

“矮胖”，內部（非葉子）節點可以擁有可變數量的子節點（數量范圍預先定義好）

應用

大部分文件系統、數據庫系統都采用B樹、B+樹作為索引結構

區別

B+樹中只有葉子節點會帶有指向記錄的指針（ROWID），而B樹則所有節點都帶有，在內部節點出現的索引項不會再出現在葉子節點中。

B+樹中所有葉子節點都是通過指針連接在一起，而B樹不會。

B樹的優點

對于在內部節點的數據，可直接得到，不必根據葉子節點來定位。

B+樹的優點

非葉子節點不會帶上 ROWID，這樣，一個塊中可以容納更多的索引項，一是可以降低樹的高度。二是一個內部節點可以定位更多的葉子節點。

葉子節點之間通過指針來連接，范圍掃描將十分簡單，而對于B樹來說，則需要在葉子節點和內部節點不停的往返移動。

B 樹、B+ 樹區別來自：differences-between-b-trees-and-b-trees、B樹和B+樹的區別

八叉樹

八叉樹圖片

八叉樹（octree），或稱八元樹，是一種用于描述三維空間（劃分空間）的樹狀數據結構。八叉樹的每個節點表示一個正方體的體積元素，每個節點有八個子節點，這八個子節點所表示的體積元素加在一起就等于父節點的體積。一般中心點作為節點的分叉中心。

用途

三維計算機圖形

最鄰近搜索

責任編輯：haq