数据结构与算法 5. 二叉树 2021-07-17 浏览量 620 暂无评论 [TOC] [课程链接](https://www.xuetangx.com/learn/THU08091000384/THU08091000384/5883586/video/9215810) [资料链接](http://dsa.cs.tsinghua.edu.cn/~deng/ds/dsacpp/) ## 5.1 树 向量和列表这种线性结构无法兼顾静态和动态操作的效率,怎么结合各自的优势? ## 5.2 一些性质 路径、深度、高度 节点的高度等于以该节点为根的子树的高度。 任一节点的深度加上高度不大于树的高度。 $depth(v)+height(v)<=height(T)$ ## 5.3 树的表示 ### 接口 节点|功能 --|-- root()|根节点 parent()|父节点 firstChild()|长子 nextSibling()|兄弟 insert(i, e)|将e作为第i个孩子插入 remove(i)|删除第i个孩子及其后代 traverse()|遍历 ### 5.3.1 双亲表示法 不利于查找孩子节点或兄弟节点。 ```cpp #define MAX_TREE_SIZE 100 typedef int TElemType; typedef struct PTNode { TElemType data; // 节点数据 int parent; // 双亲位置 } PTNode; typedef struct { PTNode nodes[MAX_TREE_SIZE]; // 节点数组 int r, n; // 根的位置和节点数 } PTree; ``` 可以添加一个长子域域来体现孩子关系,添加右兄弟域来体现兄弟关系,但仍然不方便 。 rank|data|parent| --|--|-- 0|A|-1 1|B|0 2|C|0 ### 5.3.2 孩子表示法 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706212436365.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 5.3.3 双亲孩子表示法 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706212708663.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 分析:即便这样查找双亲和孩子都比较方便,但各children的子数据集大小悬殊很大,总体规模为边的数量n-1,则每个children的子数据集的平均规模为$O(1)$,可否借助此性质简化表示方法? ### 5.3.4 孩子兄弟表示法 二叉树来了,规整性突出。 观察每个节点的不变性。 每个节点均设两个引用: - 纵:firstChild() - 横:nextSibling() ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706214803361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp typedef struct CSNode { TElemType data; struct CSNode *firstChild, *nextSibling; } CSNode, *CSTree; ``` ## 5.4 二叉树 ### 5.4.1 二叉树 高度增长缓慢,宽度增长爆炸。 因为每个节点的度最多为2,所以 - 深度为k的节点,至多$2^k$ - $h BinNodePosi(T) BinNode::insertAsLC(T const &e) { return lChild = new BinNode(e, this); } template BinNodePosi(T) BinNode::insertAsRC(T const &e) { return rChild = new BinNode(e, this); } template int BinNode::size() { // 后代总数 int s = 1; if (lChild) s += lChild->size(); if (rChild) s += rChild->size(); return s; } ``` ### 5.5.3 BinTree类 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210717164310620.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ### 5.5.4 高度更新 ```cpp #define stature(p) ( (p) ? (p)->height : -1) template int BinTree::updateHeight(BinNodePosi(T) x) { return x->height = 1 + max(stature(x->lChild), stature(x->rChild)); } // 若v更新了高度,那么它的祖先高度也会变化 template void BinTree::updateHeightAbove(BinNodePosi(T) x) { while (x) { updateHeight(x); x = x->parent; } } ``` ### 5.5.5 节点插入 ```cpp template BinNodePosi(T) BinTree::insertAsRC(BinNodePosi x, T const & e) { _size++; x->insertAsRC(e); updateHeightAbove(x); return x->rChild; } ``` ## 5.6 先序遍历 ### 5.6.1 转化策略 利用已有轮子,通过**遍历**将半线性结构转化为线性结构。 ### 5.6.2 遍历规则 根节点在次序中的位置。 先序:根-左-右 层次(广度):自上而下、先左后右 ### 5.6.3 递归实现 ```cpp template void traverse(BinNodePosi(T) x, VST & visit) { if (!x) return; visit(x->data); traverse(x->lChild, visit); traverse(x->rChild, visit); } // T(n) = O(1) + T(a) + T(n-a-1) = O(n),渐进的,可以改进 ``` **观察:** 递归处于整个程序的尾部,称作尾递归,非常容易化解为迭代的形式。 ### 5.6.4 迭代实现1 引入**栈**。 注意压栈的次序。 ```cpp template void travPre_I1(BinNodePosi(T) x, VST & visit) { Stack S; if (x) S.push(x); while (!S.empty()) { x = S.pop(); visit(x->data); if (HasRChild(*x)) S.push(x->rChild); if (HasLChild(*x)) S.push(x->lChild); } } ``` 缺点:不容易推广至中序及后序遍历算法。 ### 5.6.5 迭代实现2 **观察:** 对于任何一棵子树,都是沿着左侧链访问,再自下往上遍历右孩子 ```cpp template // 使用static修饰,不必担心与其他文件中的函数同名,和全局变量类似,不会发生冲突 static void visitAlongLeftBranch( BinNodePosi(T) x, VST & visit, Stack data); S.push(x->rChild); x = x->lChild; } } template void travPre_I2(BinNodePosi(T) x, VST & visit) { Stack void traverse(BinNodePosi(T) x, VST & visit) { if (!x) return; traverse(x->lChild, visit); visit(x->data); traverse(x->rChild, visit); } ``` ### 5.7.2 迭代 观察:当节点接到控制权后,不首先访问自己,而是将控制权转交给它的左孩子,访问完左孩子后,访问左孩子的右孩子,再访问自己。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021071720133566.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ```cpp template static void goAlongLeftBranch(BinNodePosi(T) x, Stack & S) {while (x) {S.push(x); x = x->lChild;}} template void travIn_I1(BinNodePosi(T) x, VST & visit) { Stack S; while (true) { goAlongLeftBranch(x, S); if (S.empty()) break; x = S.pop(); visit(x->data); x = x->rChild; // 当访问完一个节点及它的左孩子时,栈顶元素为该节点的祖先 } } ``` ## 5.8 后序遍历 ### 5.8.1 递归 ```cpp void traverse(BinNodePosi(T) x, typename VST) { if (!x) return; traverse(x->lChild, visit); traverse(x->rChild, visit); visit(x->data); } ``` ### 5.8.2 迭代 ```cpp template static void gotoLeftmostLeaf(Stack & S) { while (BinNodePosi(T) x = S.top()) if (HasLChild(*x)) { if (HasRChild(*x)) S.push(x->rChild); S.push(x->lChild); } else S.push(x->rChild); S.pop(); } void travPost_I(BinNodePosi(T) x, VST & visit) { Stack S; if (x) S.push(x); while (!S.empty()) { if (S.top != x->parent) gotoLeftmostLeaf(S); x = S.pop(); visit(x->data); } } ``` ### 5.8.3 表达式树 逆波兰表达式等效为后序遍历,数字为叶子,双亲为运算符,运算优先级为后序遍历次序。 ## 5.9 层次遍历 有根性:垂直 有序性:水平 自上而下、自左向右,顺序 ```cpp void BinNode::travLevel(VST & visit) { Queue Q; Q.enqueue(this); while (!Q.empty()) { BinNodePosi(T) x = Q.dequeue(); visit(x->data); if (HasLChild(*x)) Q.enqueue(x->lChild); if (HasRChild(*x)) Q.enqueue(x->rChild); } } ``` ## 完全二叉树 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021071814454218.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) # 5.10 重构 由遍历序列还原树。 先序+后序不可以,但是在真二叉树的条件下是可以的。 ```cpp #include #include typedef struct BinTree { int key; BinTree* lChild; BinTree* rChild; }BinTree; int arrayFind(int* A, int begin, int end, int key) { for (int i = begin; i < end; i++) if (key == A[i]) return i; return -1; } BinTree* reconstBinTree( int* preOrder, int pbegin, int pend, int* inOrder, int ibegin, int iend) { if (pbegin >= pend || ibegin >= iend) return NULL; BinTree* root = new BinTree; *root = { preOrder[pbegin], NULL, NULL }; int r = arrayFind(inOrder, ibegin, iend, preOrder[pbegin]); root->lChild = reconstBinTree(preOrder, pbegin + 1, r - ibegin + pbegin + 1, inOrder, ibegin, r); root->rChild = reconstBinTree(preOrder, r - ibegin + pbegin + 1, pend, inOrder, r + 1, iend); return root; } void travPre(BinTree* t) { if (!t) return; printf("data is %d\n", t->key); travPre(t->lChild); travPre(t->rChild); } int main() { std::cout << "Hello World!\n"; int PreOrder[] = { 43, 12, 8, 32, 16, 35, 78, 56, 88, 83, 121, 97 }; int InOrder[] = { 8, 12, 16, 32, 35, 43, 56, 78, 83, 88, 97, 121 }; BinTree* root = reconstBinTree(PreOrder, 0, 12, InOrder, 0, 12); travPre(root); return 0; } ``` # 5.11 Huffman树 无前缀冲突编码 叶子通路唯一=>解决编码句读问题。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210718160117670.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 如何构造编码树,使得文件最小呢?=>最优编码树 使叶子只在最后两层,否则,交换节点。 还要考虑出现的频率,带权编码:将频次高的尽可能放在高处。 使用贪婪策略: 1. 为每个字符创建一颗单节点的树,组成森林F 2. 按照出现的频率,对所有树排序 3. while (F中的树不止一棵) 取出频率最小的两棵树$T_1$和$T_2$ 将它们合并成一棵新树$T$ 这棵新树的频率为两棵子树频率之和,再插回有序森林中 赞赏 微信支付 支付宝支付