数据结构与STL_第5章_树

null第五章 树和二叉树第五章 树和二叉树北京邮电大学 信息与通信工程学院《数据结构与STL》第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树 （计划学时6h）*1. 树的逻辑结构《数据结构与STL》5.1 树的逻辑结构5.1 树的逻辑结构定义 树是n (n≥0) 个结点的有限集, 如果n=0，称为空树；如果n>0，则 (1) 有且仅有一个称为根的结点root (2) n>1时，其余结点可分为m个互不相交的有限集T1 … Tn，其中每一个集合又是一棵树，称为根的子树 *《数据结构与STL》5.1 树的逻辑结构5.1 树的逻辑结构*root《数据结构与STL》2. 树的基本术语2. 树的基本术语结点的度 树的度 叶结点 分支结点 《数据结构与STL》*结点的度：结点拥有的子树的个数。树的度：树内各结点的度的最大值。叶结点：度为0的结点。分支结点：度不为0的结点。2. 树的基本术语2. 树的基本术语孩子 双亲 兄弟 祖先 子孙 《数据结构与STL》* 结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。 同一双亲的孩子之间互称兄弟。 结点的祖先：从根到该结点所经分支上的所有结点。结点的子孙：以某结点为根的子树中任一结点。2. 树的基本术语2. 树的基本术语路径 路径长度《数据结构与STL》*路径：从根结点到其他结点的一条路经。路径长度：路经经过的边的个数。路径长度=32. 树的基本术语2. 树的基本术语结点层次 树的深度《数据结构与STL》*树的深度：树中结点的最大层次。 2. 树的基本术语2. 树的基本术语层序编号 《数据结构与STL》* 将树中结点按照从上到下. 同层从左到右的次序依次给它们从1开始编号，这种方式就是层序编号。2. 树的基本术语2. 树的基本术语有序树 无序树 《数据结构与STL》* 如果树中各结点的子树从左至右是有次序的（不能互换），则称该树为有序树；否则为无序树。2. 树的基本术语2. 树的基本术语森林 《数据结构与STL》* m(m>=0)棵互不相交的树的集合构成森林。2. 树的基本术语2. 树的基本术语同构《数据结构与STL》* 两棵树同构就是这两棵树的形状相同。第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树*2. 树的存储结构《数据结构与STL》5.2 树的存储结构5.2 树的存储结构四种存储结构 双亲示法 孩子表示法 双亲孩子表示法 孩子兄弟表示法 树的基本操作*《数据结构与STL》1）双亲表示法1）双亲表示法*0 1 2 3 4 5 6size=6《数据结构与STL》结点结构 结点的C++描述 #define MaxSize 100 template struct pNode { T data; int parent; } ; 树的描述： pNode Tree[MaxSize]; int size;带右兄弟的双亲表示法带右兄弟的双亲表示法*0 1 2 3 4 5 6size=6《数据结构与STL》结点结构 结点的C++描述 template struct pNode { T data; int parent，rightsib; } ; 树描述： pNode Tree[MaxSize]; int size;2）孩子表示法2）孩子表示法①多重链表表示法*《数据结构与STL》结点结构缺点：会浪费大量的指针域2）孩子表示法2）孩子表示法*0 1 2 3 4 5 6《数据结构与STL》struct CNode { int child; CNode *next; } template struct CBNode { T data; CNode *firstchild; } 孩子结点表头结点②孩子链表表示法3）双亲孩子表示法3）双亲孩子表示法*0 1 2 3 4 5 6《数据结构与STL》4）孩子兄弟表示法4）孩子兄弟表示法*root《数据结构与STL》结点结构结点描述 template struct TNode { T data; TNode *firstchild,*rightsib; } ;树的基本操作树的基本操作InitTree() DestroyTree() Root() Parent() Depth() //求树的深度 PreOrder() //先序遍历 PostOrder() //后序遍历 LevelOrder() //层次遍历*《数据结构与STL》树的遍历树的遍历定义 从根结点出发，按照某种次序依次访问树的所有结点，使每个结点仅被访问一次。 分类 1. 前序遍历 2. 后序遍历 3. 层序遍历 *《数据结构与STL》 访问：对结点的各种处理，比如，输出结点内容如何遍历这棵树？如何遍历这棵树？*root《数据结构与STL》树的遍历树的遍历1. 前序遍历 （1）访问根结点 （2）按照从左到右的顺序依次遍历根结点的每一棵子树。*《数据结构与STL》A BEFKL CG DHIJM树的遍历树的遍历2. 后序遍历 （1）按照从左到右的顺序依次遍历根结点的每一棵子树 （2）访问根结点。*《数据结构与STL》EKLFB GC HIMJD A树的遍历树的遍历3. 层序遍历（也称为广度遍历） 从第一层开始，从上到下逐层遍历，同层按从左到右的顺序遍历。 *《数据结构与STL》A BCD EFGHIJ KLM练习练习写出该树的前序. 后序. 层次遍历序列*前序：ABCEFGD后序：BEGFCDA层次：ABCDEFG《数据结构与STL》练习练习写出该树的度. 深度，以及前序. 后序. 层次遍历序列 *前序：ABEFCGDHKLMIJ后序：EFBGCKLMHIJDA层次：ABCDEFGHIJKLM树的度为3，深度为4《数据结构与STL》第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树*3. 二叉树的逻辑结构《数据结构与STL》5.2 二叉树的逻辑结构5.2 二叉树的逻辑结构定义 n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的左右子树组成。 特点 1. 每个结点最多只有两个子树 2. 左右子树次序不能颠倒 *《数据结构与STL》5.2 二叉树的逻辑结构5.2 二叉树的逻辑结构树和二叉树的区别 *同一棵树不同的二叉树《数据结构与STL》5.2 二叉树的逻辑结构5.2 二叉树的逻辑结构二叉树具备5种形态*《数据结构与STL》5.2 二叉树的逻辑结构5.2 二叉树的逻辑结构特殊的二叉树 （1）斜树 （2）满二叉树 （3）完全二叉树*《数据结构与STL》特殊的二叉树特殊的二叉树（1）斜树 所有结点都只有左子树的二叉树称为左斜树； 所有结点都只有右子树的二叉树称为右斜树。《数据结构与STL》*特殊的二叉树特殊的二叉树（2）满二叉树 所有的分支结点都存在左子树和右子树，并且所有叶子都在同一层上。*《数据结构与STL》特殊的二叉树特殊的二叉树（3）完全二叉树 按从上到下. 从左到右的顺序为结点编号，与满二叉树序号一一对应的二叉树。*《数据结构与STL》2. 二叉树的性质2. 二叉树的性质性质1： 在二叉树的第i层上至多有 2i-1个结点(i≥1).*《数据结构与STL》数学归纳法证明当i=1 只有一个根结点 2i-1=20=1成立 假设i=k 结论成立，即第k层最多有2k-1结点则i=k+1时，由于第k层每个结点最多有两个孩子结点，所以该层最多有结点2*2k-1 =2k结点. 由此，该结论成立2. 二叉树的性质2. 二叉树的性质性质2 深度为 k 的二叉树至多有 2k-1 个结点 (k≥0)。*《数据结构与STL》根据性质1，求等比数列的前k项和： 20 + 21 + 22 + … + 2k-1 = 2k-1提示：试试利用性质12. 二叉树的性质2. 二叉树的性质性质3 任何一棵二叉树T，如果其叶结点数为n0，度为2的结点数为n2，则n0=n2+1. *《数据结构与STL》2. 二叉树的性质2. 二叉树的性质1）二叉树只有三类结点，度为0. 1. 2的结点，所以 树总的结点： n0 +n1+ n2 2）二叉树n0没有分支， n1有1个分支； n2有2个分支，所以 树的总分支: 2*n2 + n1 * 结点数和分支数的关系？《数据结构与STL》习

