树和二叉树的定义

《树和二叉树的定义》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10讲树和二叉树的定义主讲人：陈红丽对比树型结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱（双亲）多个后继（孩子）)树的定义树是n（n≥0）个结点的有限集合，在任一棵非空树中：(1)有且仅有一个称为根(root)的结点。(2)其余结点可分为m个互不相交的集合，而且其中的每一个集合本身又是一棵树，称为根的

2、子树。ABCDEFGHIJMKL结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点DHIJM树的基本术语(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟结点祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，第l层的结点的子树根结点的层次为l+1树中叶子结点所在的最大层次任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根

3、结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF有序树：子树之间存在确定的次序关系。无序树：不考虑子树的顺序。树的抽象数据类型的定义ADTTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，则称为空树；　　若D中仅含一个数据元素，则关系R为空集；　　否则R={H}，(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)当n>1时，其余数据元素可分为m(m>0)个互不相交的(非空)有限集T1,T2,…,Tm

4、,其中每一个子集本身又是一棵符合本定义的树，称为根root的子树，每一棵子树的根xi都是根root的后继，即∈H,i=1,2,…,m。基本操作：}ADTTree基本操作：{结构初始化}InitTree(&T);操作结果：构造空树T。CreateTree(&T，definition);初始条件：definition给出树T的定义。操作结果：按definition构造树T。{销毁结构}DestroyTree(&T);初始条件：树T存在。操作结果：销毁树T。{引用型操作}TreeEmpt

5、y(T);初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树T存在。操作结果：返回T的根。Value(T，cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Parent(T，cur_e);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChild(T，cur_e

6、);初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回"空"。RightSibling(T，cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回“空”。TraverseTree(T，visit());初始条件：树T存在，visit是对结点操作的应操作结果：按某种次序对T的每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。{加工型操作}Assi

7、gn(T，cur_e，value);初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值为value。ClearTree(&T);初始条件：树T存在。操作结果：将树T清为空树。InsertChild(&T，&p，i，c);初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度＋1，非空树c与T不相交。操作结果：插入c为T中p所指结点的第i棵子树。DeleteChild(&T，&p，i);初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除T中p所

8、指结点的第i棵子树。二叉树定义或为空树，或是由一个根结点和两棵互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。特性二叉树中每个结点最多有两棵子树；二叉树每个结点的度小于等于2子树有左右之分，不能颠倒——有序树二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念二叉树与度为2的树相同吗？为什么？ABCDEFGHK根结点左子树右子树ADTBinaryTree{数据对象：D是具有相同特性的数据元素的集合。数据关系：若D为空集，称BinaryTree为空二叉树；