DS06-树树和二叉树VIP专享VIP免费

第六章树和二叉树第六章树和二叉树树的概念与定义树的概念与定义二叉树二叉树二叉树的遍历与线索化二叉树的遍历与线索化树和森林树和森林哈夫曼树及其应用哈夫曼树及其应用树的计数树的计数6.16.1树的概念与定义树的概念与定义树的定义：树的定义：树树(tree)(tree)是是n(n≥0)n(n≥0)个结点的个结点的有限集有限集TT，当，当n=0n=0时，称为空树；当时，称为空树；当n>0n>0时，满足以下条件：时，满足以下条件：（（11）有且仅有一个结点被称为树根（）有且仅有一个结点被称为树根（rooroott）结点；）结点；（（22）当）当n>1n>1时，除根结点以外的其余时，除根结点以外的其余n-1n-1个结点可以划分成个结点可以划分成m(m>0)m(m>0)个互不相交的有个互不相交的有限集限集T1,T2,…T1,T2,…，，TmTm，其中每一个集合本，其中每一个集合本身又是一棵树，称为根的子树身又是一棵树，称为根的子树(subtree)(subtree)。。图6.1结点结点(node)(node)：：表示树中的元素，包括表示树中的元素，包括数据项及若干指向其子树的分支。数据项及若干指向其子树的分支。结点的度结点的度(degree)(degree)：：结点拥有的子树结点拥有的子树的数目。图的数目。图6.16.1中结点中结点AA的度为的度为33。。叶子叶子(leaf)(leaf)：：度为度为00的结点称为叶子的结点称为叶子结点，也称为终端结点。图结点，也称为终端结点。图6.16.1中，叶中，叶子结点有：子结点有：KK，，LL，，FF，，GG，，MM，，II，，JJ。。分支结点分支结点：：度不为度不为00的结点称为分支结的结点称为分支结点，也称为非终端结点。图点，也称为非终端结点。图6.16.1中，非中，非终端结点有：终端结点有：AA，，BB，，CC，，DD等。等。孩子结点孩子结点(child)(child)：：结点的子树的根称结点的子树的根称为该结点的孩子结点。图为该结点的孩子结点。图6.16.1中，结点中，结点AA的孩子结点为的孩子结点为BB，，CC，，DD，结点，结点BB的的孩子结点为孩子结点为EE，，FF。。双亲结点双亲结点(parents)(parents)：：孩子结点的上层孩子结点的上层结点称为该结点的双亲结点。图结点称为该结点的双亲结点。图6.16.1中，中，结点结点II的双亲为的双亲为DD，结点，结点LL的双亲为的双亲为EE。。兄弟结点兄弟结点(sibling)(sibling)：：具有同一双亲结具有同一双亲结点的孩子结点之间互称为兄弟结点。图点的孩子结点之间互称为兄弟结点。图6.16.1中，结点中，结点BB，，CC，，DD互为兄弟，结互为兄弟，结点点KK，，LL互为兄弟。互为兄弟。树的度树的度：：树中最大的结点的度数即为树树中最大的结点的度数即为树的度。的度。图图6.16.1中的树的度为中的树的度为33。。结点的层次结点的层次(level)(level)：：从根结点算起，从根结点算起，根为第一层，它的孩子为第二层……。根为第一层，它的孩子为第二层……。若某结点在第若某结点在第ll层，则其孩子结点就在层，则其孩子结点就在第第l+1l+1层。图层。图6.16.1中，结点中，结点AA的层次为的层次为11，结点，结点MM的层次为的层次为44。。树的高度树的高度(depth)(depth)：：树中结点的最大层树中结点的最大层次数。图次数。图6.16.1中的树的高度为中的树的高度为44。。森林森林(forest)(forest)：：m(m≥0)m(m≥0)棵互不相交棵互不相交的树的集合。的树的集合。有序树与无序树：有序树与无序树：树中结点的各子树从树中结点的各子树从左至右是有次序的（不能互换）则称该树左至右是有次序的（不能互换）则称该树为为有序树有序树，否则称该树为，否则称该树为无序树。无序树。6.26.2二叉树二叉树二叉树的定义：二叉树的定义：二叉树是由二叉树是由n(n≥0)n(n≥0)个个结点的有限集结点的有限集TT构成，此集合或者为空构成，此集合或者为空集，或者由一个根结点及两棵互不相交集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二的左右子树组成，并且左右子树都是二叉树。叉树。注意：注意：二叉树的子树有左右之分，因此二叉树的子树有左右之分，因此二叉树是一种有序树。二叉树是一种有序树。二叉树的性质：二叉树的性质：...