题

快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题

习题已知正则二叉树中（只有度为0和2的结点）有n个叶子结点，则这个二叉树的结点总数是_____ A 2*n B 2*n-1 C 2*n+1 D 不确定 *《数据结构与STL》2. 二叉树的性质2. 二叉树的性质性质4 具有n个结点的完全二叉树的深度为 +1。 *《数据结构与STL》根据性质2: 设完全二叉树的深度为k，则其结点数 2k-1-1 1，则其双亲为[i/2] (2) 如果2i>n，则结点无左孩子，否则其左孩子为2i (3) 如果2i+1>n，则无右孩子，否则其右孩子为2i+1 *《数据结构与STL》2. 二叉树的性质2. 二叉树的性质*双亲左孩子右孩子《数据结构与STL》用归纳法可证（2）和（3），再用（2）和（3）证明（1）。3. 二叉树的基本操作3. 二叉树的基本操作InitBiTree() DestroyBiTree() PreOrder() //前序遍历 InOrder() // 中序遍历 PostOrder() //后序遍历 LevelOrder() //层次遍历*《数据结构与STL》4. 二叉树的遍历4. 二叉树的遍历三种遍历方式 1）前序遍历（DLR） 2）中序遍历（LDR） 3）后序遍历（LRD） 4）层序遍历 约定 D：根结点 L：左子树 R：右子树 *《数据结构与STL》4. 二叉树的遍历4. 二叉树的遍历1. 前序遍历（DLR） （1）访问根结点 （2）前序遍历左子树 （3）前序遍历右子树 *《数据结构与STL》A BDEFG C4. 二叉树的遍历4. 二叉树的遍历2. 中序遍历（LDR） （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树 *《数据结构与STL》DBFEG A C4. 二叉树的遍历4. 二叉树的遍历3. 后序遍历（LRD） （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点 *《数据结构与STL》DFGEB C A4. 二叉树的遍历4. 二叉树的遍历4. 层序遍历（也称为广度遍历） 从第一层开始，从上到下逐层遍历，同层按从左到右的顺序遍历*《数据结构与STL》A BC DE FG练习练习写出二叉树的前序. 中序. 后序. 层序序列*前序：A BDEF CGH中序：DBFE A GHC后序：DFEB HGC A层序：A BC DEG FH《数据结构与STL》思考思考已知二叉树的前序序列 { ABCDEFGH } 和中序序列 { CDBAFEHG } ，能否唯一确定一棵二叉树? D L R L D R L R D *《数据结构与STL》null*前序序列 { A BCD EFGH }中序序列 { CDB A FEHG }《数据结构与STL》练习练习已知二叉树的前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG } ，画出该二叉树。*《数据结构与STL》null*前序 { ABHFDECKG }中序 { HBDFAEKCG }《数据结构与STL》思考思考什么样的二叉树前序序列和中序序列相同？ 什么样的二叉树后序序列和中序序列相同？ 什么样的二叉树前序序列和后序序列相同？ D L R L D R L R D*《数据结构与STL》第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树*4. 二叉树的存储结构《数据结构与STL》5.4 二叉树的存储结构5.4 二叉树的存储结构二叉树的存储结构 1）顺序存储结构 2）二叉链表 3）三叉链表 4）线索链表*《数据结构与STL》1）顺序存储结构1）顺序存储结构*《数据结构与STL》 用一维数组存储二叉树中的结点 结点的存储位置（下标）体现结点之间的逻辑关系——父子关系。 完全二叉树 一般二叉树00 1 2 3 4 5 6 7 8 990 1 2 3 4 5 6 7 8 9137894562012543678顺序存储结构顺序存储结构*《数据结构与STL》

