published: true
date: 2022-1-22
tags: ‘算法与数据结构’ 树
基本概念 树的定义(在任意非空树中)本章介绍树的相关知识,包含数据结构:二叉树、哈夫曼树;以及二叉树的三种遍历、计算叶子数、深度、中缀表达式等,使用哈夫曼树生成最优前缀码。
可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
必有一个称为根的结点。当n>1(结点树)时,其余结点可分为m(m>0)个互不相交的有限集T1,T2······T_m。其中每一个集合本身又是一颗树,称为根的子树。 特点
非空树中至少有一个根结点。树中各子树是互不相交的集合。任意结点都可以有零个或多个直接后继结点,但至多只有一个直接前趋结点。叶结点无后继,根结点无前趋。 关键词
结点:树中的元素,包括数据项及若干指向其子树的分支。结点的度:结点拥有的子树数。树的度:一个树中最大的结点的度。叶子结点:度为0的结点,也叫终端结点。分支结点:度不为0的结点,也叫非终端结点。内部结点:除根结点外的分支结点。孩子结点:结点子树的根,称为该结点的孩子。双亲结点:孩子结点的上层结点,称为该结点的双亲。兄弟结点:同一双亲的孩子之间互称为兄弟。堂兄弟结点:其双亲在同一层的结点互称为堂兄弟。树的层次:从根结点算起,根为第一层,它的孩子为第二层······树的深度:树中结点的最大层次数。有序树和无序树:如果将树中结点的各子树看成从左至右有次序的(即不能互换),则称该树为有序树,否则称无序树。有序树最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子。森林:m(m>=0)颗互不相交的树的集合。祖先:结点的祖先是从根到该结点所经分支上的所有结点。子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。 基本 *** 作
初始化、求根、求双亲、求孩子结点、求右兄弟、建树、插入子树 *** 作、删除子树 *** 作、遍历 *** 作、清除 *** 作。
应用场景决策树、二叉排序树、句法依存树······
二叉树 基础概念每个结点至多有两棵子树。不存在度大于2的结点。子树有左右之分,次序不能任意颠倒。二叉树不是一种特殊的树,只是一种特殊的树形结构。 满二叉树
深度为k的满二叉树,有2^k - 1个结点。
2 0 + … … + 2 k − 1 = 2 k − 1 2^0 + ……+2^{k-1} = 2^k-1 20+……+2k−1=2k−1
2^k - 1,是深度为k的二叉树所具有的最大结点个数。每层上的结点数都达到最大值。只有度为0和度为2的结点。每个结点均有两棵高度相同的子树。叶子结点都在树的最下一层。
判断一个树是否是完全二叉树:
思路:从上到下,右到左扫描,第一个度小于2的之后的每一个结点都必须是叶子结点。
foreach node in one_layer begin: if node有两个孩子,则continue; if node无左孩子但有右孩子,则return False; if (node有一个左孩子)||(node是叶子),则: foreachafnode in NODES(node之后的结点集) if afnode不是叶子,则return False; endforeach return Ture;完全二叉树
对比满二叉树,次序是一样的,最后一层只缺少右边的若干结点。叶子结点只可能在最大的两层上出现。对任意结点,若其右子树的深度为L,则其左子树的深度必为L或L+1。除最后一层外,每一层的结点数均达到最大值。 性质
二叉树的第i层至多有2^{i-1}个结点(i>=1)。深度为k的二叉树,至多有2^k - 1个结点。对任意二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2 + 1。具有n个结点的完全二叉树的深度为[log_2 n ] + 1。对于有n个结点的完全二叉树的结点按层序编号(从第一层到最后一层,每层从左到右),则对任一结点(1<= i <=n),有:
如果i=1,则结点i是根结点,无双亲,否则,其双亲结点是[i/2]如果2i>n,则结点i无左孩子(结点i为叶子),否则其左孩子是节点2i。如果2i + 1>n,则结点i无右孩子,否则右左孩子是节点2i。 存储 顺序存储
将任意二叉树修补为完全二叉树,用顺序表对元素进行存储,原二叉树空缺的结点,其顺序表相应单元置空:
链式存储结点有三个域:数据域、指向左、右子树的指针域:
struct btnode{ char c; btnode* lchild; btnode* rchild; btnode(char c): c(c),lchild(NULL),rchild(NULL){ } };基本 *** 作 创建二叉树:
思路:
按先序序列建立二叉链表。abd···ef··g··(要求会画图)
建立根结点先序建立左子树先序建立右子树
int x = 0; // char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',}; btnode* creatTree(char *str){ cout << x << "," << str[x] << "; "; if(x >= 23 || str[x] == '#'){ x += 1; return NULL; } btnode* cur_node = new btnode(str[x]);//建立当前树的根接节点 x += 1; cur_node->lchild = creatTree(str); cur_node->rchild = creatTree(str); return cur_node; }计算叶子数:
若树空,return 0;若树t只有唯一的根,则return 1否则
求该二叉树的左子树的叶子数m。求该二叉树的右子树的叶子数n。return m+n;
int countLeaf(btnode *T){ if(T == NULL){ return 0; } if(T->lchild == NULL && T->rchild == NULL){ return 1; } int m = countLeaf(T->lchild); int n = countLeaf(T->rchild); return m+n; }计算树的深度:
若树为空,return 0;否则
计算左子树的高度m计算右子树的高度nreturn(m>n)?m+1:n+1
int high(btnode *T){ if(T == NULL){ return 0; }else{ int m = high(T->lchild) + 1; int n = high(T->rchild) + 1; if(m > n){ return m; }else{ return n; } } }带括号的中缀表达式:
//仿照中序遍历,只是区分左右子树 void infixexpression(btnode *T){ if(T != NULL){ if(T->lchild != NULL)cout << "("; infixexpression(T->lchild); cout << T->c; infixexpression(T->rchild); if(T->rchild != NULL)cout << ")"; } }遍历 先序遍历(根左右):
void preorder(btnode *T){ if(T != NULL){ cout << T->c << ", "; preorder(T->lchild); preorder(T->rchild); }else{ cout << "#, ";//输出占位符,保持结构 } }中序遍历(左根右):
void inorder(btnode *T){ if(T != NULL){ inorder(T->lchild); cout << T->c << ", "; inorder(T->rchild); }else{ cout << "#, ";//输出占位符,保持结构 } }后序遍历(左右根):
void postorder(btnode *T){ if(T != NULL){ postorder(T->lchild); postorder(T->rchild); cout << T->c << ", "; }else{ cout << "#, ";//输出占位符,保持结构 } }主函数:
int main(){ cout << "Create Tree" << endl; char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',}; btnode* bt_tree = creatTree(str); //遍历 cout << endl << endl << "preorder,inorder,postorder:" << endl; preorder(bt_tree); cout << endl; inorder(bt_tree); cout << endl; postorder(bt_tree); //计算叶子数 cout << endl << endl; int x = countLeaf(bt_tree); cout << "coutLeaf:" << x << endl; //计算树深 cout << endl << "high=" << high(bt_tree) << endl; //中缀表达式 cout << endl << "infixexpression:" << endl; infixexpression(bt_tree); return 0; }输出:
Create Tree 0,-; 1,+; 2,a; 3,#; 4,#; 5,*; 6,b; 7,#; 8,#; 9,-; 10,c; 11,#; 12,#; 13,d; 14,#; 15,#; 16,/; 17,e; 18,#; 19,#; 20,f; 21,#; 22,#; preorder,inorder,postorder: -, +, a, #, #, *, b, #, #, -, c, #, #, d, #, #, /, e, #, #, f, #, #, #, a, #, +, #, b, #, *, #, c, #, -, #, d, #, -, #, e, #, /, #, f, #, #, #, a, #, #, b, #, #, c, #, #, d, -, *, +, #, #, e, #, #, f, /, -, coutLeaf:6 high=5 infixexpression: ((a+(b*(c-d)))-(e/f))层序遍历:
思路:利用队列
//层序遍历二叉树 void printBinTree(btnode* root) { queue递归算法的非递归描述q; btnode* b; //树为空 if (root == NULL) { cout << "treeNode is empty!" < c << ", "; //打印对头的数据 //对头的左孩子存在就入队 if (b->lchild) { q.push(b->lchild); } //对头的右孩子存在就入队 if (b->rchild) { q.push(b->rchild); } } } int main(){ cout << "Create Tree" << endl; char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',}; btnode* bt_tree = creatTree(str); cout << endl; printBinTree(bt_tree); return 0; }
//中序遍历为例 void nonRecInorder(btnode *T){ btnode * p = T; vectorst; if(T != NULL){ st.push_back(p); }else{ return; } p = p->lchild; while(1){ while(p != NULL){//右 st.push_back(p);//同时压栈 p = p->lchild; } if(!st.empty()){ p = st.back(); st.pop_back(); cout << p->c << ", ";//中 p = p->rchild;//左 }else{ return; } } } int main(){ cout << "Create Tree" << endl; char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',}; btnode* bt_tree = creatTree(str); cout << endl; nonRecInorder(bt_tree); return 0; }
//计算叶子数的非递归描述 int nonRecCountLeaf(btnode *T){ if(T == NULL) return 0; int num = 0; vector树 树的表示st; while (T != NULL || !st.empty()) { while (T != NULL) { cout << "node:" << T->c << endl;//print st.push_back(T); T = T->lchild; } if (!st.empty()) { T = st.back();//从空那边回来 st.pop_back(); if(T->lchild == NULL && T->rchild == NULL)//判断是否为叶子节点 num++; T = T -> rchild; } } return num; } int main(){ cout << "Create Tree" << endl; char str[] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c', '#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#',}; btnode* bt_tree = creatTree(str); cout << endl; int x = nonRecCountLeaf(bt_tree); cout << endl << "num:" << x; return 0; }
双亲表示法:
孩子链法:
转换孩子兄弟表示法:
将树转换为二叉树:
加线:在兄弟之间加一连线。抹线:对每个结点,除其第一孩子外,去除其与其余孩子之间的关系。旋转:以树的根结点为轴心,将整棵树顺时针转45`。树转换为二叉树其右子树一定为空。
二叉树转换为树:
加线:若p结点是双亲结点的左孩子则将p的右孩子,右孩子的右孩子,······沿分支找到的所有右孩子,都与p的双亲连起来。抹线:抹掉原二叉树中双亲与右孩子之间的连线。调整:将结点按层次排列,形成树结构。
森林转换为二叉树:将各棵树分别转换成二叉树,将每棵树的根结点用线相连。
哈夫曼树 基础概念
路径:若树中存在某个结点序列k_1,k_2······k_j。满足k_i是k_{i+1}的双亲,则该结点序列是树上的一条路径。
树的路径长度是指树根到树中每一个结点的路径之和。
完全二叉树的路径长度最短。
结点的权:给树的结点赋以一定意义的数值,称为结点的全权。
结点的带权路径长度:从树根到某个结点的路径长度与该结点的权的积。
树的带权路径长度:树中所有叶子结点的带权路径长度之和。
哈夫曼树的定义:
由n个带权叶子结点构成的二叉树具有不同形态。其中WPL最小的二叉树又叫做最优二叉树,或最佳判定树。
w p l = ∑ k = 1 n w k l k wpl = sum_{k=1}^{n}w_kl_k wpl=k=1∑nwklk
其中,w_k是第i个叶子结点的权值,l_k是根到第i个叶子结点的路径长度。
创建哈夫曼树与哈夫曼编码创建:
初始化n个权值,到forest的前n个单元,作为forest中n个孤立的根结点。
将前n个单元的双亲、左、右孩子指针均置为0。
不妨将下标为0的单元留空。
foreach pos in(n+1~2n-1) begin 进行1次合并,从froest中删除两棵树,生成1棵新树: 从forest的根结点中,选取根结点权值最小、次小的两棵树p1和p2。 合并forest[p1]和forest[p2],生成新根结点forest[pos] 置forest[pos].w = forest[p1].w + forest[p2].w 置forest[p1]和forest[p2]分别为forest[pos]的左右孩子。 置forest[p1]和forest[p2]的双亲为forest[pos] endforeach return
**前缀码:**任一字符的编码,不能是其他字符的前缀。
将值作为结点的值,将权重作为边。构造最优二叉树将树中每个结点的左分支置为0,右分支置为1。从根到叶子结点的一个标号序列,就是该叶子结点的编码。
原因:没有一片树叶是其他树叶的祖先,所以叶子结点编码不可能是其他叶子结点编码的前缀。
数据处理data = [] with open("huffmandata.txt", "r", encoding="utf-8") as f: data = f.read() data[1]
'b'
nums = [0,0,0,0,0] for i in data: if(i == 'a'): nums[0] += 1 if(i == 'b'): nums[1] += 1 if(i == 'c'): nums[2] += 1 if(i == 'd'): nums[3] += 1 if(i == 'e'): nums[4] += 1 nums
[398964, 400200, 399318, 400002, 401516]
weight = [0, 0, 0, 0, 0] for i in range(5): weight[i] = nums[i]/len(data) weight
[0.199482, 0.2001, 0.199659, 0.200001, 0.200758]
op = [0, 0.199482, 0.2001, 0.199659, 0.200001, 0.200758, 0, 0, 0, 0, ] mem = [1,1,1,1,1,1,1,1,1,1,] len(mem)
10生成哈夫曼树
op = [0.199482, 0.2001, 0.199659, 0.200001, 0.200758, 0, 0, 0, 0,] mem = [1,1,1,1,1,1,1,1,1,] # 标记是否用过 temp = [] # 存储逆序前的哈夫曼树 weizhi = [] n = len(weight) c = n for i in range(n, 2*n-1): min_1 = 1 min_1_index = 0 min_2 = 1 min_2_index = 0 for j in range(0, c): if(op[j]*mem[j] < min_1): min_1 = op[j] min_1_index = j for j in range(0, c): if((op[j]*mem[j] < min_2) & (op[j] != min_1)): min_2 = op[j] min_2_index = j # 标记 mem[min_1_index] = 20 # 这里只要是一个较大的数就行 mem[min_2_index] = 20 temp.append(op[min_1_index]) temp.append(op[min_2_index]) print(min_1_index,min_2_index) if(min_1_index < n): weizhi.append(min_1_index) if(min_2_index < n): weizhi.append(min_2_index) op[i] = op[min_1_index] + op[min_2_index] c += 1 # print(op) temp.append(1) # 逆序 huffmantree = [0,] for i in range(len(op)-1,-1,-1): huffmantree.append(temp[i]) print(weizhi) huffmantree
0 2 3 1 4 5 6 7 [0, 2, 3, 1, 4] [0, 1, 0.599899, 0.40010100000000004, 0.39914099999999997, 0.200758, 0.2001, 0.200001, 0.199659, 0.199482]生成最优前缀码
l = len(huffmantree)
# 生成的列表方便逆序生成正确的编码 codes = [] for i in range(l-1, int(l/2)-1, -1): # print(i) codes.append(-1) while(int(i/2) != 0): if(i%2 == 1): codes.append(1) else: codes.append(0) i = int(i/2) codes
[-1, 1, 0, 0, -1, 0, 0, 0, -1, 1, 1, -1, 0, 1, -1, 1, 0]
# 找到对应的位置 element_src = ['a', 'b', 'c', 'd', 'e'] element = ['x','x','x','x','x'] for i in range(0, len(element_src)): element[i] = element_src[weizhi[i]] element
['a', 'c', 'd', 'b', 'e']
ele_encode = {} s = "" j = 0 for i in range(len(codes)-1,-1,-1): if(codes[i] == -1): ele_encode[element[j]] = s j += 1 s = "" else: s += str(codes[i]) ele_encode
{'a': '01', 'c': '10', 'd': '11', 'b': '000', 'e': '001'}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)