首页 > 编程札记 > 编程

【数据结构】二叉树复习

阅读：评论：0

【数据结构】二叉树复习

二叉树

- 0、二叉树相关概念及性质
- 一、二叉树链式存储
- 二、二叉树的遍历
- - 1. 先序遍历
  - 2. 中序遍历
  - 3. 后序遍历
  - 4. 层次遍历
- 二、二叉树基础操作
- - 1. 创建二叉树
  - 2. 查找二叉树节点
  - 3. 计算二叉树深度
  - 4. 销毁二叉树
- 三、二叉树的应用
- - 1. 判断一棵树是否为完全二叉树
  - 2. 霍夫曼(Huffman)树
  - - 2.1 定义
    - 2.2 背景
    - 2.3 霍夫曼树的构造
    - 2.4 霍夫曼编码
    - 2.5 霍夫曼树和霍夫曼编码算法实现
    - 2.6 书上的另一种结构体和算法
- 四、二叉树力扣练习

0、二叉树相关概念及性质

术语：

满二叉树：所有分支结点的度均为2，并且所有叶子节点都集中出现在二叉树的最底层。
完全二叉树：二叉树中度小于2的结点只能出现在数的最下面两层，且最底层的叶结点都依次排列在该层最左边的位置。

性质：

二叉树的第i层上，至多有2^(i-1)个节点(i≥1)。(等比数列)
深度为k的二叉树至多有2^k-1个节点(k≥1)。(等比数列求和)
任意二叉树，若叶结点个数为n0，度为2的结点的个数为n2，则n0=n2+1。(结点数为n的树一定包含n-1个分支)
具有n个结点的完全二叉树的深度为向下取整(logn)+1。
对于包含n个结点的完全二叉树，当i>1时，其双亲结点为向下取整(i/2)；

一、二叉树链式存储

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

二叉树的大部分操作都是递归

二、二叉树的遍历

1. 先序遍历

根左右

void PreOrderTraverse(BiTNode *T){if(!T){cout << T->data << ' ';if(T->lchild)   PreOrderTraverse(T->lchild);if(T->rchild)   PreOrderTraverse(T->rchild);}
}

2. 中序遍历

左根右

void InOrderTraverse(BiTNode *T){if(T){if(T->lchild)   InOrderTraverse(T->lchild);cout << T->data << ' ';if(T->rchild)   InOrderTraverse(T->rchild);}
}

3. 后序遍历

左右根

void PostOrderTraverse(BiTNode *T){if(T){if(T->lchild)   PostOrderTraverse(T->lchild);if(T->rchild)   PostOrderTraverse(T->rchild);cout << T->data << ' ';}
}

4. 层次遍历

一层一层输出(c++队列操作)