方法

快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载

：1. 将二叉树按照完全二叉树编号 2. 然后用一维数组存储该二叉树，其中无结点的位置使用NULL表示完全二叉树适合采用顺序存储结构2）二叉链表2）二叉链表*《数据结构与STL》结点的C++的类型描述： template struct Node { T data; Node* lch; Node* rch; };二叉树的C++描述二叉树的C++描述template class BiTree { protected: Node *root; void Create (Node* &R, int i); void Release(Node *R); public: BiTree(): root(NULL){} BiTree(Node *R); void PreOrder ( Node *R ); void InOrder ( Node *R ); void PostOrder ( Node *R ); void LevelOrder ( Node *R ); ~BiTree(); };*《数据结构与STL》建立二叉树建立二叉树基本思想 以顺序存储结构作为建立二叉树的输入，根据二叉树的定义，分三步建树： 1. 建立根结点 2. 建立左子树 3. 建立右子树 *《数据结构与STL》nulltemplate void BiTree::Create(Node *&R, int i, char ch[], int num) { if (i>num || ch[i]==‘0’) R = NULL; else { R=new Node; R->data = ch[i]; Create(R->lch, 2*i, ch, num); Create(R->rch, 2*i+1 , ch, num); } }//注意，ch[0]没用。*《数据结构与STL》二叉链表的遍历二叉链表的遍历假设使用二叉链表表示二叉树已经建立，则如何实现以下四种遍历操作？ ①PreOrder() //前序遍历 ②InOrder() //中序遍历 ③PostOrder() //后序遍历 ④LevelOrder() //层次遍历*《数据结构与STL》① PreOrder() 前序遍历 DLR递归实现① PreOrder() 前序遍历 DLR递归实现template < class T > void BiTree::PreOrder ( Node *Root ) { if (Root!=NULL) { cout<data; // 访问结点 PreOrder(Root ->lchild); // 遍历左子树 PreOrder(Root ->rchild); // 遍历右子树 } }*《数据结构与STL》① PreOrder() 前序遍历 DLR非递归实现① PreOrder() 前序遍历 DLR非递归实现二叉树前序遍历非递归的关键 在前序遍历完某结点的左子树后，如何找到该结点的右子树的根？ * 这就需要栈：保存当前结点，然后当该结点的左子树访问完毕后，当前结点出栈，访问其右子树。《数据结构与STL》前序遍历过程前序遍历过程*《数据结构与STL》基本思想基本思想1）如果当前结点非空 访问当前结点 当前结点入栈； 将当前结点的左孩子作为当前结点； 2）如果当前结点为空 栈顶结点出栈， 将该结点的右孩子作为当前结点； 反复执行1）2)，直到当前结点=NULL && 栈空. *《数据结构与STL》nulltemplate void BiTree::PreOrder(Node *R) { Stack*> S; while(!S.IsEmpty() || (R!=NULL)) { if (R!=NULL) { cout<data; S.Push(R); R=R->lch; } else { R=S.Pop(); R=R->rch; } } }*《数据结构与STL》root②InOrder() 中序遍历LDR-递归②InOrder() 中序遍历LDR-递归template < class T > void BiTree::InOrder ( Node *Root ) { if (Root!=NULL) { InOrder(Root ->lchild); // 遍历左子树 cout<data; // 访问结点 InOrder(Root ->rchild); // 遍历右子树 } } *《数据结构与STL》root②InOrder() 中序遍历LDR-非递归②InOrder() 中序遍历LDR-非递归中序与前序遍历的区别 前序遍历： 1）先访问该结点 2）再入栈 3）然后访问其左子树； 4）出栈，访问其右子树 中序遍历： 1）先入栈 2）访问其左子树 3）结点出栈，访问该结点； 4）访问该结点的右子树*《数据结构与STL》中序遍历过程中序遍历过程*《数据结构与STL》基本思想基本思想1）如果当前结点非空 当前结点入栈； 将当前结点的左孩子作为当前结点； 2）如果当前结点为空 栈顶结点出栈， 访问当前结点 将该结点的右孩子作为当前结点； 反复执行1）2)，直到当前结点NULL && 栈空 *《数据结构与STL》nulltemplate void BiTree::InOrder (Node *R) { Stack*> S; while(!S.IsEmpty() || (R!=NULL)) { if (R!=NULL) { S.Push(R); R=R->lch; } else { R=S.Pop(); cout<data; R=R->rch; } } }*《数据结构与STL》③PostOrder() 后序遍历LRD -递归③PostOrder() 后序遍历LRD -递归template < class T > void BiTree::PostOrder ( Node *Root ) { if (Root!=NULL) { PostOrder(Root ->lchild); // 遍历左子树 PostOrder(Root ->rchild); // 遍历右子树 cout<data; // 访问结点 } }*《数据结构与STL》③PostOrder() 后序遍历LRD –非递归③PostOrder() 后序遍历LRD –非递归二叉树后序遍历的关键 1）当前结点入栈，访问其左子树 2）利用栈顶结点，访问其右子树 3）当前结点出栈，访问该结点*《数据结构与STL》 因此，必须为栈中的元素设置标记，用来判断什么时候出栈。后序遍历过程后序遍历过程*《数据结构与STL》③PostOrder() 后序遍历LRD-非递归③PostOrder() 后序遍历LRD-非递归后序遍历的过程 1.当前结点指针!=NULL时，入栈，置标记(L)，遍历左子树; 2.当前结点指针==NULL时， (1)若栈顶元素标记为R，退栈打印，直到栈顶元素标记为L； (2)若栈顶元素标记为L，改标记R,则遍历右子树； 反复执行1）2）直到栈空。*《数据结构与STL》栈中元素的结构template struct SNode { Node *ptr; int tag; //1左 2右 };nulltemplate void BiTreee::Postorder (Node *R) { SNode S[MAXSIZE]; int top = -1; do { while (R!=NULL) //左子树不空，进栈 { S[++top].ptr=R; S[top].tag=1； R=R->lch; } while(top!=-1 && S[top].tag==2) //右子树返回,访问结点； { cout<data; top--; } if(top!=-1 && S[top].tag==1) //左子树返回，修改标志； { R=S[top].ptr->rch; S[top].tag=2; } } while(top!=-1) }*《数据结构与STL》④LevelOrder() //层次遍历④LevelOrder() //层次遍历层序遍历 从上到下，从左到右依次访问每一个结点。先访问的结点，其左右孩子结点也会先访问。 *《数据结构与STL》ABCDEGF ④LevelOrder() 层次遍历④LevelOrder() 层次遍历这是一个队列的应用 基本思想 根结点非空，入队。 如果队列不空 { 队头元素出队 访问该元素 若该结点的左孩子非空，则左孩子入队； 若该结点的右孩子非空，则右孩子入队； } *《数据结构与STL》nulltemplate void BiTree::LevelOrder (Node *R) { Queue*> Q; if (R!=NULL) Q.InQueue(R); while (!Q.IsEmpty()) { Node *p=Q.DelQueue(); cout<data; if (p->lchild!=NULL) Q.InQueue(p->lchild); if (p->rchild!=NULL) Q.InQueue(p->rchild) } }*《数据结构与STL》析构函数析构函数template < class T > void BiTree::Release ( Node *Root ) { if (Root!=NULL) { Release(Root ->lchild); // 释放左子树 Release(Root ->rchild); // 释放右子树 delete Root; // 释放根结点 } } *《数据结构与STL》例1例1统计二叉树中的结点总数 *提示： 结点总数= 左子树 + 右子树 + 1《数据结构与STL》统计二叉树中的结点总数统计二叉树中的结点总数template int Count(Node *R) { if (R==NULL) return 0; else { int m=Count(R->lch); int n=Count(R->rch); return m+n+1; } }*《数据结构与STL》思考题思考题已知二叉树的前序序列 和中序序列 ，编写算法建立二叉树。 测试数据： 前序序列{ ABHFDECKG } 中序序列{ HBDFAEKCG } *《数据结构与STL》null*前序 { ABHFDECKG }中序 { HBDFAEKCG }《数据结构与STL》基本思路基本思路1. 前序序列(s1,e1)中的s1位置是根结点R 2. 在中序序列(s2,e2)中找R的位置pos 3. 将前序序列进行分割 i= s1+pos-s2， (s1+1, i) (i+1, e1) 4. 将中序序列进行分割 (s2, pos-1) (pos+1, e2) 反复继续，1，2，3,4直到区间中只有一个元素。*《数据结构与STL》前序 { ABHFDECKG }中序 { HBDFAEKCG }代码代码//辅助函数，查找元素x中序序列的位置 template int BiTree::Find(T x, T InBuf[], int s, int e) { //s中序序列查找区间左边界 e 右边界 for(int i=s; i<=e && InBuf[i]!='\0'; i++) if (InBuf[i]==x) return i; return 0; } // 注意下标0的元素没使用*《数据结构与STL》nulltemplate void BiTree::Create(Node* &R, T PreBuf[], T InBuf[], int s1, int e1, int s2, int e2) { if (s1<=e1) { int pos=Find(PreBuf[s1], InBuf, s2, e2); if (pos==0) R=NULL; else { R=new Node; R->data = PreBuf[s1]; int i = s1+pos-s2; Create(R->lch, PreBuf, InBuf, s1+1,i,s2,pos-1); Create(R->rch, PreBuf, InBuf, i+1, e1, pos+1,e2); } } else R=NULL; }*《数据结构与STL》前序 { ABC }中序 {BAC }3）三叉链表3）三叉链表*《数据结构与STL》3）三叉链表3）三叉链表 三叉链表结点的C++的类型描述： template struct Node { public: T data; Node* parent; Node* lchild; Node* rchild; };*《数据结构与STL》4. 线索链表4. 线索链表N个结点的二叉链表一共有________指针域？ 其中有_________指针域是NULL? 我们能不能充分利用这些NULL的指针域，用来保存一些有用的信息？ *《数据结构与STL》2NN+14. 中序线索链表4. 中序线索链表*ACGBErootDFlchilddatarchild 结点结构：ltagrtag《数据结构与STL》线索二叉树线索二叉树template struct Node { T data; Node * lch, *rch; int ltag；//1 表示左孩子 2表示前驱 int rtag; //1 表示右孩子 2表示后继 }*《数据结构与STL》第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树*5. 树、森林、二叉树的转换《数据结构与STL》5.5 树、森林、二叉树的转换5.5 树、森林、二叉树的转换树的孩子兄弟表示法*《数据结构与STL》5.5 树、森林、二叉树的转换5.5 树、森林、二叉树的转换二叉链表表示法 *《数据结构与STL》物理结构物理结构*物理结构相同，只是解释不同而已。《数据结构与STL》逻辑结构逻辑结构*树和二叉树的逻辑结构有一一对应的关系。《数据结构与STL》1. 树转换成二叉树1. 树转换成二叉树*树与二叉树的对应关系 当以二叉链表为存储结构时，给定一颗树，可以找到唯一的一颗二叉树与之对应。 任何一颗与树对应的二叉树，其右子树必空。ABCEDABCDE树转换成二叉树树转换成二叉树转换原则 第一个右兄弟结点 右孩子 第一个孩子结点  左孩子*《数据结构与STL》null树转换为二叉树的方法： （1）加线：树中所有相同双亲结点的兄弟结点之间加一条连线； （2）去线：对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去该结点与其他孩子结点之间的连线； （3）调整：整理所有保留的和添加的连线，使每个结点的孩子结点连线位于左孩子指针位置，使每个结点的兄弟结点连线位于右孩子指针位置。树转换成二叉树树转换成二叉树特点 树的前序遍历 二叉树的前序遍历 树的后序遍历 二叉树的中序遍历*《数据结构与STL》前序:ABCDE 后序：BDCEA前序:ABCDE 中序：BDCEAnullABDCEIFGH练习null二叉树还原为树的方法 （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来； （2）删除原二叉树中所有双亲结点与右孩子结点的连线； （3）整理所有保留的和添加的连线，使每个结点的孩子结点连线顺序位于下方孩子结点位置。2. 森林转换成二叉树2. 森林转换成二叉树森林：是若干棵树的集合 若干棵树—>森林，每一棵树—>二叉树 —>森林－>二叉树 转换原则 1）将森林中的每棵树转换成二叉树 2）从第二棵树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子。*《数据结构与STL》null森林转换为二叉树方法 从第二棵二叉树开始，依次将当前二叉树的根结点作为前一棵二叉树根结点的右孩子结点，直至所有二叉树都连接起来。森林转换成二叉树森林转换成二叉树*《数据结构与STL》3. 二叉树转换成森林3. 二叉树转换成森林转换原则 1）根结点的右孩子  第二棵树的根结点 根结点右孩子的右孩子第三棵树的根结点 …… 2）根结点的左孩子 按照结点的左孩子是该结点的第一个孩子，结点右孩子是该结点的右兄弟转换。*《数据结构与STL》二叉树转换成森林二叉树转换成森林*《数据结构与STL》4. 森林的遍历4. 森林的遍历森林有两种遍历方式 1）前序遍历 前序遍历森林中的每一棵树 2）后序遍历 后序遍历森林中的每一棵树*《数据结构与STL》森林的遍历森林的遍历前序序列： 后序序列：*ABECD FG HIJKEBCDA GF IKJH《数据结构与STL》第五章 树和二叉树第五章 树和二叉树学习内容： 　　1. 树的逻辑结构 　　2. 树的存储结构 　　3. 二叉树的逻辑结构 　　4. 二叉树的存储结构 　　5. 树、森林、二叉树的转换 　　6. 哈夫曼树*6. 哈夫曼树《数据结构与STL》5.6 哈夫曼树5.6 哈夫曼树1. 相关概念 1）叶子结点的权值 对叶子结点赋予一个有意义的数量值。 2）二叉树的带权路径长度 设二叉树有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和。 *例如：WPL= 72+52+23+43+92 =60《数据结构与STL》null 3）哈夫曼树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。*《数据结构与STL》WPL1= 22+43+53+32 = 37 WPL2= 23+43+52+31 = 31 WPL3= 22+32+42+52 =28 WPL4= 23+33+42+51 =28 三棵具有相同权值叶子结点的二叉树图c图dnull已知：一组权值给定的叶子结点{w1,w2 , … , wn}，如何构造一棵哈夫曼树？*提示 ： 只要让权值最大的叶子结点离根最近，权值最小的叶子结点离根最远，就能使带权路径长度最小。《数据结构与STL》2. Huffman树构造算法null构造哈夫曼树（从下向上构造） 已知：权值表 {w1, w2, …, wn} 1）选择有效权值中最小的两个，构成最小二叉树，标记这两个权值已用。 2）将这两个权值相加，之和并入权值表;返回1。 结束条件 如果权值表没有没用过的权值。 *《数据结构与STL》例如：已知权值 W={ 5, 6, 2, 9, 7 }例如：已知权值 W={ 5, 6, 2, 9, 7 }*第一步第二步第三步《数据结构与STL》例如：已知权值 W={ 5, 6, 2, 9, 7 }例如：已知权值 W={ 5, 6, 2, 9, 7 }*第四步第五步：《数据结构与STL》注意 : 结点有规律的放置问题(全部左小右大或全部左大右小)3. Huffman编码3. Huffman编码编码 给每一个字符标记一个单独的代码。 编码分类 等长编码：ASCII码等 不等长编码：Huffman编码*《数据结构与STL》例如，假设要传送的电文为 ABACCDA， 电文中只有A,B,C,D四种字符。 00 01 00 10 10 11 00，码长14。(表a,等长码) 0 110 0 10 10 111 0，码长13。(表b)null思想（不等长编码） 使用频率高的字符，编码长度短； 使用频率低的字符，编码长度长； 利用不等长编码，可以使报文总长度较短，这也是文件压缩技术的核心。 *《数据结构与STL》null不等长编码的关键：解码时的唯一性 比如：A:0 B:1 C:10 编码：AABAABC00100110 解码：AA?* 让任意编码都不是其他编码的前缀B:10 C:11编码：AABAABC0010001011解码：AABAABC《数据结构与STL》nullHuffman编码是最优前缀编码. 约定 左分支：0 右分支：1 叶结点编码 从根到叶子的路径 *000111100101《数据结构与STL》null两种编码方式 1）字符编码 比如：A的编码是1110,则使用4个字符‘1’ ‘1’ ‘1’‘0’存储在文件中。 2）bit编码 比如：A的编码是1110，则使用4个bit存储。 提示：二进制文件存储的最小单位是字节，所以必须使用位运算法，每当凑够8个bit时，存储一次。*《数据结构与STL》4. Huffman编码的解码4. Huffman编码的解码解码过程 1)从左到右读取编码串 2)从根结点开始,如果是0,则选择左支;如果是1,则选择右支;直到叶结点。 反复上述过程,直到翻译完毕。*《数据结构与STL》0001001110110111101 CDCEBBEBnull练习: 假设用于通讯的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成，各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母

