主要内容 数据结构与算法 第五章树 51树的概念 52树的链式存储 任课教员:张铭 http:/db.pku.edu.cn/mzhang/ds/ 53树的顺序存储 zhang@db.pku.edu.cn 北京大学信息科学与技术学院 令54K又树 网络与信息系统研究所 版权所有,转或翻印必究 补充树计数 张铭嶇 0权责。翰印彭究 51树的概念 511树和森林 令511树和森林 令树的逻辑结构 令树形结构的各种 512森林与二叉树的等价转换 表示法 令513树的抽象数据类型 树的定义和概念∞ BObF GO C 令森林的定义 令514树的周游 张帖霉 斯有 京大息 树的逻辑结构 树形结构的各种表示法 包含n个结点的有穷集合K(n>0),且在K上定义了一个 关系N,关系N满足以下条件 树形表示法 有且仅有一个点k。∈K,它对于关系N来说没有齣驱。结 令形式语言表示法 除结点k外,K中的每个结点对于关系N来说备有且仅有一 令文氏图表示法 除結点k外的任何结点k∈K,都存在一个结点序列k0 令凹入表表示法 k1,…,k3,使得k就是树根,且k=k,其中有序对<k 嵌套括号表示法 1k>∈N(1≤≤s)。这样的结点序列称为从根到结点k的 北京大带息歌
1 数据结构与算法 第五章 树 任课教员:张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有,转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 2 主要内容 5.1 树的概念 5.2 树的链式存储 5.3 树的顺序存储 5.4 K叉树 补充 树计数 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 3 5.1 树的概念 5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 4 5.1.1 树和森林 树的逻辑结构 树形结构的各种 表示法 树的定义和概念 森林的定义 I J F E G A B C D H 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 5 树的逻辑结构 包含n个结点的有穷集合K (n>0),且在K上定义了一个 关系N,关系N满足以下条件: 有且仅有一个结点k0∈K,它对于关系N来说没有前驱。结 点k0称作树的根 除结点k0外,K中的每个结点对于关系N来说都有且仅有一 个前驱 除结点k0外的任何结点k∈K,都存在一个结点序列k0, k1,…,ks,使得k0就是树根,且ks=k,其中有序对<ki- 1,ki >∈N(1≤i≤s)。这样的结点序列称为从根到结点k的 一条路径 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 6 树形结构的各种表示法 树形表示法 形式语言表示法 文氏图表示法 凹入表表示法 嵌套括号表示法
树形表示法 形式语言表示法 树的理辑结构是 结点集合K={A,B,C,D,E,F,G,H,I, K上的关系N={<A,B>,<A,C>,<B,D>, ○○○ B,E>,<B,F>,<c,G>, (a)树形表示法 有,轴 张铭嶇 0权责。翰印彭究 文氏图表示法 凹入表表示法 oooollo o (b)文氏图衰示法 c)凹入表表示法 张帖霉 张铭 512豪林与二叉树的等价转换 歌晶灵型 嵌套括号表示法 24动态左子点右兄弟点“二又链我表示法 (A(B(D)(E(D)(J)(F)C(G)(H)) (d)墩套括号表示法 534带度量的后次序表示 图书目录,杜威表示法
2 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 7 树形表示法 I J F E G A B C D H (a)树形表示法 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 8 形式语言表示法 树的逻辑结构是: 结点集合K={A,B,C,D,E,F,G,H,I,J} K上的关系N={<A,B>,<A,C>,<B,D>, <B,E>,<B,F>,<C,G>, <C,H>,<E,I>,<E,J>} 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 9 文氏图表示法 A B C D I J F E G H (b)文氏图表示法 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 10 凹入表表示法 B A D E I J F G H C (c)凹入表表示法 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 11 5 树 5.1 树的概念 5.1.1 树和森林 5.1.2 森林与二叉树的等价转换 5.1.3 树的抽象数据类型 5.1.4 树的周游 5.2 树的链式存储 5.2.1 子结点表表示法 5.2.2 左子结点/右兄弟结点表示法 5.2.3 动态结点表示法 5.2.4 动态“左子结点/右兄弟结点”二叉链表表示法 5.2.5 父指针表示法及等价类的并查算法 5.3 树的顺序存储 5.3.1 带右链的先根次序表示法 5.3.2 带双标记位的先根次序表示法 5.3.3 带左链的层次次序表示法 5.3.4 带度数的后根次序表示法 5.4 K叉树 图书目录,杜威表示法 凹 入表表 示法 (例子 ) 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 12 嵌套括号表示法 (A(B(D)(E(I)(J))(F))(C(G)(H))) (d)嵌套括号表示法
氏图到嵌套括号表示的转化 树的定义 从最外依次将示集合 的方福转化牺号对 ■树是包括n个结点的有限集合T(n1),使得 有一个特别标出的称作根的蜡点 除根以外的其它结点被分成m个m20不相交的靠合T o⊙@o⊙@ T2,…,Tm,而且这些集合的每一个又都是树。树T1 T2,…,Tm称作这个根的子树 ■这个定义是递归的,我们用子树来定义树:只包 (A(BDOE(OF(C(GHD 结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北大啦 机新有,食 大息单 有,盛 树结构中的概念(1) 树结构中的概念(2) 着<k,k>∈N,则称k是k!的父结点(或称“父 母),而k′则是k的子结点(或“儿子”、“子女”) 没有子树的结点称作树叶或终端结点 着有序对<k,k′>及<k,k">∈N,则称k’和k 为兄弟 非终端结点称为分支结点 :若有一条由k到达k的陪径,则称k是k3的祖先,k是k 一个结点的子树的个数称为度数 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 根结点的层数为0,其它任何结点的层数 等于它的父结点的层数加1 北大位 张 新有,究 张铭鷾 叔有,印鱼究 树结构中的概念(3) 512森林与二叉树的等价转换 有序树在树T中如果子树T1,T2,…, 森林( forest)森林是零棵或多 Tm的相对次序是重要的,则称树T为有向 棵不相交的树的集合(通常是有 序集合)。 有序树,简称有序树。 删去树根,树就变成森林 在有序树中可以称T1是根的第一棵子树,T2 加上一个结点作树根,森林就变 是根的第二棵子树,等等 成树 物歌抗 新有,食邮岛究 张铭·票有,气即必究
3 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 13 文氏图到嵌套括号表示的转化 A B C D E I J G H F (A(B(D)(E(I)(J)) (C (F)) (G)(H))) 从最外层依次将表示集合 的方框转化成括号对 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 14 树的定义 树是包括n个结点的有限集合T(n≥1),使得: 有一个特别标出的称作根的结点 除根以外的其它结点被分成m个(m≥0)不相交的集合T1, T2,…,Tm,而且这些集合的每一个又都是树。 树T1, T2,…,Tm称作这个根的子树 这个定义是递归的,我们用子树来定义树:只包 含一个结点的树必然仅由根组成,包含n>1个结 点的树借助于少于n个结点的树来定义 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 15 树结构中的概念(1) 若<k,k′>∈N,则称k是k′的父结点(或称“父 母”),而k′则是k的 子结点(或“儿子”、“子女”) 若有序对<k,k′>及<k,k″>∈N,则称k′和k″ 互为兄弟 若有一条由 k到达ks的路径,则称k是ks的祖先,ks是k 的子孙 树形结构中,两个结点的有序对,称作连接这两结点的 一条边 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 16 树结构中的概念(2) 没有子树的结点称作树叶或终端结点 非终端结点称为分支结点 一个结点的子树的个数称为度数 根结点的层数为0,其它任何结点的层数 等于它的父结点的层数加1 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 17 树结构中的概念(3) 有序树 在树T中如果子树T1,T2,…, Tm的相对次序是重要的,则称树T为有向 有序树,简称有序树。 在有序树中可以称T1是根的第一棵子树,T2 是根的第二棵子树,等等 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 18 5.1.2 森林与二叉树的等价转换 森林(forest) 森林是零棵或多 棵不相交的树的集合(通常是有 序集合)。 删去树根,树就变成森林 加上一个结点作树根,森林就变 成树
森林与二叉树的等价转换(续) 图示:森林与二叉树 在树或森林与二叉树之间有一个自然 对应的关 树所对应的二叉树里 ○○ 二个孳蝻2 左子结点是它在原来树里的第 右子结点是它在原来的树里的下一个兄弟 机新有,食 大息单 张铭 有,盛 形式化:森林到二叉树 形式化:二叉树到森林 把森林F看作树的有序集合,F=(T1T2,…, 设B是一棵二叉树,rt是B的根,L是rt的左 Tn),对应于F的二叉树B(F)的定义是 子树,R是rt的右子树,则对应于B的森林 若n=0,则B(F)为空 F(B)的定义是: 着n>0,则B(F)的根是T1的根W1,B(F的左子树是 B(T1,T12,…,T1m),其中T1,T12,…,T1m是 若B为空,则F(B)是空的森林。 W1的子树;B(F的右子树是B(T2 若B不为空,则F(B)是一棵树T加上森林 此定义精确地确定了从森林到二叉树的转换 F(R),其中树T1的根为t,rt的子树为F(L 北大位 张 张铭鷾 叔有,印鱼究 513树/森林的结点ADT(1) 树/森林的结点ADT(2) emplate<dass T> void setvalue(T&)/设量结点的值 class TreeNode /设量左子结点 void s Id(TreeNode<T>* pointer) /设量右兄弟 Tree Node( const T&)//贝构造函数 void setsibling (TreeNode<T>* pointer); virtual~ TreeNodert};//析构函数 //以第一个左子结点身份插入结点 bool isLeafo /如果绪点是叶,返回tue void InsertFirst(TreeNode<T>* node); 返回结点的值 //以右兄弟的身份插入结点 TreeNode<T>* LeftMostChildo;//返回第一个左孩子 void InsertNext(TreeNode<T>* node); TreeNode<T>* Rightsibling(;/返回右兄弟 物歌抗 张 张铭·票有,气即必究
4 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 19 森林与二叉树的等价转换(续) 在树或森林与二叉树之间有一个自然 的一一对应的关系。 任何森林都唯一地对应到一棵二叉树;反 过来,任何二叉树也都唯一地对应到一个 森林。 树所对应的二叉树里 一个结点的左子结点是它在原来树里的第 一个子结点 右子结点是它在原来的树里的下一个兄弟 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 20 图示:森林与二叉树 G F D H J T2 E A B1 T11 T12 T1 C K G F H D C A B1 K E J 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 21 形式化:森林到二叉树 把森林F看作树的有序集合,F=(T1,T2,…, Tn),对应于F的二叉树B(F)的定义是: 若n=0,则B(F)为空 若n>0,则B(F)的根是T1的根W1,B(F)的左子树是 B(T11,T12,…,T1m),其中T11,T12,…,T1m是 W1的子树;B(F)的右子树是B(T2,…,Tn) 此定义精确地确定了从森林到二叉树的转换 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 22 形式化:二叉树到森林 设B是一棵二叉树,rt是B的根,L是rt的左 子树,R是rt的右子树,则对应于B的森林 F(B)的定义是: 若B为空,则F(B)是空的森林。 若B不为空,则F(B)是一棵树T1加上森林 F(R),其中树T1的根为rt,rt的子树为F(L) 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 23 5.1.3 树/森林的结点ADT(1) template<class T> class TreeNode { public: TreeNode(const T&);//拷贝构造函数 virtual ~TreeNode(){}; //析构函数 bool isLeaf(); //如果结点是叶,返回true T Value(); //返回结点的值 TreeNode<T>* LeftMostChild(); //返回第一个左孩子 TreeNode<T>* RightSibling(); //返回右兄弟 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 24 树/森林的结点ADT(2) void setValue(T&); //设置结点的值 //设置左子结点 void setChild(TreeNode<T>* pointer); //设置右兄弟 void setSibling(TreeNode<T>* pointer); //以第一个左子结点身份插入结点 void InsertFirst(TreeNode<T>* node); //以右兄弟的身份插入结点 void InsertNext(TreeNode<T>* node); };
树/森林的ADT(1) 树/森林的ADT(2) template <dlass t> class Tree 返回 current结点的父结点 TreeNode<T>* Parent(TreeNode<T>* current); //构造函数 /删除以 subroot为根的子树的所有结点 virtual~ Tree(;//析构函数 void Delete SubTree(TreeNode<T>* subroot) 回树中的根结点 /先根深度优先周游树 TreeNode<t>* getRooto void Root First /创建树中的根结点,使根结点元章的值为 rootValue /后根深度优先周游树 void CreateRoot(const T& rootValue); 判断是否为空树,如果是则返回true 广度优先周游树 bool isEmpty Or id widthTraverse(TreeNode<T>* root); 北大啦 514森林的周游 森林的周游 按深度方向周游 先根次序 后根次序 ○○ ndBI Rr 按广度方向周游 宽度优先周游 层次周游 北大位 张 新有,究 张铭鷾 叔有,印鱼究 周游森林vs周游二叉树 补充:一种广度优先周游森林 m先根次序周游森林 前序法周游二叉树 后根次序周游森林 ■按中序法周游对应的二叉树 ■中根周游? 无法明确规定根在哪两个子结点之间 Prevsiblingo函数采用本框架 物歌抗 新有,食邮岛究 张铭·票有,气即必究
5 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 25 树/森林的ADT(1) template <class T> class Tree { public: Tree(); //构造函数 virtual ~Tree(); //析构函数 //返回树中的根结点 TreeNode<T>* getRoot(); //创建树中的根结点,使根结点元素的值为rootValue void CreateRoot(const T& rootValue); //判断是否为空树,如果是则返回true bool isEmpty(); 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 26 树/森林的ADT(2) //返回current结点的父结点 TreeNode<T>* Parent(TreeNode<T>* current); //返回current结点的前一个邻居结点 TreeNode<T>* PrevSibling(TreeNode<T>* current); //删除以subroot为根的子树的所有结点 void DeleteSubTree(TreeNode<T>* subroot); //先根深度优先周游树 void RootFirstTraverse(TreeNode<T>* root); //后根深度优先周游树 void RootLastTraverse(TreeNode<T>* root); //广度优先周游树 void WidthTraverse(TreeNode<T>* root); }; 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 27 5.1.4 森林的周游 按深度方向周游 先根次序 后根次序 按广度方向周游 宽度优先周游 层次周游 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 28 森林的周游 A B C K F D E G H J G H F D C A B K E J 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 29 周游森林vs周游二叉树 先根次序周游森林 前序法周游二叉树 后根次序周游森林 按中序法周游对应的二叉树 中根周游? 无法明确规定根在哪两个子结点之间 北京大学信息学院 张铭 编写 ©版权所有,转载或翻印必究 Page 30 补充:一种广度优先周游森林 A B C K F D E G H J G H F D C A B K E J PrevSibling()函数采用本框架