文档介绍：,所有元素之间具有明显的层次特性。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。二叉树的基本性质:(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;(2)深度为m的二叉树最多有2m-1个结点;(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分;(5)具有n个结点的完全二叉树的深度为[log2n]+1;(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,….n给结点进行编号(k=1,2….n),有以下结论:①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2);②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历:(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点。设一棵完全二叉树共有700个结点,则该二叉树中有______个叶子结点?最佳答案假设n0是度为0的结点总数(即叶子结点数),n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知:n0=n2+1,则n=n0+n1+n2(其中n为完全二叉树的结点总数),由上述公式把n2消去得:n=2n0+n1-1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0=(n+1)/2或n0=n/2,合并成一个公式:n0=?(n+1)/2?,就可根据完全二叉树的结点总数计算出叶子结点数。或者根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,:n0+n1+n2=700n0=n2+1;2n0=701-n1;因为结点数为整数,所以n1=1,no=350或者完全二叉树的定义:若设二叉树的高度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层从右向左连续缺若干结点,这就是完全二叉树。可以算出,这棵二叉树共十层,1-9层的节点个数为2^9-1=511个,所以最后一层的节点个数为70