void LevelOrserTraverse(BiTNode *T){BiTNode *cur;queue<BiTNode*> qu;qu.push(T);while(!qu.empty()){ // 队列不为空时cur = qu.front();qu.pop(); // 获得并删除队首元素cout << cur->data << ' ';if(cur->lchild) qu.push(cur->lchild);if(cur->rchild) qu.push(cur->rchild);}
}

二、二叉树基础操作

1. 创建二叉树

c++ new的用法
注意：在建树时，要按照完全二叉树方法输入，无左子树或右子树的用空格代替。
eg. 如下树：创建树的输入为(%代表空格) ABD%G%%%CE%%F%%

注意：cin无法读入空格！！！！

// 基于先序遍历创建二叉树
/*
void CreatePreBiTree(BiTNode *T){错误方式，相当于传递进来的指针当做了形参，实际上并不会改变指针的值。下面才是正确的传递方式，将指针作为引用来传入，建树是可以修改指针所指向的值
*/
void CreatePreBiTree(BiTree &T){TElemType data;// cin >> data; // wrong. cin无法读入空格，遇到空格即读取结束data = getchar(); // 将cin改成如下读取方式，或使用scanfif(data == ' ') T = NULL; // 空字符else{T = new BiTNode;T->data = data;CreatePreBiTree(T->lchild); // 先建立左子树CreatePreBiTree(T->rchild); // 再建立右子树}
}

函数声明时的误区：参考blog
只有先序遍历方便建树。

2. 查找二叉树节点

当查找到值相等的节点时，返回该节点。

深度优先(先序遍历)

// 深度优先遍历查找目标结点(先序遍历)
BiTNode* FindNode(BiTNode *T, TElemType x){BiTNode *p = NULL; // 用来暂存返回值if(T == NULL)   return NULL; // 找到最后没找到else if(T->data == x)   return T; // 找到了else{p = FindNode(T->lchild, x); // 找左子树if(p == NULL)return FindNode(T->rchild, x); // 左子树没找到就找右子树elsereturn p;}
}

广度优先

// 广度优先遍历查找目标节点(层次遍历)
BiTNode *BFindNode(BiTNode *T, TElemType x){queue<BiTNode*> qu;BiTNode *cur;qu.push(T);while(!qu.empty()){cur = qu.front();qu.pop();if(cur->data == x)return cur;if(cur->lchild) qu.push(cur->lchild);if(cur->rchild) qu.push(cur->rchild);}
}

3. 计算二叉树深度

// 基于后序遍历计算二叉树的高度
int BiTreeDepth(BiTNode *T){int left_depth = 0 , right_depth = 0;if(T == NULL)   return 0; // 起始条件left_depth = BiTreeDepth(T->lchild);right_depth = BiTreeDepth(T->rchild);// 总是选择左右子树中最高的深度并加上自身(+1)return left_depth>right_depth ? left_depth+1 : right_depth+1;
}

4. 销毁二叉树

基于后序遍历销毁，必须要从下往上，从叶往根销毁。

// 基于后序遍历销毁二叉树
void DestoryBiTree(BiTNode *T){if(T){DestoryBiTree(T->lchild);DestoryBiTree(T->rchild);free(T); // 左右子树都为空 就是叶子节点 释放}
}

三、二叉树的应用

1. 判断一棵树是否为完全二叉树

思路：根据定义，完全二叉树应满足如下条件：

叶结点只能出现在树的最后两层
度为1的结点最多只能有一个，且只能是左孩子
若分别用n0、n1、n2表示度为0、1、2的节点个数，则只可能有一下三种情况：① n1=n2=0，n0=1(只有一个根节点情况)；② n2=0，n0=n1=1(根节点+左孩子情况)；③ n2≠0，n1=1/0，n0≠0。
从层次遍历的角度来说，会先遍历所有度为2的结点，再遍历度为1的结点，最后遍历所有度为0的叶子节点。如果违反了这个顺序，则说明这不是一颗完全二叉树。

一棵完全二叉树要同时满足以上所有条件，在一次层次遍历中判断。
计算节点的度：if (T->lchild && T->rchild)

// 基于层次遍历，判断一棵树是否是完全二叉树
bool IsCompleteBiTree(BiTNode *T){queue<BiTNode*> qu;BiTNode *cur;bool degree_notmore_one = false; // 用来记录是否访问过度不大于1的节点qu.push(T);while(!qu.empty()){cur = qu.front();qu.pop();if(!cur->lchild && !cur->rchild) // 左右子树都不存在，即叶子节点degree_notmore_one = true; // 度为0已经访问过else if(!cur->lchild && cur->rchild) // 只有左子树没有右子树，不符合完全二叉树条件return false;else if(cur->lchild && !cur->rchild){ // 只有左子树没有右子树// 若已经访问过度不大于1的节点，则不是完全二叉树。因为是层次遍历。if(degree_notmore_one)return false;degree_notmore_one = true; // 度=1qu.push(cur->lchild);}else{ // 左右子树都存在if(degree_notmore_one)return false;qu.push(cur->lchild);qu.push(cur->rchild);}}return true; // 以上情况均未出现
}

2. 霍夫曼(Huffman)树

2.1 定义

霍夫曼树：又叫最优树二叉树，是一种带权路径长度(WPL)最小的二叉树。

带权路径长度WPL：根节点到叶结点之间的路径长度与该叶结点的权值的乘积叫做该叶结点的带权路径长度。

eg. 上图WPL = 8×3 + 7×2 + 6×2

2.2 背景

在解决某些问题时，可以利用霍夫曼树得到最佳算法。如现在有五个有序数组ABCDE，分别包含200、40、160、360、100个元素，现要将这五个数组进行归并，最终得到一个整体有序的数组，问：如何归并达到最高效率？
根据线性表知识知：若两个有序数组X和Y，包含数据元素分别为m和n，则将X和Y进行归并的时间复杂度为O(m+n)，最坏情况下，需要m+n-1次比较。
将ABCDE进行归并有多种情况，以下为两种可能情况(按照最坏情况下的比较次数计算)：

则WPLa = 200×3 + 40×3 + 160×2 + 360×2 + 100×2 = 1960
WPLb = 40×4 + 100×4 + 160×3 + 200×2 + 360×1 = 1800
对比之下，b的效率更高，因此如何合并至关重要。

2.3 霍夫曼树的构造

如何构造霍夫曼树 = 给定n个权值，如何构造包含n个叶结点的二叉树使得WPL最小？
① 从n个节点中选择最小的两个节点进行合并，记他俩的父节点为S1，S1的权值是二者之和。
② 从剩下的n-2个节点加上S1中选择最小的两个节点进行合并，计他们的父节点为S2，S2权值是二者之和。
③ 重复步骤②，直至合并最后两个节点。
则上图中所建成Huffman树的过程如下：

2.4 霍夫曼编码

霍夫曼树可以用于文件压缩。
如果字符集的大小是M，则这个字符集中每个符号的编码就需要向上取整(logM) 位bit。人们希望提出一种有效的编码机制来降低文件所占用的总比特数。一种简单的策略是让编码长度随着字符使用频率变化，保证经常出现的符号的编码尽可能的短。举例说明：
设一个文件只包含a、e、i、o、u五个字符，则每个字符需要[log5] = 3位，其中出现频率等信息如下：

字符	标准编码	出现频次	总位数
a	000	10	30
e	001	15	45
i	010	12	36
o	011	3	9
u	100	4	12
总计			132

用霍夫曼树对其重新编码(不再沿用原来的标准编码)：五个叶结点及其权值：a:10; e:15; i:12; o:3; u:4。编码越短意味着分支越少，即可使用霍夫曼树。
首先选择3、4进行结合，再选择10与其父节点结合，再选择12与其父节点结合，在选择15与其父节点结合。左分支代表0，右分支代表1。(反过来也可以)
最终构造的Huffman树及各字符编码如下：
编码：叶->根；解码：根->叶

霍夫曼编码的实质就是让使用频率高的字符采用的编码越短。但实际发现，霍夫曼编码并不唯一(合并时并未规定哪个是左子树哪个是右子树、左右分支进行01规定时也可以任意)

2.5 霍夫曼树和霍夫曼编码算法实现

结构体继续沿用二叉树的结构体

typedef struct BiTNode{int data;BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

霍夫曼树建立算法

#include<utility> // pair
// 构建Huffman树
void HufTree(int n, int *weight, BiTree &HT){/*n：叶结点数量weight[]：叶结点权值HT：构建的Huffman树*/if(n <= 1)  return; // 只有一个节点，直接返回// 对所有权值进行排序QuickSort(n, weight);// for(int i=0; i<n; i++)//     cout << weight[i] << ' ';// cout << endl;// 构造键值对容器vector< pair<int, BiTNode*> > weight_node; // 存储节点权值，以及是否形成了树for(int i=0; i<n; i++){pair<int, BiTNode*> p(weight[i], NULL);weight_node.push_back(p);}// 构建Huffman树pair<int, BiTNode*> lchild, rchild, parent;vector< pair<int, BiTNode*> >::iterator it;while(weight_node.size() > 1){// 获取权值最小的两个节点并从vector中删除lchild = weight_node.back();weight_node.pop_back();rchild = weight_node.back();weight_node.pop_back();// 构建其父节点parent.second = new BiTNode;parent.first = lchild.first + rchild.first; // 计算父节点权值parent.second->data = parent.first;if(lchild.second == NULL){ // 是叶子节点，之前未建树lchild.second = new BiTNode;lchild.second->lchild = lchild.second->rchild = NULL;lchild.second->data = lchild.first;}parent.second->lchild = lchild.second; // 指向左孩子if(rchild.second == NULL){ // 是叶子节点，之前未建树rchild.second = new BiTNode;rchild.second->lchild = rchild.second->rchild = NULL;rchild.second->data = rchild.first;}parent.second->rchild = rchild.second; // 指向右孩子// 插入存储父节点for(it=d()-1; it>=weight_node.begin(); it--){if((*it).first >= parent.first){weight_node.insert(it+1, parent);break;}}if(it < weight_node.begin())weight_node.insert(weight_node.begin(), parent);}PreOrderTraverse(weight_node[0].second); // 输出检验HT = weight_node[0].second; // Huffman树构建完成
}

同样在函数声明的形参中注意使用BiTree &HT而不是BiTNode *T。
以上算法用到了快速排序。

// 3. 
int Partition(int *a, int left, int right){int index = left, temp = a[left];while(left < right){while(left < right && a[right] <= temp) right--;a[left] = a[right];while(left < right && a[left] >= temp)  left++;a[right] = a[left];}a[left] = temp;return left;
}
// 2. 
void QSort(int *a, int left, int right){if(left < right){int part = Partition(a, left, right);QSort(a, left, part);QSort(a, part+1, right);}
}// 1. 从大到小排序
void QuickSort(int n, int *a){QSort(a, 0, n-1);
}

霍夫曼编码

根据建立好的Huffman树，规定左子树0右子树1(或相反)，来从根->叶对叶结点进行编码。map键值对容器的使用

// 2. 利用先序遍历的递归获得
void GetHufCode(BiTNode *T, map<int, string> &code, string str){if(!T->lchild && !T->rchild){ // 遍历到了叶子节点code[T->data] = str;}if(T->lchild){str += '0';GetHufCode(T->lchild, code, str);// 注意：string没有减号运算操作，可以通过这种方法来删除最后一个字符ase(str.length() - 1); }if(T->rchild){str += '1';GetHufCode(T->rchild, code, str);ase(str.length() - 1);}
}
// 1. 获取哈夫曼编码
void HufCode(BiTNode *T, map<int, string> &huf_code){string temp = "";// 利用先序遍历GetHufCode(T, huf_code, temp);// 输出霍夫曼编码map<int, string>::iterator it;for(it = huf_code.begin(); it != d(); it++)cout << it->first << " : t" << it->second << endl;
}

测试样例

int main(){int weight[5] = {10, 15, 12, 3, 4};// 建立霍夫曼树BiTree HT;HufTree(5, weight, HT);// 获取霍夫曼编码map<int, string> huf_code;HufCode(HT, huf_code);return 0;
}

输出为：第一行的输出是霍夫曼树的先序遍历

实际上所建立的Huffman树为：

2.6 书上的另一种结构体和算法

上面2.5是我自己想的，这一part是书上的官方的。

typedef struct{int weight;int parent, lchild, rchild; // 数组下标
}HTNode, *HufTree;

注意下标从1开始。

weight	parent	lchild	rchild
10	7	0	0
15	8	0	0
12	8	0	0
3	6	0	0
4	6	0	0
7	7	4	5
17	9	6	1
27	9	2	3
44	0	7	8

void BookHufCode(int *weight, int n, HuffTree &HT, map<int, string> &huf_code){/*n：叶结点数量weight[]：叶结点权值HT：构建的Huffman树huf_code：存放Huffman编码*/if(n <= 1)  return; // 只有一个节点// 二叉树的性质：若叶结点个数为n0，则n0-1=n2，又∵n1=0，即没有度为1的节点，所以n总=n0+n2=2n0-1。// 又∵0号位置不存，所以一共申请2*n个HTNode (从下标1开始存数据)HT = new HTNode[2*n];// init HuffTreefor(int i=1; i<=n; i++){HT[i].lchild = HT[i].rchild = HT[i].parent = 0;HT[i].weight = weight[i-1];}// 创建Huffman树for(int i=n+1; i<2*n; i++){// 在HT数组中，选取1~i-1区间中parent=0 && weight最小的两个节点s1和s2(s1、s2表示节点在HT数组中的下标)int s1, s2;SelectTwoSmall(HT, i-1, s1, s2);HT[i].weight = HT[s1].weight + HT[s2].weight;HT[i].lchild = s1;HT[i].rchild = s2;HT[i].parent = 0;HT[s1].parent = HT[s2].parent = i;}// 创建Huffman编码// 逆向从叶->根编码，使用insert逐个往头部插入for(int i=1; i<=n; i++){int child = i, parent = HT[i].parent;string code = "";while(parent != 0){ // 没到根节点// 左孩子0右孩子1if(HT[parent].lchild == child)code.insert(0, "0");elsecode.insert(0, "1");child = parent;parent = HT[child].parent;}huf_code.insert(pair<int, string>(HT[i].weight, code)); // 插入编码}
}

用到一个函数

// 选取parent=0 && weight最小的两个节点下标x和y
void SelectTwoSmall(HuffTree HT, int n, int &x, int &y){// 永远保持min1<min2，min1下标对应x，min2下标对应yint min1 = 65535, min2 = 65535;y = x = 0;for(int i=1; i<=n; i++){if(HT[i].parent == 0){if(HT[i].weight < min1){min2 = min1; y = x;min1 = HT[i].weight; x = i;} else if(HT[i].weight > min1 && HT[i].weight < min2){min2 = HT[i].weight;y = i;}}}
}