[工学]数据结构 C语言版严蔚敏版第6章 树和二叉树.ppt

;学习提要 ;;线性结构 ;;树形结构;;6 树的定义和基本术语; 树是一种常用的非线性结构。我们可以这样定义：树是n（n≥0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。;K L M;介绍几个概念： 结点： 数据元素的内容及其指向其子树根的分支统称为结点。 结点的度： 结点的分支数。 终端结点（叶子）： 度为0的结点。 非终端结点 ： 度不为0的结点。 结点的层次： 树中根结点的层次为1，根结点子树的根为第2层，以此类推。 树的度： 树中所有结点度的最大值。 树的深度： 树中所有结点层次的最大值。 有序树、无序树： 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。; 森林: 是m（m≥0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 孩子、双亲: 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 子孙: 以某结点为根的子树中的所有结点都被称为是该结点的子孙。 祖先: 从根结点到该结点路径上的所有结点。 兄弟: 同一个双亲的孩子之间互为兄弟。 堂兄弟: 双亲在同一层的结点互为堂兄弟。; 2. 树的基本运算 常用操作： （1）构造一个树 CreateTree (T) （2）清空以T为根的树 ClearTree(T) （3）判断树是否为空 TreeEmpty(T) （4）获取给定结点的第i个孩子 Child(T,node,i) （5）获取给定结点的双亲 Parent(T,node) （6）遍历树Traverse(T) 对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历。;6.2 二叉树 （Binary Tree）; 二叉树是n(n?0)个结点的有限集合。它或为空树(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。;　　1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。【5分】 　　树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。　　树和二叉树的区别有二：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制，当只有一个孩子时，不知为左/右孩子。　　2．树和二叉树之间有什么样的区别与联系？【4分】 　　树和二叉树逻辑上都是树形结构，区别有以上题1所述三点。二叉树不是树的特例。 3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。【10】　　线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为1的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。; 二叉树的基本运算 （1） 构造一棵二叉树 CreateBTree ( BT) （2）清空以BT为根的二叉树 ClearBTree(BT) （3）判断二叉树是否为空 BTreeEmpty(BT) （4）获取给定结点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node) （5）获取给定结点的双亲 Parent(BT,node) （6）遍历二叉树Traverse(BT);A) 二叉树的第 i 层上至多有2 i-1（