文档介绍：:1树2。结点的度3。叶子4。分支点5。、子结点7兄弟8结点的层数9树的高度10二叉树11空二叉树12左孩子、右孩子13孩子数14满二叉树15完全二叉树16先根遍历17中根遍历18后根遍历19二叉树的遍历20判定树21哈夫曼树二、填空题树(及一切树形结构)是一种“__分支层次______”结构。在树上,___根_____结点没有直接前趋。对树上任一结点X来说,X是它的任一子树的根结点惟一的__前驱______。一棵树上的任何结点(不包括根本身)称为根的________。若B是A的子孙,则称A是B的_______一般的,二叉树有_____二叉树、_只根_____的二叉树、只有_左子树_____的二叉树、只有_右子树_____的二叉树、同时有左右______的二叉树五种基本形态。二叉树第i(i>=1)层上至多有_____个结点。深度为k(k>=1)的二叉树至多有_____个结点。对任何二叉树,若度为2的节点数为n2,则叶子数_____。满二叉树上各层的节点数已达到了二叉树可以容纳的_最大值_____。满二叉树也是_完全二叉树_____二叉树,但反之不然。具有n个结点的完全二叉树的深度为______。如果将一棵有n个结点的完全二叉树按层编号,则对任一编号为i(1<=i<=n)的结点X有:若i=1,则结点X是_根_____;若i〉1,则X的双亲PARENT(X)的编号为__i/2取整____。若2i>n,则结点X无_左孩子_____且无_右孩子_____;否则,X的左孩子LCHILD(X)的编号为__2i____。若2i+1>n,则结点X无__右孩子____;否则,X的右孩子RCHILD(X)的编号为__为2i+1____。。,该指针具有标识二叉链表的作用。,若二叉树为空,则_root_____=,这个值或者是___指向孩子的_________的指针,或者是__空指针Null____。,一共有__2n______个指针域,其中只有__n-1______个用来指向结点的左右孩子,其余的____n+1____个指针域为NULL。,其中最常用的是_二叉链表_______与__三叉链表______。“残缺”位置上增设“__虚结点_____”将其转化为完全二叉树。**,请在横线处填充适当的语句。Voidcountleaf(bitreptrt,int*count)/*根指针为t,假定叶子数count的初值为0*/{if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))___*count++_____;countleaf(t->lchild,&count);_______countleaf(t->rchild,&count);_}}、左子树和右子树三部分组成,因此对二叉树的遍历也可相应地分解成___访问根结点_____、_遍历左子树_______、_遍历右子树_______三项“子任务”。、L、R分别表示二叉树的三项子任务,限定“先左后右”,这样可能的次序有:________、________、________三种,按这三种次序进行的遍历分别称为________、________、________。、_中序遍历_______、___后序遍历_____等三种。**,对应于一次比较或判断,每个__终端节点______对应一种分类结果。,其终端结点为n1,……,nk。每个终端结点ni对应的百分为pi(通常将pi称为n1的权)。再假定ni的祖先数为li,这样,按T进行分类的平均比较次数为________。,请在以下横线处填充适当的语句。采用静态链表作存储结构,设置一个大小为2n-1的数组,令数组每个元素由四个域组成:wt是结点的权值;lchild、rchild分别为结点的左、右孩子指针;parent是结点的双亲在数组中的下标。其数组元素类型定义如下:typedefstruct{floatwt/*权值*/intparent,lchildrchild;/*指针域*/}node;typedefnodehftree[2*n-1];在这种存储结