第六章树和二叉树剖析.doc

第六章 树和二叉树 前面所学是线性结构，其本质在于：中，除开首尾元素外，每一个元素之前驱与后继均是唯一的。 非线性结构的本质在于：扩展了后继与前驱的这一唯一性约束。 线性结构的树扩展：取消线性结构的后继唯一性，则变成所谓树结构。 线性结构的图扩展：同时取消前驱和后继的唯一性约束，则变成图结构。（第七章） 日常生活中的树结构实例： 树结构示意图 家谱；各种社会组织机构的结构；源程序的语法结构树；棋盘状态树；… 6-1树的定义及基本术语 树(Tree)：由个结点的有限集合构成()。 时称为空树(Null tree)； 时，只存储一个根结点(Root)； 时，由根及其个子树(Subtree)构成。 嵌套集合表示法 A (B (E (K, L)), C (G), D (H (M), I, J)) 广义表表示法 如图所示。 注：树定义的递归特性！ 树的表示方法 ① 树的层次结构表示法：以根、子树的形式表示。 ② 树的嵌套集合表示法：任何两集合或不相交或一个包含另外一个。 ③ 广义表表示法：把根作为表的名字写在表的左边，然后一层层嵌套进去。 ④ 凹入表示法：长的表示父辈以上的结点，短的表示子辈以下的结点。 有关树结构描述的基本术语 树结点(Tree Node)； 分枝结点(Node)/非终端结点/内部结点（度不为零的结点）； 结点的度(Degree)：结点的子树个数 叶子结点(Leaf)/中终端结点(Terminal Node)（度为零的结点） A B E K L F C G D H I J M 凹入表示法 树的度：树中结点之最大度值 孩子（Child）结点：结点的子树的根 双亲结点（Parent）结点：结点的父亲结点 兄弟（Sibling）：同属一父亲结点的孩子结点 祖先结点：当前结点到根结点路径上的所有结点 子孙结点：从当前结点到其下的所有结点 结点的层次：根算1，其下逐层加1的层次信息值 堂兄弟：双亲在同层的结点 树的深度(Depth)：树中结点深度的最大值 有序树：将结点的子树之间看成是有序的关系时，如自右向左，或自左向右等 无序树：结点的子树根结点之间没有次序关系的树 有序树的第一个孩子和最后一个孩子： 森林(Forest)：颗互不相交的树的集合（）。例如树的子树集合。 注：树和森林可以相互递归定义。 如：F表示森林，则Tree=(root,F)，其中，root是数据元素（根），F是m棵互不相交的子树（m=0）构成的森林。表示为，为root的第棵子树。时，。 有关树的ADT定义 ADT Tree { 数据对象：是具有相同特性的数据元素之集合。 数据关系： ，则称为空树()。 ，则。 ，，则是如下二元关系： ① ，则是唯一的没有前驱的数据元素； ②，则存在一个划分，，有（即各划分之间互不相交）。，都唯一地，使得（即是的子结点）； ③ 对的划分，关系也存在一个唯一的划分，，，其中，是一棵以为根的树。 注：即与之对应；同时，时，。 基本操作： InitTree(T); DestroyTree(T);//销毁树结构，并回收存储空间 CreateTree(T,definition); //definition表示构造树结构的条件（定义） ClearTree(T);//将树清为空树 TreeEmpty(T); //空时返回1，否则返回0 TreeDepth(T); //根为1 Root(T); Value(T,cur_e);//返回树中结点cur_e的值 Assign(T,cur_e,value);//将value值赋给结点cur_e Parent(T,cur_e); //返回cur_e的父结点 LeftChild(T,cur_e);//返回cur_e的最左孩子结点 RightSibling(T,cur_e); //返回cur_e的右边兄弟结点 InsertChild(T,p,i,c); //将c结点插入树T结点之第i棵树处 DeleteChild(T,p,i); //删除树T中结点p的第i棵子树 TraverseTree(T,visit()); //遍历树中结点，并