8

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 26 日 1

树及其抽象数据类型 树的实现 树林林 2

树的 几种不不同表现形式 3

4

html head body meta title h1 ul h2 li li a 5

树是 n(n 0) 个结点的有限集 T,T 非空时满 足 : 有且仅有 一个特殊的称为根 (root) 的结点 r; 除根结点外, 其余结点可分为 m(m 0) 个互不不相交的 非空有限集 T 1,T 2,,T m, 其中每个集合 又是 一棵 非空树, 称为 r 的 子树 (subtree) 关于 子树 结点数为 0 的树称为空树 一棵 非空树可以没有 子树 (m=0), 即这棵树只包含 一个根结点 如有 子树, 则 子树 非空 6

空树 父结点 子结点 路路径 路路径 长度 结点的度数 树的度数 无序树 有序树 结点的次序 最左 子结点 长 子 次 子 右兄弟 7

ADT Tree is operations Tree createemptytree(void); Tree constree(node p, Tree t1, Tree ti); int isnull(tree t); Node root(tree t); Node parent(node p); Tree leftchild(tree t); Tree rightsibling(tree t); End ADT Tree 8

深度优先周游 : 先根次序 :A B D E I J F C G H 后根次序 :D I J E F B G H C A 广度优先周游 : 能否确定树结构? 如何确定? A B C D E F G H I J B C A D E F G H I J 9

/* 按先根次序周游树的递归算法 */ void preorder(tree t) { Tree c; if (t==null) return; visit( root(t) ); c = leftchild ( t ); while (c!=null) {preorder ( c ); c = rightsibling ( c ); } } 10

void npreorder ( Tree t ) { Tree c = t; Stack s = createemptystack ( ); /* 栈元素的类型是 Tree */ do{ while ( c!=null ) { visit ( root(c) ); push ( s, c ); c = leftchild ( c ); } while ((c==null)&&(!isemptystack(s))) { c = rightsibling(top(s)); pop(s); } } while(c!=null); } 11

/* 按后根次序周游树的递归算法 */ void postorder( Tree t ) { Tree c; if (t==null) return; c = leftchild ( t ); while (c!=null) { postorder ( c );c = rightsibling ( c ); } visit(root(t) ); } 12

void levelorder(tree t) { Tree c; } Queue q; /* 队列元素的类型为 Tree */ q = createemptyqueue(); c =t; if (c==null) return; enqueue(q,c); while (!isemptyqueue(q)) { c = frontqueue(q); dequeue(q); visit( root(c) ); c = leftchild( c ); while (c!=null){ enqueue(q,c); c = rightsibling( c ); } } 13

子结点表示法 父指针表示法 子表表示法 长 子- 兄弟表示法 14

树的最基本表示 方法是 子结点表示法, 其基本设计与 二叉树的左右指针表示法类似 : 用 一个数据单元表示结点, 通过结点间的指针表示树结构 在 m 度结点表示的 n 个结点的树中, 恰有 n (m 1)+1 个空树引 用域 15

树中除根以外的每个结点都有唯 一的 一个 父结点 根据这 一特性, 可 用 一组连续的存储空间, 即 用 一个顺序表存储树中的各个结点 表中的每个元素包括结点本身的信息以及本结点的 父结点在表中的下标 16

结点的结构可定义为 : struct ParTreeNode{ DataType info; /* 结点中的元素 */ int parent; /* 结点的 父结点位置 */ }; 树的类型定义为 : struct ParTree{ int MAXNUM; /* 树中最 大结点个数 */ int n; /* 树中已有结点的个数 */ struct ParTreeNode * nodelist; /* 存放树中结点的数组 */ }; typedef struct ParTree * PParTree; / 树类型的指针类型 */ 17

问题 : 1) 求结点的 子结点和兄弟就需要查询整个表 2) 没有表示出结点之间的左右次序, 无法求树中某个指定结点的最左 子结点和右兄弟结点等基本运算 改进 方法是按 一种周游次序在表中存放结点, 其中较常 见的 一种 方法是依次存放树的先根序列列 18

