数据结构与算法-树

6树2/50第5章树树的逻辑表示、基本概念树、森林与二叉树的相互转换树、森林的周游由周游序列确定二叉树UNION/FIND算法3/50树是n（n≥0）个结点的有限集。当n=0时，称为空树；在任意一棵非空树中满足如下条件：

(1)有且仅有一个特定的称为根（root）的结点，它没有直接前驱，但有零个或多个直接后继。

(2)其余n-1个结点可以划分成m（m>0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。

树的概念4/50(1)树型表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。树的逻辑表示法5/50(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。树的逻辑表示法6/50(3)凹入表示法。使用线段的伸缩描述树结构。树的逻辑表示法7/50(4)括号表示法(广义表表示法)。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。树的逻辑表示法8/50树结构中的概念没有子树的结点称作树叶或终端结点

非终端结点称为分支结点一个结点的子树的个数称为度数根结点的层数为0，其它任何结点的层数等于它的父结点的结点层数加19/50树结构中的概念有序树在树T中如果子树T1，T2，…，Tm的相对次序是重要的，则称树T为有向有序树，简称有序树。在有序树中可以称T1是根的第一棵子树，T2是根的第二棵子树，等等10/50森林与树森林(forest)

森林是零棵或多棵不相交的树的集合(通常是有序集合)。11/50(1)在所有相邻兄弟结点之间加一水平连线。(2)对每个非叶结点k,除了其最左边的孩子结点外,删去k与其他孩子结点的连线。(3)所有水平线段以左边结点为轴心顺时针旋转45度，使之结构层次分明。树做这样的转换所构成的二叉树是唯一的。树转换为二叉树12/50加边删边调整13/50将树转换为二叉树的形式表示。令结点的两个链域分别指向该结点的第一个儿子和右边的兄弟。RBACDEFHGK∧∧∧RADBE∧C∧F∧G∧∧H∧K∧∧14/50森林转换为二叉树的方法如下：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。

森林转换为二叉树15/5016/50将一棵二叉树还原为树或森林，具体方法如下：（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。（2）删掉原二叉树中所有双亲结点与右孩子结点的连线。（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。二叉树还原为树或森林17/50二叉树到森林的转换示例1.添加连线2.删除右孩子节点的连线3.整理18/50树的周游深度优先先根次序后根次序广度优先宽度优先周游（层次周游）19/501）先根次序若树非空，则遍历方法为：①访问根结点。②从左到右，依次先根遍历根结点的每一棵子树。

先根次序周游序列ABECFHGD等同于转换的二叉树进行先序周游树的周游20/502)后根次序若树非空，则遍历方法为：①从左到右，依次后根遍历根结点的每一棵子树。②访问根结点。

后根次序周游序列为EBHFGCDA等同于转换的二叉树进行中序周游树的周游21/50树的周游按广度方向周游宽度优先周游也称为层次周游层次周游序列为ABCDEFGH22/50森林的周游深度优先先根次序后根次序广度优先宽度优先周游（层次周游）23/501）先根次序若森林非空，则遍历方法为：①访问森林中第一棵树的根结点。②先根次序周游第一棵树的根结点的子树森林。③先根次序周游其他的树。

先根周游序列为ABCDEFGHIJ等同于转换的二叉树进行先序周游森林的周游24/502）后根次序若森林非空，则遍历方法为：①后根次序周游森林中第一棵树的根结点的子树森林。②访问第一棵树的根结点。③后根次序周游其他的树。

后根周游序列为BCDAFEHJIG等同于转换的二叉树进行中序遍历森林的周游25/50森林的周游按广度方向周游宽度优先周游（层次周游）层次周游序列为AEGBCDFHIJ26/50关于二叉树的先序、中序和后序周游序列确定二叉树的问题。给定先序、中序周游序列可唯一确定二叉树。给定后序、中序周游序列可唯一确定二叉树由周游序列确定二叉树27/50任何n(n≥0)个不同结点的二叉树,都可由它的中序序列和先序序列唯一地确定。证明：先序序列是a1a2…an中序序列是b1b2…bn根结点：a1。在中序序列中与a1相同的结点为：bj。

