《树和二叉树》ppt课件

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

1、第6章树和二叉树1主要内容§6.1树的定义和基本术语§6.2二叉树§6.3遍历二叉树§6.4线索二叉树§6.5树和森林§6.6赫夫曼树及其应用2§6.1树的定义和基本术语(1)树（Tree）是n(n≥0)个结点的有限集。在任意一棵非空树中:A、有且仅有一个称为根的结点；B、当n≥2时，其余结点分为m(m≥0)个互不相交的子集，每个子集本身又是一棵树，称为根的子树。以上是一个递归的定义——在树的定义中又用到了树的概念，由此可见递归是树的固有特性。ABMLKJIHGFEDC3§6.1树的定义和基本术语(2)ABMLKJIHGFEDC树根：A每个子集都是满足树的定义的树，称为A

2、的子树－－B子树、C子树、D子树。树根A没有直接前驱；其余结点有且仅有一个直接前驱有，有0个或多个直接后继。三个互不相交的子集：{B,E,F,K,L}{C,G}{D,H,I,J,M}树的特征：层次性和分支性4§6.1树的定义和基本术语(3)结点的度：结点的非空子树个数树的度：树内各结点度的最大值分支结点(非终端结点)：度非0的结点叶子结点(终端结点)：度为0的结点孩子：结点的子树的根双亲：孩子的直接前驱结点兄弟：同一个双亲的孩子结点互称为兄弟子孙：以某结点为根的子树中的任一结点祖先：从根到该结点所分支上的所有结点堂兄:双亲在同一层的结点5结点的层次：从根开始定义起，根为第

3、一层，根的孩子为第二层。若某结点在第L层，则其子树的根在第L+1层。树的深度（高度）：结点层次的最大值有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。森林：m（m≥0）个树的集合ABMLKJIHGFEDCTree=(A(B(E(K,L),F),C(G),D(G,H(M),I,J)))§6.1树的定义和基本术语(4)6树的基本操作：构造空树InitTree(&T);销毁树DestroyTree(&T);创建树CreateTree(&T,definition);清空树ClearTree(&T);判断空树TreeEmp

4、ty(T);求树的深度TreeDepth(T);求双亲parent(T,cur_e);求长子LeftChild(T,cur_e);求右邻兄弟RightSibling(T,cur_e);插入子树InsertChild(&T,&p,i,c);删除子树DeleteChild(&T,&p,i);遍历树TraverseTree(T,visite());§6.1树的定义和基本术语(5)7§6.2二叉树二叉树的定义二叉树的性质二叉树的存储结构8§6.2.1二叉树的定义(1)二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有

5、左右之分，其次序不能任意颠倒。二叉树可以为空，称为空二叉树;非空二叉树一定有两个子树；左、右子树有次序关系，不能互换；二叉树可以有5种基本形态：二叉树不是结点的度都不超过2的有序树.§6.2二叉树根左子树右子树Ø根根根9§6.2.1二叉树的定义(2)具有三个结点的树与二叉树§6.2二叉树A、三个结点的树有两种不同的形态B、三个结点的二叉树有五种不同的形态树型结构的共同特征：层次性、分支性10§6.2.1二叉树的定义(3)二叉树的基本操作初始化空二叉树InitBiTree(&T)销毁二叉树DestroyBiTree(&T)创建二叉树CreateBiTree(&T,defin

6、ition)清空二叉树ClearBiTree(&T)判断空二叉树BiTreeEmpty(T)求二叉树深度BiTreeDepth(T)求双亲parent(T,e)求左孩子LeftChild(T,e)求右孩子RightChild(T,e)求左兄弟LeftSibling(T,e)求右兄弟RightSibling(T,e)插入子树InsertChild(T,p,LR,c)删除子树DeleteChild(T,p,LR)先序遍历二叉树PreOrderTraverse(T,visite())中序遍历二叉树InOrderTraverse(T,visite())后序遍历二叉树PostOrd

7、erTraverse(T,visite())按层次遍历levelTraverse(T,visite())§6.2二叉树11§6.2二叉树二叉树的定义二叉树的性质二叉树的存储结构12§6.2.2二叉树的性质(1)性质1在二叉树的第i层上至多有2i-1个结点(i≥1)；性质2深度为k的二叉树上至多有2k-1个结点(k≥1)；性质3设任意一棵二叉树中有n0个度为0的结点，n2个度为2个结点，则有：n0=n2+1；§6.2二叉树满二叉树：一棵深度为k且有2k－1个结点的二叉树。即：所有非终端结点的度都等于2，且所有树叶都分布在同一个层