资源描述：
《数据结构-第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5树与等价问题6.6赫夫曼树及其应用6.7回溯法与树的遍历6.8树的计数2021/9/716.1树的定义和基本术语树（Tree)的定义：树是n(n>=0)个结点的有限集。在任意一棵非空树中：(1)有且仅有一个特定的称为根(Root)的结点；(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树（SubTree）。（注意：上述的定义也是递归的。）2021/9/72CH.66.1树的定义和基本术语基本
2、概念和术语根、子树、结点、非终端结点（分支结点）、终端结点（叶结点）。2021/9/73CH.66.1树的定义和基本术语基本术语树的结点(node)：包含一个数据元素及若干指向其子树的分支（或子树）。有根结点、叶结点、分支结点之分。结点的度(degree)：结点的子树个数。叶子(leaf)或终端结点：度为0的结点。非终端结点或分支(branch)结点：度不为0的结点。树的度(degree)：树中结点的最大度。孩子(child)和双亲(parent)：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。2021/9/74CH.66.1树的定义和基本术语基本术语兄
3、弟(sibling)：同一个双亲的孩子结点之间互称兄弟结点。结点的祖先(ancestor)：从根到该结点所经分支上的所有结点。结点的子孙(descendant)：以某结点为根的子树中的任一结点都称为该结点的子孙。结点的层次(level)：从根开始定义起，根为第一层，根的孩子为第二层。堂兄弟：其双亲在同一层的结点互为堂兄弟。树的深度(depth)或高度：树中结点的最大层次。有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。森林：是m(m>=0)棵互不相交的树的集合。2021/9/75CH.66.1树的定义和基本术语基本概念根：
4、树中无前驱的结点。结点的度：后继结点的个数。叶子或终端结点：无后继的结点。非终端结点或分支结点：有后继的结点。结点的直接后继是该结点的孩子（儿子）。结点的直接前驱是该结点的双亲。具有相同直接前驱的结点之间互称兄弟。结点的祖先包括该结点所有的前驱结点。结点的子孙包括该结点的所有的后继结点。2021/9/76CH.66.1树的定义和基本术语树的图示结点－分支图集合、广义表表达式、凹入表示法（P120)。ACGT2DHIT3JMBEFLKT12021/9/77CH.6树的表示bacghdefij嵌套集合表示嵌套括号表示ijdfghabcea(b(d,e(i,j),f),c(g
5、,h))2021/9/78CH.66.1树的定义和基本术语树的特征每个结点至多有一个直接前驱，可以有多直接后继。树能表示具有层次性的对象。2021/9/79CH.66.2二叉树6.2.1二叉树的定义二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点)。二叉树的子树有左右之分,其次序不能任意颠倒。2021/9/710CH.66.2二叉树二叉树可看成是一棵特殊的“树”：树的结点个数有些定义规定至少为1，而二叉树的结点个数可以为0。树中结点的最大度数没有限制，二叉树结点最大度数为2。一般有序树的结点只有先后之分，无左、右之分，二叉树的结
6、点子树有明确的左、右之分。2021/9/711CH.66.2.1二叉树的定义ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:基本操作P:InitBiTree(&T);DestroyBiTree(&T);CreateBiTree(&T,definition);ClearBiTree(&T);BiTreeEmpty(T);BiTreeDepth(T);Root(T);Value(T,e);Assign(T,&e,value);2021/9/712CH.66.2.1二叉树的定义Assign(T,&e,value);Parent(T,e);
7、LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);InsertChild(T,p,LR,c);DeleteChild(T,p,LR);PreOrderTraverse(T,visit());InOrderTraverse(T,visit());PostOrderTraverse(T,visit());LevelOrderTraverse(T,Visit());}ADTBinaryTree2021/9/713CH.66.2.1二叉树的定义二叉树的五种形态：空二