A B C D E F G H I J info parent 0 A -1 1 B 0 2 D 1 3 E 1 4 H 3 5 I 3 6 J 3 7 C 0 8 F 7 9 G 7 19

/* 在 父指针表示的树中求右兄弟结点的位置 */ int rightsibling_partree(ppartree t, int p) { int i; if (p>=0 && p<t->n) for (i=p+1;i<t->n;i++) if (t->nodelist[i].parent==t->nodelist[p].parent) return i ; return -1; } /* 在 父指针表示的树中求最左 子结点的位置 */ int leftchild_partree(ppartree t, int p) { if (t->nodelist[p+1].parent==p) return(p+1); else return -1 ; } 20

父指针表示 方法的主要优点是存储空间 比较节省, 对 求某个结点的 父 母和求某个结点的最左 子结点操作都 很 方便便, 但是对求某个结点的右兄弟运算 比较慢 21

把整棵树表示成 一个结点表 结点表中的每个元素 又包含 一个表, 它记录了了这个结点的所有 子结点的位置, 称为 子表 ( 或者称为边表 ) 结点表的 长度即树中结点的个数, 一般 用 一维数组顺序存储 ; 结点表中除了了要保存元素本身的信息外, 还要保存 子表的表头链接 而 子表的 长度依赖于各结点的度数, 所以各不不相同, 一般 用单链表表示 ; 子表中结点的链接顺序是按其在树中从左到右的次序进 行行的 22

23

struct EdgeNode { /* 子表中结点的结构 */ int nodeposition; /* 子结点在结点表中的位置 */ struct EdgeNode *link; /* 指向下 一个 子表中的结点 */ }; struct ChiTreeNode { /* 结点表中结点的结构 */ DataType info; /* 结点本身的信息 */ struct EdgeNode *children; /* 本结点 子表的头指针 */ }; 24

struct ChiTree { /* 树结构 */ int MAXNUM /* 树中最 大结点个数 */ int root; /* 根结点的下标 */ int n; /* 实际结点个数 */ struct ChiTreeNode * nodelist; /* 结点表 */ }; typedef struct ChiTree * PChiTree; 25

与 父指针表示法类似, 通常树结点表中的结点也按某种遍历序排列列 由于还有 子结点表, 通过它们可以直接找到相关 子结点, 各种找 子结点的操作 ( 求最左 子结点 找全部 子结点等 ) 实现都 比较 方便便 但求某个结点的 父结点和右兄弟实现起来 比较费事, 因为要找某结点的 父结点必须依次检查哪个结点的 子表中是否包含该结点, 而要找某结点的右兄弟时, 则 首先要找到其 父结点, 然后再从 父结点的 子表中找寻它的右兄弟结点 26

int parent_chitree(pchitree t, int p) { int i; struct EdgeNode *v; for (i=0;i<t->n;i++) { } } /* 逐个检查树的各个结点, 是不不是 父结点 */ v=t->nodelist[i].children; /* 若检查的结点 子表中有 p, 则返回值是该结点的位置 */ while (v!=null) if (v->nodeposition==p) return i ; else v=v->link; return(-1); /* 无 父结点, 则返回值为 -1 */ 27

int rightsibling_chitree(pchitree t, int p) { int i; struct EdgeNode *v; for (i=0;i<t->n;i++){ v = t->nodelist[i].children; while (v!=null) if (v->nodeposition==p) if (v->link==null)return(-1); else return(v->link->nodeposition); else v=v->link; } return(-1); } 28

在这种存储结构中, 类型定义如下 : struct CSNode; /* 树中结点结构 */ typedef struct CSNode * PCSNode; /* 结点的指针类型 */ struct CSNode { /* 结点结构定义 */ DataType info; /* 结点中的元素 */ PCSNode lchild; /* 结点的最左 子结点的指针 */ PCSNode rsibling; /* 结点的右兄弟的指针 */ }; typedef struct CSNode * CSTree; /* 树类型定义 */ 29

A t A B C D E F G H I J D B F E C G H I J 30

