《树及其应用》PPT课件

《《树及其应用》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008年8月第五章树及其应用《数据结构》制作者：叶洁第五章树及其应用树的定义和基本术语5.13.23.35.2二叉树5.3树和森林5.4特殊二叉树3.35.5二叉树的其他操作遍历二叉树5.6§5.1树的定义和基本术语一、树的定义前提：树是n（n>=0）个结点的有限集。任意一棵非空树中：（1）由且仅有一个称为根的结点；（2）当n>1时，其余所有结点分为m棵（m>=0）互不相交的有限集T1T2T3等，每一个子集又是一棵树，称为根的子树。ABCDEFGHIJKLMNOPQR§5.1树的定义和基本术语二、树型结构的特点1、由且仅有一个结点没有前驱，该结点被称为树的根。

2、2、除根结点外，其余结点由且仅有一个直接前驱结点。3、包括根结点，每个结点可以有任意多个后继三、树的表示1、直观法2、集合法3、凹入表4、广义表表示ABCFGJKLABCGFJKLABFJKLCG（）A(B(F(J,K(L),))C(,G))）§5.1树的定义和基本术语四、树的基本术语1、结点的度结点拥有的子树的数目称为该结点的度2、树的度树中所有结点的度的最大值称为树的度3、叶子结点度等于0的结点称为叶子结点或终端结点4、分支结点度大于0的结点称为分支结点或非终端结点5、结点的关系孩子结点：某结点的直接后继双亲结点：某结点的直接前驱兄弟结点：同一双亲的结点互称

3、为兄弟祖先：从根结点到达该结点的路径上经过的所有结点6、结点的层数和树的深度结点的层数：从根开始为1，到该结点所经历的层数树的深度：树中所有结点的最大层数7、有序树和无序树有序树：树中各结点的子树是按照一定的次序从左向右安排的称为有序树无序树：否则称为无序树8、森林：是m（m>=0）棵互不相交的数的集合ABCFGKLM§5.2二叉树一、二叉树的定义1、二叉树：树的度小于等于2的有序树2、左子树、右子树3、左孩子、右孩子二、二叉树的形态ABCFGKLMAABFKLMACGL§5.2二叉树三、二叉树的性质性质1：二叉树上终端结点数等于双分支结点数加1。性质2：二叉树

4、上第i层上至多有个结点性质3：深度为h的二叉树至多有个结点满二叉树：一颗深度为k的二叉树且有个结点的二叉树完全二叉树：在一棵二叉树中，除最后一层外，其余层都是满的，并且最后一层或者是满的，或者是在右边缺少若干个结点。2i-12h-12k-1先上后下：上不满下不准有先左后右完全二叉树左不满右不准有没有左孩子不准有右孩子§5.2二叉树性质4：具有n个结点的完全二叉树的深度为「log（n+1）或logn+1性质5：对完全二叉树中编号为i的结点有如下性质：（1）若其有左孩子，则左孩子的编号为2i，若其有右孩子，择右孩子的编号为2i+1（2）除根结点外，若一个结点的编号为

5、i，则它的双亲结点的编号为i/2（3）若i<=n/2,则编号为i的结点为分支结点，否则为叶子结点（4）若n为奇数，则每个分支结点既有左孩子又有右孩子，若n为偶数，则编号最大的分支结点（n/2）只有左孩子，没有右孩子，其余分支结点既有左孩子，又有右孩子§5.2二叉树1、顺序存储结构2、链式存储结构（1）、结点结构（2）、结点定义StructBTreeNode{ElemTypedata;BTreeNode*left,*right;}3、二叉树存储表示leftdatarightABCFGKMAB^^CF^M^^K^^G§5.3遍历二叉树一、遍历的定义用某种方式使数据结

6、构中的所有结点都被访问，且只访问一次二、遍历的方式1、先序遍历二叉树（1）操作若二叉树不空，则a.访问根结点b.先序遍历左子树c.先序遍历右子树（2）算法Voidpreorder(BTreeNode*bt){if(bt!=NULL){visit(bt);Preorder(bt->left);Preorder(bt->right);}}§5.3遍历二叉树2、中序遍历二叉树（1）操作若二叉树不空，则：a.中序遍历二叉树b.访问根结点c.中序遍历二叉树（2）算法Voidinorder(BTreeNode*bt){if(bt!=NULL){inorder（bt->lef

7、t）;Visit(bt);inorder(bt->right);}}§5.3遍历二叉树3、后序遍历二叉树（1）操作若二叉树不空，则：a.后序遍历二叉树b.后序遍历二叉树c.访问根结点（2）算法Voidpostorder(BTreeNode*bt){if(bt!=NULL){postorder（bt->left）;postorder(bt->right);Visit(bt)}}§5.4二叉树其他运算1、初始化二叉树voidinitbtree(BTreeNode*&bt){bt=NULL;}2、按先序次序创建一棵二叉树voidcreatbtree(BTreeNode

8、*&bt){ElemTy