《数据结构——C语言描述》第6章：树

《《数据结构——C语言描述》第6章：树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树树的概念与定义二叉树二叉树的遍历与线索化树和森林哈夫曼树及其应用树的计数6.1树的概念与定义树的定义：树(tree)是n(n≥0)个结点的有限集T，当n=0时，称为空树；当n>0时，满足以下条件：（1）有且仅有一个结点被称为树根（root）结点；（2）当n>1时，除根结点以外的其余n-1个结点可以划分成m(m>0)个互不相交的有限集T1,T2,…，Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。图6.1结点(node)：表示树中的元素，包括数据项及若干指向其子树的分支。结点的度(degre

2、e)：结点拥有的子树的数目。图6.1中结点A的度为3。叶子(leaf)：度为0的结点称为叶子结点，也称为终端结点。图6.1中，叶子结点有：K，L，F，G，M，I，J。分支结点：度不为0的结点称为分支结点，也称为非终端结点。图6.1中，非终端结点有：A，B，C，D等。孩子结点(child)：结点的子树的根称为该结点的孩子结点。图6.1中，结点A的孩子结点为B，C，D，结点B的孩子结点为E，F。双亲结点(parents)：孩子结点的上层结点称为该结点的双亲结点。图6.1中，结点I的双亲为D，结点L的双亲为E。兄弟结点(sibli

3、ng)：具有同一双亲结点的孩子结点之间互称为兄弟结点。图6.1中，结点B，C，D互为兄弟，结点K，L互为兄弟。树的度：树中最大的结点的度数即为树的度。图6.1中的树的度为3。结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层……。若某结点在第l层，则其孩子结点就在第l+1层。图6.1中，结点A的层次为1，结点M的层次为4。树的高度(depth)：树中结点的最大层次数。图6.1中的树的高度为4。森林(forest)：m(m≥0)棵互不相交的树的集合。有序树与无序树：树中结点的各子树从左至右是有次序的（不能互换

4、）则称该树为有序树，否则称该树为无序树。6.2二叉树二叉树的定义：二叉树是由n(n≥0)个结点的有限集T构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。注意：二叉树的子树有左右之分，因此二叉树是一种有序树。二叉树的性质：性质1在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2深度为k的二叉树至多有2k－1个结点（k>=1）。性质3对任意一棵二叉树BT，如果其叶子结点数为n0，度为2的结点数为n2，则n0＝n2＋1。性质4具有n个结点的完全二叉树的深度为【log2n】＋1。（

5、符号【x】表示不大于x的最大整数。）二叉树的性质：性质5对于具有n个结点的完全二叉树，如果对其结点按层次编号，则对任一结点i(1≤i≤n)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是【i/2】(2)如果2i>n，则结点i无左孩子；如果2i≤n，则其左孩子是2i(3)如果2i+1>n，则结点i无右孩子；如果2i+1≤n，则其右孩子是2i+1满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n

6、的结点一一对应时，称为完全二叉树。1231145891213671014151231145891267101234567123456二叉树的存储结构顺序存储结构:为了能够反映出结点之间的逻辑关系，必须将它“修补”成完全二叉树，对应该完全二叉树，可以开辟长度为12的数组，对12个数据元素进行存储，原二叉树中空缺的结点在数组中的相应单元必须置空abcdeφφφφfg二叉树的存储结构链式存储结构:表示二叉树的链表中的结点应该包含3个域：数据域和指向左、右子树的指针域，二叉树的这种存储结构被称为二叉链表。Lchilddatarchi

7、ld在n个结点的二叉链表中，有n+1个空指针域6.3二叉树的遍历与线索化二叉树的遍历：是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。先根遍历二叉树（1）访问根结点；（2）先根遍历左子树；（3）先根遍历右子树。中根遍历二叉树（1）中根遍历左子树；（2）访问根结点；（3）中根遍历右子树。后根遍历二叉树（1）后根遍历左子树；（2）后根遍历右子树；（3）访问根结点。先根遍历:-+a*b–cd/ef中根遍历:a+b*c–d–e/f后根遍历:abcd-*+ef/-typedefstructNode{

8、datatypedata;structNode*Lchild;structNode*Rchild;}BTnode,*Btree;先根遍历算法voidpreorder(Btreeroot){if(root!=NULL){Visit(root->data);preorder(root->Lch