第六章树和二叉树第六章树和二叉树树的概念与定义树的概念与定义二叉树二叉树二叉树的遍历与线索化二叉树的遍历与线索化树和森林树和森林哈夫曼树及其应用哈夫曼树及其应用树的计数树的计数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构成，此集合或者为空构成，此集合或者为空集，或者由一个根结点及两棵互不相交集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二的左右子树组成，并且左右子树都是二叉树。叉树。注意：注意：二叉树的子树有左右之分，因此二叉树的子树有左右之分，因此二叉树是一种有序树。二叉树是一种有序树。二叉树的性质：二叉树的性质：...
