第6章-树电子课件.pptx

普通高等教育国家级规划教材《数据结构》（C语言版）;第6章树;2023/8/25;树是由n(n≥0)个结点构成的有限集合，n=0的树称为空树；当n≠0时，树中的结点应该满足以下两个条件：;有序树：

（1）有确定的根；

（2）树根和子树根之间为有向关系;6.1树的基本概念;6.1树的基本概念;结点:数据元素+指向子树的分支

结点的度:分支的个数

树的度:树中所有结点的度的最大值

叶子结点:度为零的结点（终点结点）;分支结点:度大于零的结点（非终端结点）

结点的层次:假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1;从根到结点的路径:

孩子结点、双亲结点、兄弟结点、祖先、子孙;任何一棵非空树是一个二元组

Tree=（root，F）

其中：root被称为根结点，F被称为子树森林;;A(B(E,F),C,D(G,H(J,K),I))

(a)图6.1的括号表示法;;;ADTtree{

数据对象D:具有相同性质的数据元素构成的有限集合;

数据关系R:如果D为空或D仅含一个元素,则R为空;否则,D中存在一个特殊的结点root,称之为根结点,其无前驱;其他结点被分成互不相交的m(m≥0)个集合,分别构成root的m棵子树;若这些子树非空,则它们的根结点rooti均称为整棵树根结点root的后继结点;而每棵子树也是一棵树,因而它们中数据元素间的关系也同样满足数据关系R。

树的基本操作如下:;（1）inittree(T) 初始化一棵树T;

（2）cleartree(T) 若树T已存在,则将它置空,使之成为一棵空树;

（3）emptytree(T) 判断一棵已存在的树T是否是空树,若是返回1;否则返回0;

（4）root(T) 返回树T的根结点;

（5）child(T,a,i) 返回树T中结点a的第i个子女;

（6）parent(T,a) 返回树T中结点a的双亲;;（7）degree(T,a) 返回树T中结点a的度数;

（8）depth(T) 返回树T的高度（深度）;

（9）choose(T,C) 返回树T中满足条件C的某一个结点;

（10）addchild(T,a,i,t1) 表示在树T中将树t1作为结点a的第i棵子树插入;

（11）delchild(T,a,i) 若树T中结点a的第i棵子树存在,则删除它;

（12）createtree(a,F) 构造一棵新树,该树以a为根结点、以森林F中的树为子树;;（13）equaltree(T1,T2) 判断两棵树T1和T2是否相等,若相等,返回1;否则返回0;

（14）numofnode(T) 返回树T中所含结点的个数;

（15）preorder(T) 输出树T前序遍历的结果;

（16）postorder(T) 输出树T后序遍历的结果;

（17）levelorder(T) 输出树T层次遍历的结果;

（18）destroytree(T) 销毁一棵已存在的树T。

}ADTTree;;6.3树的存储结构;#defineMAXSIZE100

typedefchardatatype;/*结点值的类型*/

typedefstructnode/*结点的类型*/

{

datatypedata;

intparent;/*结点双亲的下标*/

}node;;;2.孩子表示法;（1）指针方式的孩子表示法;A;#definem3 /*树的度数*/

typedefchardatatype; /*结点值的类型*/

typedefstructnode

{ /*结点的类型*/

datatypedata;

structnode*child[m];/*指向子女的指针数组*/

}node*tree;

treeroot;;（2）数组方式的孩子表示法;-1;#definem3

#defineMAXSIZE20

typedefchardatatype;

typedefstructnode{

datatypedata;

intchild[m];

}treenode;

treenodetree[MAXSIZE];

introot;

intlength;;（3）链式方式的孩子表示法;A;#defineMAXSIZ