第06章-树、二叉树.ppt

《第06章-树、二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树、二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用6.1树的定义和基本术语树(Tree)是n(n>0)个结点的有限集T，非空树满足以下条件:有且仅有一个特定的称为根(Root)的结点;(2)除根结点外的其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合本身又是一棵树,并且称为根的子树(subtree)树的定义6.1树的定义和基本术语树的定义(b)是只有一个根结点的树;(a)是有13个结点的树,其中A是根,其余结点分成三个互不相交的子树；6.1树的定义和基本术语树的

2、基本术语树的结点：包含一个数据元素及若干个指向其子树的分支结点的度：结点拥有的子树数树的度：树内各结点的度的最大值叶子（终端结点）：度为零的结点非终端结点（分支结点）：度不为零的结点孩子、双亲及兄弟结点：结点的祖先、子孙和堂兄弟：结点的层次和树的深度：有序树和无序树：森林：是m棵互不相交的树的集合6.2二叉树二叉树的定义度不大于2的树称为二叉树。相关术语左子结点、右子结点(a)空二叉树A(b)根和空的左右子树AB(c)根和左子树AB(d)根和右子树ACB(e)根和左右子树二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)性质2：深度为k的二

3、叉树至多有2k-1个结点性质3：对于任何一棵二叉树T，如果其叶子数为n0，度为2的结点数为n2，则n0=n2+1满二叉树：一棵深度为k且有2k-1个结点的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时6.2二叉树二叉树的性质6.2二叉树性质4：具有n个结点的完全二叉树的深度为└log2n┘+1性质5：如果对一棵n个结点的完全二叉树的结点按层序编号，则对任意结点i(1≤i≤n)，有(1)当i=1时，该结点为根，它无双亲结点；(2)当i>1时，该结点的双亲结点编号为└i/2┘；(3)当2i

4、

5、仅被访问一次。其中常见的有三种情况：分别称之为先(根)序遍历，中(根)序遍历和后(根)序遍历。先序(Preorder)遍历若遍历的二叉树为空，执行空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。中序(Inorder)遍历若遍历的二叉树为空，执行空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。后序(Postorder)遍历若遍历的二叉树为空，执行空操作；否则(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。二叉树的遍历abdcegjkhfidbajgkehcfidbjkgheifca后序遍历：左子树

6、右子树根中序遍历：左子树根右子树前序遍历：根左子树右子树6.3遍历二叉树和线索二叉树层次遍历：从上到下从左到右abcdefghijk6.3遍历二叉树和线索二叉树二叉树的遍历遍历序与二叉树的对应前序遍历序+中序遍历序唯一确定二叉树后序遍历序+中序遍历序唯一确定二叉树前序遍历序：abdceghfi中序遍历序：dbagehcfi线索二叉树定义6.3遍历二叉树和线索二叉树lchildLTagdataRTagrchild其中：Ltag=0lchild域指示结点的左孩子1lchild域指示结点的前驱Rtag=0rchild域指示结点的右孩子1rchild域指示结点的后继以

7、这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树.对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化.线索二叉树例：6.3遍历二叉树和线索二叉树线索二叉树中序线索二叉树的遍历6.3遍历二叉树和线索二叉树后继的寻找方法:若结点右标志为1,则右链为线索,指示其后继;否则遍历右子树时访问的第一个结点为其后继,即右子树中最左下的结点。前驱的寻找方法:若结点左标志为1,则左链为线索,指示其前驱;否则遍历左子树时最后访问的一个结点为其前驱。二叉树的线索化线索化的过程即为在遍历的过程中修改

8、空指针的过程.6.3遍历二叉树和线索二