C++基礎(chǔ)語法中的二叉樹詳解

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

二叉樹

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;

// 二叉樹結(jié)構(gòu)typedef struct BiTNode{ TElemType data; struct BiTNode *lchild， *rchild;}BiTNode， *BiTree;

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

// 構(gòu)建二叉樹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;}

// 訪問結(jié)點(diǎn)Status visit（TElemType e）{ printf（“%c”， e）; return OK;}

// 對二叉樹T求葉子結(jié)點(diǎn)數(shù)目int Leaves（BiTree T）{ int l = 0， r = 0; if （NULL == T） return 0; if （NULL == T-》lchild && NULL == T-》rchild） return 1;

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

// 層次遍歷：dep是個(gè)全局變量，高度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是個(gè)全局變量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（“是葉子結(jié)點(diǎn)”）; num++; } else printf（“不是葉子結(jié)點(diǎn)”）; 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（“葉子結(jié)點(diǎn)是 %d

”， num）;

printf（“葉子結(jié)點(diǎn)是 %d

”， Leaves（T））;

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

printf（“高度是 %d

”， depTraverse（T））;

getchar（）; return 0;}

性質(zhì)

（1）非空二叉樹第 i 層最多 2（i-1） 個(gè)結(jié)點(diǎn) （i 》= 1）

（2）深度為 k 的二叉樹最多 2k - 1 個(gè)結(jié)點(diǎn) （k 》= 1）

（3）度為 0 的結(jié)點(diǎn)數(shù)為 n0，度為 2 的結(jié)點(diǎn)數(shù)為 n2，則 n0 = n2 + 1

（4）有 n 個(gè)結(jié)點(diǎn)的完全二叉樹深度 k = ? log2（n） ? + 1

（5）對于含 n 個(gè)結(jié)點(diǎn)的完全二叉樹中編號為 i （1 《= i 《= n） 的結(jié)點(diǎn)

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

b.若 2i 》 n，則 i 結(jié)點(diǎn)沒有左孩子，否則孩子編號為 2i

c.若 2i + 1 》 n，則 i 結(jié)點(diǎn)沒有右孩子，否則孩子編號為 2i + 1

存儲結(jié)構(gòu)

二叉樹數(shù)據(jù)結(jié)構(gòu)

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

順序存儲

二叉樹順序存儲圖片

鏈?zhǔn)酱?/p>

二叉樹鏈?zhǔn)酱鎯D片

遍歷方式

a.先序遍歷

b.中序遍歷

c.后續(xù)遍歷

d.層次遍歷

分類

（1）滿二叉樹

（2）完全二叉樹（堆）

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

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

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

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

（5）最小失衡樹：平衡二叉樹插入新結(jié)點(diǎn)導(dǎo)致失衡的子樹：調(diào)整：

LL型：根的左孩子右旋

RR型：根的右孩子左旋

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

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

其他樹及森林

1、樹的存儲結(jié)構(gòu)

（1）雙親表示法

（2）雙親孩子表示法

（3）孩子兄弟表示法

并查集

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

2、平衡二叉樹（AVL樹）

性質(zhì)

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

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

（3）最小二叉平衡樹的節(jié)點(diǎn)的公式：F（n）=F（n-1）+F（n-2）+1 （1 是根節(jié)點(diǎn)，F(xiàn)（n-1） 是左子樹的節(jié)點(diǎn)數(shù)量，F(xiàn)（n-2） 是右子樹的節(jié)點(diǎn)數(shù)量）

平衡二叉樹圖片

最小失衡樹

平衡二叉樹插入新結(jié)點(diǎn)導(dǎo)致失衡的子樹

調(diào)整：

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; // 創(chuàng)建紅黑樹 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（）;

// 析構(gòu) tree.~bst（）;

getchar（）; return 0;}

紅黑樹的特征是什么？

（1）節(jié)點(diǎn)是紅色或黑色。

（2）根是黑色。

（3）所有葉子都是黑色（葉子是 NIL 節(jié)點(diǎn)）。

（4）每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）（新增節(jié)點(diǎn)的父節(jié)點(diǎn)必須相同）

（5）從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。（新增節(jié)點(diǎn)必須為紅）

調(diào)整

（1）變色

（2）左旋

（3）右旋

應(yīng)用

關(guān)聯(lián)數(shù)組：如 STL 中的 map、set

紅黑樹、B 樹、B+ 樹的區(qū)別？

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

（2）B+ 樹則將數(shù)據(jù)都保存在葉子節(jié)點(diǎn)，同時(shí)通過鏈表的形式將他們連接在一起。

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

特點(diǎn)

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

“矮胖”，內(nèi)部（非葉子）節(jié)點(diǎn)可以擁有可變數(shù)量的子節(jié)點(diǎn)（數(shù)量范圍預(yù)先定義好）

應(yīng)用

大部分文件系統(tǒng)、數(shù)據(jù)庫系統(tǒng)都采用B樹、B+樹作為索引結(jié)構(gòu)

區(qū)別

B+樹中只有葉子節(jié)點(diǎn)會(huì)帶有指向記錄的指針（ROWID），而B樹則所有節(jié)點(diǎn)都帶有，在內(nèi)部節(jié)點(diǎn)出現(xiàn)的索引項(xiàng)不會(huì)再出現(xiàn)在葉子節(jié)點(diǎn)中。

B+樹中所有葉子節(jié)點(diǎn)都是通過指針連接在一起，而B樹不會(huì)。

B樹的優(yōu)點(diǎn)

對于在內(nèi)部節(jié)點(diǎn)的數(shù)據(jù)，可直接得到，不必根據(jù)葉子節(jié)點(diǎn)來定位。

B+樹的優(yōu)點(diǎn)

非葉子節(jié)點(diǎn)不會(huì)帶上 ROWID，這樣，一個(gè)塊中可以容納更多的索引項(xiàng)，一是可以降低樹的高度。二是一個(gè)內(nèi)部節(jié)點(diǎn)可以定位更多的葉子節(jié)點(diǎn)。

葉子節(jié)點(diǎn)之間通過指針來連接，范圍掃描將十分簡單，而對于B樹來說，則需要在葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)不停的往返移動(dòng)。

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

八叉樹

八叉樹圖片

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

用途

三維計(jì)算機(jī)圖形

最鄰近搜索

責(zé)任編輯：haq