资源描述：
《数据结构讲义第6章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树树是计算机算法最重要的非线性结构。树中每个数据元素至多有一个直接前驱，但可以有多个直接后继。树是一种以分支关系定义的层次结构。§6.1树的基本概念一、树（Tree）的定义a.树是n(≥0)结点组成的有限集合。{N.沃恩}(树是n(n≥1)个结点组成的有限集合。{D.E.Knuth})在任意一棵非空树中：⑴有且仅有一个没有前驱的结点----根(root)。⑵当n>1时，其余结点有且仅有一个直接前驱。⑶所有结点都可以有０个或多个后继。b.树是n(n≥0)个结点组成的有限集合。在任意一棵非空树
2、中：⑴有一个特定的称为根（root）的结点。⑵当n>1时，其余结点分为ｍ（ｍ≥0）个互不相交的子集T1，T2，…，Tm。每个集合本身又是一棵树，并且称为根的子树（subtree）树的固有特性---递归性。即非空树是由若干棵子树组成，而子树又可以由若干棵更小的子树组成。树的基本概念（3）中有13个结点，其中Ａ是树根，其余结点分成三个互不相交的子集。Ｔ1={B,E,F,K,L}Ｔ2={C,G}Ｔ3={D,H,I,J,K}T1,T2,T3都是根A的子树，它们本身又是一棵树。T1:根B{E,K,L}{F}根E{
3、k}{L}T2:根C{G}T3:根D{H,M}{I}{J}根H{M}T=Null⑴AT⑵ABCDEFGIJHT⑶KLM树的基本操作二、树的基本操作1、InitTree(&T)初始化2、DestroyTree(&T)撤消树3、creatTree(&T,F)按F的定义生成树4、ClearTree(&T)清除5、TreeEmpty(T)判树空6、TreeDepth(T)求树的深度7、Root(T)返回根结点8、Parent(T,x)返回结点x的双亲9、Child(T,x,i)返回结点x的第i个孩子10、Ins
4、ertChild(&T,&p,i,x)把x插入到P的第i棵子树处11、DeleteChild(&T,&p,i)删除结点P的第i棵子树12、traverse(T)遍历树的基本术语树的结点：包含一个数据元素及若干指向子树的分支。●结点的度:结点拥有子树的数目●叶结点:度为零的结点●分枝结点:度非零的结点●树的度:树中各结点度的最大值●孩子:树中某个结点的子树的根●双亲:结点的直接前驱●兄弟:同一双亲的孩子互称兄弟●祖先:从根结点到某结点j路径上的所有结点（不包括指定结点）。●子孙:某结点的子树中的任一结点称
5、为该结点的子孙●结点层次:从根结点到某结点j路径上结点的数目（包括结点j）●树的深度:树中结点的最大层次●有向树：结点间的连线是有向的。我们所讲的树都是有向的。●有序树:若树中结点的各子树从左到右是有次序的,称该树为有序树,否则为无序树●森林:由m棵互不相交的树构成F=(T1,T2,.......Tm)一棵树去掉根结点后就表成了森林。对森林加上一个结点，并从该结点引边到各树的根结点就变成了森林。树的逻辑表示１、结点和结点间的连线表示法ABCDEFGIJHTKLM２、文式图表示法----集合嵌套。树的逻辑
6、表示４、凹式表示法----层次表示。３、广义表表示法----递归表示。(A（B（E（J，K，L），F），C（G），D（H（M），I）））§6.2二叉树一、二叉树的定义二叉树是ｎ（ｎ≥0）个结点的有限集合。此集合或为空，或由一个根结点加上至多两个互不相交的左右两个子树组成。结点的度最大为２。子树有左右之分，不能颠倒。二叉树可以有五种基本形态：ABtreeBtree=NullABtreeABtreeABtree二叉树的基本运算initBiTree(&T)初始化Root(T)返回根结点Parent(T,x)返
7、回结点x的双亲LeftChild(T,x)返回结点x的左孩子RighChild(BT,x)返回结点x的右孩子creatbiTree(&T)生成一棵二叉树树InsertLChild(&T,y,x)把x作为y的左子树插入InsertRChild(&T,y,x)把x作为y的右子树插入DelLChild(&T,y)删除结点y的左子树DelRChild(&T,y)删除结点y的右子树Traverse(T)遍历二叉树clearBiTrr(&T)把二叉树置成空树二叉树的性质【性质1】二叉树的第i层结点数最多为2i-1个
8、（i>0）。【性质2】深度为Ｋ的二叉树至多有２k-1个结点(K>0)。【性质3】对任何一棵二叉树，设ｎ0,ｎ1,ｎ2分别是度为0,1,2的结点数，则有：ｎ0＝ｎ2+1证明:∵n=n0+n1+n2(n为结点总数)b=n1+2n2(b为分支总数)b=n-1(除根结点外,任一结点都有分支连入父结点)∴n=b+1=n1+2n2+1=n0+n1+n2整理得:n0=n2+1二叉树的性质满二叉树：深度为k且有2k-1个结点的二叉树。特点：1、每一层上的结