采 用 长 子 - 兄弟表示法表示树时, 除找 父结点和从 子树构造树之外, 其余的基本运算实现起来都是 比较简单的 甚 至可以 用 一个简单的表达式或赋值语句句代替函数调 用 找结点的全部 子结点也很容易易 : 先找到 长 子, 再由 子结点的 rsibling 字段逐个地找 子结点的右兄弟 长 子 - 兄弟表示法的缺点是寻找某个指定结点的 父结点 比较麻烦, 需要对树进 行行周游, 周游时检查被访问的结点的各个 子结点的位置是不不是指定结点 31

树林林是由零个或多个不不相交的树所组成的集合 树林林中所有树也是有序的, 彼此称为兄弟 与 自然界的树林林有所不不同, 这 里里的树林林可以是 一个空集, 也 可以只由 一棵树构成 如果从 一棵树中将根结点 ( 连同根结点到各 子结点的边 ) 删除, 便便得到 一个树林林 32

先根次序周游 : 首先访问树林林中第 一棵树的根结点 ; 然后先根次序周游第 一棵树除去根结点剩下的所有 子树构成的树林林 ; 最后先根次序周游除去第 一棵树之后剩下的树林林 后根次序周游 : 首先后根次序周游第 一棵树的根结点的所有 子树构成的树林林 ; 然后访问树林林中第 一棵树的根结点 ; 最后后根次序周游除去第 一棵树之后剩下的树林林 33

前 面所有树的表示 方法都可以推 广到树林林 下 面给出 用这些 方法表示 一个树林林的例例 子 34

35

36

37

在树林林 ( 包括树 ) 与 二叉树之间有 一个 自然的 一 一对应 的关系 任何树林林都唯 一地对应到 一棵 二叉树 ; 任何 二叉树也都唯 一地对应到 一个树林林 38

39

首先在所有相邻的兄弟结点之间加 一条线 ; 然后对每个 非终端结点, 只保留留它到其最左 子结点的连线, 删去它与其它 子结点之间原有的连线 ; 最后以根结点为轴 心, 将整棵树顺时针旋转 一定 角度 ( 如 45 度 ), 使其层次分明 40

把树林林 F 看作树的序列列 :F = T 1,T 2,,T n, 对构造应于 F 的 二叉树 B(F) 的定义可以递归描述如下 : 若 n = 0, 则 B(F) 为空 ; 若 n>0, 则 B(F) 的根是 T 1 的根 w 1, B(F) 的左 子树是 B(T 11,T 12,,T 1m ), 其中 T 11,T 12,,T 1m 是 T 1 的 子树 ; B(F) 的右 子树是 B(T 2,,T n ) 41

42

(1) 若某结点是其 父 母的左 子结点, 则把该结点的右 子 结点, 右 子结点的右 子结点, 都与该结点的 父 母 用 ( 虚 ) 线连起来 ; (2) 去掉原 二叉树中所有 父 母到右 子结点的连线 ; 整理理由 (1) (2) 两步所得到的树或树林林, 使之结构层次 分明 43

设 B 是 一棵 二叉树,r 是 B 的根,L 是 r 的左 子树,R 是 r 的右 子树, 则构造对应于 B 的树林林 F(B) 可作如下严格的递归描述 : 若 B 为空 二叉树, 则 F(B) 是空的树林林 ; 若 B 不不为空 二叉树, 则 F(B) 是 一棵树 T1 加上树林林 F(R), 其中树 T1 的根为 r,r 的 子树为 F(L) 44

树是 一种常 见的树形结构, 它常 用的存储表示有四种 : 子结点表示法 父结点表示法 子表表示法和 长 子 - 兄弟表示法 周游是树上的重要操作, 主要有深度优先和 广度优先两种 方式, 在深度优先中 又分为先根次序周游和后根次序周游 由于树 / 树林林与 二叉树之间存在对应关系, 所以常常把树与树林林转换为 二叉树处理理 这使得 二叉树的讨论和它的 llinkrlink 表示更更加重要 二叉树和树的各种存储 方式都应该包 ( 隐 ) 含所有的结点和结点之间关系的信息, 不不同的表示原则上应该可以相互转换 45