{b1…bj-1}bj{bj+1…bn}←→a1{a2…ak}{ak+1…an}28/50例：已知先序序列为ABDGCEF,中序序列为DGBAECF根结点：G左先序:空左中序:空右先序:空右中序:空根结点：A左先序:BDG左中序:DGB右先序:CEF右中序:ECF根结点：B左先序:DG左中序:DG右先序:空右中序:空根结点：D左先序:空左中序:空右先序:G右中序:G根结点：C左先序:E左中序:E右先序:F右中序:F根结点：E左先序:空左中序:空右先序:空右中序:空根结点：F左先序:空左中序:空右先序:空右中序:空29/50思考1实现由先序、中序序列构造二叉树的算法：30/50任何n(n＞0)个不同结点的二叉树,都可由它的中序序列和后序序列唯一地确定。证明：后序序列是a1a2…an中序序列是b1b2…bn根结点：an。在中序序列中与an相同的结点为：bj。{b1…bj-1}bj{bj+1…bn}←→{a1a2…ak}{ak+1…an-1}an31/50例：后序序列为GDBEFCA,中序序列为DGBAECF根结点：A左中序:DGB左根:B右中序:ECF右根:C根结点：B左中序:DG左根:D右中序:空右根:空根结点：D左中序:空左根:空右中序:G右根:G根结点：G左中序:空左根:空右中序:空右根:空根结点：C左中序:E左根:E右中序:F右根:F根结点：E左中序:空左根:空右中序:空右根:空根结点：F左中序:空左根:空右中序:空右根:空32/50思考2实现由后序、中序序列构造二叉树的算法：33/50①给定树的先根周游序列和后根周游序列可唯一画出一棵树。②给定森林的先根周游序列和后根周游序列可唯一确定一森林。

由周游序列确定树或者森林34/50树的存储父指针表示法35/50父指针表示法父指针(parentpointer)表示法：每个结点只保存一个指针域指向其父结点.如果两个结点到达同一根结点，它们一定在同一棵树中。36/50父指针数组表示法父节点索引标记结点索引37/50等价类的并查

（UNION/FIND）算法

并查算法包含两种基本操作：判断两个结点是否在同一个集合中，查找一个给定结点的根结点的过程称为FIND归并两个集合，这个归并过程常常被称为UNION整个操作以“UNION/FIND算法”（也可以翻译为“并查算法”）命名38/50UNION/FIND算法示例10个结点A、B、C、D、E、F、G、H、J、K和它们的等价关系（A,B）、(C,K)、(J,F)、(H,E)、(D,G)、(K,A)、(E,G)、(H,J)39/50UNION/FIND算法示例对这5个等价对的处理结果

（A,B）、(C,K)、(J,F)、(H,E)、(D,G)40/50UNION/FIND算法示例对两个等价对（K，A）和（E，G）的处理结果

41/50UNION/FIND算法实现循环链表的思想root[]标识顶点集合的顶点索引next[]指示链表中的下一个顶点length[]指示链表中的顶点数目42/50UNION/FIND算法示例(一)012435root012345next012345length111111vertices012345union(0,1)012435root002345next102345length211111vertices012345union(4,3)43/50UNION/FIND算法示例(二)25root002445next102435length211121vertices012345root004445next103425length211131vertices012345union(2,3)014301524344/50UNION/FIND算法示例(三)root004440next503421length311131vertices012345243501015root004445next103425length211131vertices012345union(0,5)24345/50UNION/FIND算法示例(四)root004440next503421length311131vertices012345243501union(2,5)root444444next203451length311161vertices01234524350146/50UNION/FIND定义classUFSets{private:

intn;

int*root;

int*next;

int*length;public:

UFSets(intsize);

int

Find(intv); voidUnion(int

v,intu);};47/50UNION/FIND算法initialize()fori=0to|v|-1

root[i]=next[i]=i;

length[i]=1;48/50UNION/FIND算法（续）union(intv，intu)

if(root[u]==root[v])return;elseif(length[root[v]]<length[root[u]])

rt=root[v];

length[root[u]]+=length[rt];

root[rt]=root[u];

for(j=next[rt];j!=rt;j=next[j])