设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

哈夫曼编码，并给出该电文的总码数。5253610364{5, 25, 3, 6, 10, 11, 36, 4}{5, 25, 6, 10, 11, 36, 7}11{11, 25, 10, 11, 36, 7}17{11, 25, 11, 36,17}1161100{22, 25, 36,17}{39, 25, 36}{39, 61}{100}01000000111111c1c2c3c4c5c6c7c872239null编码： c1:0100 c2:10 c3:0000 c4:0101 c5:001 c6:011 c7:11 c8:0001WPL=5*4+25*2+3*4+6*4+10*3+11*3+36*2+4*4=257电文的总码长 =5*4+25*2+3*4+6*4+10*3+11*3+36*2+4*4=2575. Huffman树的存储结构5. Huffman树的存储结构哈夫曼树的特点 只有度为2的结点和叶子结点，所以具有n个叶子结点的哈夫曼树的结点总数 。 顺序存储结构 设置一个的huffTree[2*n-1]数组，*《数据结构与STL》2*n-1null哈夫曼树的C++描述 struct HNode { int weight; int lchild, rchild, parent; }; HNode huffTree[2*n-1];*《数据结构与STL》例如:已知权值 W={ 5, 6, 2, 9, 7 }例如:已知权值 W={ 5, 6, 2, 9, 7 }*初始状态01234weight lchild rchild parent5678《数据结构与STL》结束状态01234weight lchild rchild parent56786. Huffman 编码的相关代码6. Huffman 编码的相关代码huffman编码表C++描述： strcut HCode { char data; char code[100]; }; //字符及其编码结构 HCode HCodeTable[N]; //文本码表Huffman 编码的C++类Huffman 编码的C++类class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, char *d); //编码 void Decode(char *s, char *d); //解码 ~ Huffman(); }创建huffman树代码创建huffman树代码void Huffman::CreateHTree(int a[], int n) { //根据权重数组a[1->n] 初始化Huffman树 huffTree = new HNode [2*n-1]; for (int i = 0; i < n; i++) { huffTree[i].weight = a[i]; huffTree[i].LChild = -1; huffTree[i].RChild = -1; huffTree[i].parent = -1; } 创建huffman树代码创建huffman树代码 int li, ri; for (int i = n; i < 2*n-1; i++) //开始建Huffman树 { //从0~i-1中选出两个权值最小的结点， SelectMin(huffTree, i, li, ri); huffTree[li].parent = huffTree[ri].parent = i; huffTree[i].weight = huffTree[li].weight + huffTree[ri].weight; huffTree[i].LChild = li; huffTree[i].RChild = ri; huffTree[i].parent = -1; } }找两个权值小的结点找两个权值小的结点Select(HNode *hTree, int n, int i1, int i2); { int i; //找一个比较值的起始值 for(i=0; ihTree[i2].weight) //i1指向最小的 { j=i2; i2=i1; i1 = j; } *null* //开始找最小的两个 i++; for( ; i