树和二叉树

树和二叉树

树形结构（非线性结构）：1）节点之间有分支；2）具有层次关系。

应用：自然界的树；人类社会的家谱和行政组织机构；计算机中的编译（用树表示源程序的语法结构）、数据库系统（用树组织信息）、算法分析（用树描述执行过程）。

定义：是n（n>=0）个节点的有限集。

若n=0,称为空树；

若n>0，则它满足如下两个条件；

1）有且仅有一个特定的称为根的节点；

2）其余节点可分为m（m>=0）个互不相交的有限集T1,T2,T3.....Tm，其中每一个集合本身又是一棵树，并称为根的子树。

树的其他表示方式：

还可以用广义表的形式表示（A(B(D))(C(E)(F))）。

树的基本术语：

根节点：非空树中无前驱节点的节点。

节点的度：节点拥有的子树数。

树的度：树内各节点的度的最大值。

叶子（终端节点）：度为0的节点

分支节点（非终端节点）：根节点以外的分支节点称为内部节点。

孩子、双亲：节点的子树的根称为该节点的孩子，该节点称为孩子的双亲。

兄弟节点：

节点的祖先：从根节点所经分支上的所有节点。 节点的子孙：以某节点为根的子树中的任一节点。 树的深度（高度）：树中最大层次（根节点为第一层）。 有序树：树中节点的各子树从左至右有次序（） 无序树：树中的节点没有次序。

森林：是m （m>=0）棵互不相交的树的集合。一棵树可以看成是一个特殊的森林。给森林中的各子树加上一个双亲节点，森林就变成了树（树一定是森林，森林不一定是树）。

二叉树的性质和存储结构

性质1、在二叉树的第i 层上至多有2^(i -1)个节点（i>=1）。至少1个

归纳基：当i=1时，只有一个根节点，2^(i -1)=2^0=1，命题成立。 归纳假设：设对所有的j （1<=j

归纳证明：由归纳假设可知，第i -1层上至多有2^(i -2)个节点。由于二叉树每个节点的度最大为2，故在第i 层上最大节点数为第i -1层上最大节点数的2倍，即：2*2^(i -2)=2^(i -1)。证毕。

性质2、深度为K 的二叉树至多有2^k -1个节点（k>=1）。至少有k 个节点

由性质1可见，深度为k 的二叉树的最大节点数为

∑

=-k

i i 1

)1(^2=2^k -1

性质3：对任何一棵二叉树T ，如果其终端节点数为n0，度为2的节点数为n2，则 n0=n2+1。

总边数为B ，B=n -1; B=n2*2+n1*1; n=n2*2+n1*1+1 总节点数为n ，n=n2*2+n1*1+1; 又 n0=n2+1

满二叉树

·一棵深度为k 且有2^k -1个节点的二叉树称为满二叉树。

·特点：1）每一层上的节点数都是最大节点数（即每层都满，不能空的）；2）叶子节点全部在最底层。

·对满二叉树节点位置进行编号：

·编号规则：从根节点开始，自上而下，自左而右。 ·每一节点位置都有元素。 ·满二叉树在同样深度的二叉树中节点个数最多；满二叉树在同样深度的二叉树中叶子节点个数最多。

完全二叉树

定义：深度为k的具有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号为1~n的节点一一对应时（1~n之间的节点不能断），称之为完全二叉树。

注：在满二叉树中，从最后一个节点开始，连续去掉任意个节点，即是一个完全二叉树。

特点：1、叶子节点只可能分布在层次最大的两层上。

2、对任一节点，如果其右子树的最大层次为i，则其左子树的最大层次必为i

或i+1.

完全二叉树的性质

性质4：具有n个节点的完全二叉树的深度为。

公式为取3,3+1=4；所以有4层

性质4表明了完全二叉树节点数n与完全二叉树深度k之间的关系。

性质5：如果对一棵有n个节点的完全二叉树（深度为[log2n]+1）,节点按层序编号（从第1层到第[log2n]+1层，每层从左到右），则对任一节点i(1<=i<-n),有：

1)如果i=1，则节点i是二叉树的根，无双亲；如果>1,则其双亲是节点[i/2]。

2)如果2*i>n,则节点i为叶子节点，无左孩子；否则，其左孩子是节点

性质5表明了完全二叉树中双亲节点编号与孩子节点编号之间的关系

二叉树的顺序存储

实现：按满二叉树的节点层次编号，依次存放二叉树中的数据元素。

//二叉树的顺序存储表示

#define MAXSIZE 100

typedef int SqBitree[MAXSIZE]//这里将树的存储类型定义为int型

SqBitree bt;

缺点：最坏情况深度为k的且有k个节点的单支树需要长度为2^k-1的一维数组。

特点：节点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树。

二叉树的链式存储结构

//二叉链表存储结构

typedef struct BiNode{

int data;

struct BiNode *Lchild ,*Rchild;

}BiNode,*BiTree;

在n个节点的二叉链表中，有n+1个空指针，分析：总共必有2*n个链域，其中除了根节点外每个节点都有一条链域与前驱相连，所以共消耗n-1个链域，因此，空指针为2*n-(n-1)=n+1(个）

三叉链表：

typedef struct TriTNode{

int data;

struct TriTNode *Lchild ,*Rchild,*parent;

}TriTNode,*TriTree;

遍历二叉树

遍历定义：顺着某一条搜索路径寻访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次（又称周游）。-----”访问”的含义很广，可以是对节点作各种处理，如：输出节点的信息、修改节点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历目的：得到树中所有节点的一个线性排列。

遍历用途：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。

遍历二叉树的算法描述：

根据遍历序列确定二叉树

·若二叉树中各节点的值均不相同，则二叉树节点的先序序列、中序序列和后序序列都是唯一的。

·有二叉树的先序序列（先序遍历，根节点不在序列头部）和中序序列，或有二叉树的后序序列和中序序列（后序遍历，根节点必在后序序列尾部）可以确定唯一一颗二叉树。有先序和后序就不行。

【算法5.1】遍历

//先序遍历递归,后序和中序改变顺序即可

int preorder(Bitree t){

if(t==null) return 0;//空二叉树

else{

visit(t);//访问根节点

preorder(t.Tchild);//递归调用左子树

preorder(t.Rchild);

}}

如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问节点的时机不同。

时间复杂度：O（n）--------每个节点只访问一次

空间复杂度：O（n）---------栈占用的最大辅助空间

【先序非递归算法】

void preorder_digui(Bitree t)

{

initStack(s);

push(s,t);

while(!stackEmpty(s))

{

while(gettop(s,p)&&p){

visit(p->data);

push(s,p->lchild);

}

pop(s,p);

if(!stackEmpty(s)){

pop(s,p);

push(s,p->rchild);

}

}

}

中序非递归算法

二叉树中序遍历的非递归算法的关键：在中序遍历过某节点的整个左子树后，如何找到该节点的根以及右子树。

基本思想：

1）建立一个栈

2）根节点进栈

3）根节点出栈，输出根节点，遍历右子树。

代码实现：

//中序遍历非递归

int InOrderTraverse(Bitree t){

Bitree p;Initstack(S); p= t;

while(p || !StackEmpty(S)){

if(p){

Push(S,p);

p = p->lchild;

}else{

Pop(S,p);

If(p)

printf("c%",p->data);

p=p->rchild;

}

return 1;

}

}

void preorder_digui(Bitree t)

{

initStack(s);

push(s,t);

while(!stackEmpty(s))

{

while(gettop(s,p)&&p){

push(s,p->lchild);

}

pop(s,p);

if(!stackEmpty(s)){

pop(s,p);

If(p)

visit(p->data);

push(s,p->rchild);

}

}

}

【后序非递归算法】

二叉树的层次遍历

思路：使用一个队列

1）将根节点进队

2）对不空时循环：从队列中列出一个节点*p,访问它；

a.若它有左孩子节点，将左孩子节点进队；

b.若它有右孩子节点，将左孩子节点进队。

//使用队列类型定义

typedef struct{

Btnode data[Maxsize];//存放对中元素

int front,rear;//队头和队尾指针

}SqQueue;

【算法】层次遍历算法

void levelOrder(BitNode *b){

BitNode *p; SqQueue *qu;

initQueue(qu); //初始化队列

enQueue(qu,b); //根节点指针进入队列

while(!QueueEmpty(qu)){//对不为空，则循环

dequeue(qu,p);//出队节点

printf("%c",p->data);//访问节点p

if(p->Tchild != null){

enQueue(qu,p->Tchild);//有左孩子时将其进队

}

if(p->Rchild != null){

enQueue(qu,p->Rchild);//有右孩子时将其进队

}

}

}

【算法】层次遍历使用栈实现

Void stact_sort(BiTree T){

BiNode *p;Stack *S;

InitStack(S);

Push(S,T);

While(!EmptyStack(S)){

}

}

按先序遍历序列建立二叉树的二叉链表

例：已知先序序列为：ABCDEFG

1）从键盘输入二叉树的节点信息，建立二叉树的存储结构2）在建立二叉树的过程中按照二叉树先序方式建立。

二叉树遍历算法的应用------复制二叉树

1）如果是空树，递归结束；

2）否则，申请新节点空间，复制根节点

a)递归复制左子树

b)递归复制右子树

【算法】复制二叉树

int cpoy(Bitree t,Bitree &newt){

if(t == null){//如果是空树返回0

newt = null;

return 0;

}else{

newt = ((BitNode*)malloc(sizeof(BitNode));//newt = new BitNode;

newt->data = t->data;

copy(t->Tchild,newt->Tchild);

copy(t->Rchild,newt->Rchild)

}

}

计算二叉树的深度

1）如果是空树，则深度为0；

2）否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。

【算法】计算二叉树的深度

//计算二叉树的深度

int depth(Bitree t){

if(t == null)return 0;//空树返回0

else{

m = depth(t->Tchild);

n = depth(t.Rchild);

if(m>n)

return (m+1);

else{

retunr (n+1);

}

}

}

【孩子兄弟表示法计算深度】

Int depth(CStree t){

Int d1,d2;

If(t){

D1=1+depth(t->firstchild);//计算第一个孩子树的深度

D2=depth(t->nextsibling);//计算兄弟子树的深度

Return d1>d2?d1:d2;

}

Else return 0;

}

【孩子链表表示计算深度】

Int getdepth(CTree t){

Return subdepth(t.r);

}

Int subdepth(int t){

If(!a.nodes[t].first) return 1;//根节点后面的first域为null

For(i=1,p=a.nodes[t].firstchild; p ; p=p->next){//

If((d=subdepth(p->next))>i)

I=d;

Return i+1;

}

}

【双亲表示法计算深度】

Int getDepth(PTree t){

Maxdep=0;

For(i=0;i

Dep=0;

For(j=i;j>=0;j=t.nodes[j].parent)

Dep++;

If(dep>maxdep) maxdep=dep;

}

Return maxdep;

}

计算二叉树的节点总数

1）如果是空树，则节点个数为0；

2）否则，节点个数为左子树的节点个数+右子树的节点个数+1。【算法表示】

int nodeCount(Bitree t){

if(t == null){

return 0；

}else{

return nodeCount(t->Rchild)+nodeCount(t->Tchild)+1;

}

}

【孩子-兄弟表示法计算叶子】

Int leafnum(CStree t){

If(t){

If(!t->firstchild)

Return 1+leafnum(t->nextsibling);

Else

Return leafnum(t->firstchild)+leafnum(t->nextsibling)

}

Else return 0;

}

计算二叉树的叶子结点

1）如果是空树，则节点个数为0；

2）否则，节点个数为左子树的节点个数+右子树的节点个数。

【算法演示】

int leadCount(Bitree t){

if(t == null){

return 0

}

if(t->Tchild==null && t->Rchild==null){

return 1;

}else{

return leadCount(t->Rchild)+leadCount(t->Tchild);

}

}

【双亲表示法计算深度】

Int parentDepth(PTree pt){

Max=0;

For(i=0;i

Dep=0;

For(j=i;j>=0;j=pt.nodes[j].parent)

Dep++;

If(dep>max)max=dep;

}

Return max;

}

线索二叉树

【问题】为什么要研究线索二叉树呢？

当用二叉链表作为二叉树的存储结构时，可以很方便地找到某个节点的左右孩子；但一般情况下，无法直接找到该节点在某种遍历序列中的前驱和后继节点。

解决方法：

1、通过遍历寻找---费时间

2、在增设前驱、后继指针域---增加了存储负

3、利用二叉链表中的空指针域

利用二叉链表的空指针域：

如果某个节点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个节点的

右孩子为空，则将空的右孩子指针域改为指向其后继-------这种改变指向的指针称为“线索”加上了线索的二叉树称为线索二叉树，对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。

树和森林

树的存储结构------1双亲表示法

实现：定义结构数组存放树的节点，每个节点含两个域：1）数据域（存放节点本身信息），2）双亲域（指示本节点的双亲节点在数组中的位置）

特点：找双亲容易，找孩子难。

树的存储结构------孩子表示法

把每个节点的孩子节点排列起来，看成是一个线性表，用单链表存储，则n个节点有n个孩子链表

特点：找孩子容易，找双亲难

树的存储结构------3孩子兄弟表示法（二叉树表示法、二叉链表表示法）

实现：用二叉链表做树的存储结构，链表中每个节点的两个指针域分别指向其第一个孩子节点和下一个兄弟节点。

//孩子兄弟表示法

typedef struct CSNode{

int data;

struct CSNode *firstchild,*nextchild;//指向第一个孩子节点、下一个兄弟节点}CSNode,*CSTree;

·将树转化为二叉树进行处理利用二叉树的算法来实现树的操作

·有树二叉树都可以用二叉链表做存储结构，则以二叉链表做媒介可以导出树与二叉树之间的一个对应关系。

将树转化成二叉树步骤

1、加线：在兄弟之间加一连线；

2、抹线：对每个节点，除了其左孩子外，去除其与孩子之间的关系；

3、旋转：以树的根节点为轴心，将整树顺时针转45°。

将二叉树转换成树的步骤

1、加线：若p节点是双亲节点的左孩子，则将p的右孩子，右孩子的右孩子......沿分支找到所有的右孩子，都与p的双亲用一条线连接起来；

2、抹线：抹掉原二叉树中双亲与右孩子之间的连线；

3、调整：将节点按层次排列，形成树结构。

森林转换成二叉树（二叉树与多棵树之间的关系）

1、将各棵树分别转换成二叉树

2、将每棵树的根节点用线相连

3、以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构

二叉树转换成森林

1、抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树；

2、还原：将孤立的二叉树还原成树。

树和森林的遍历

1、树的遍历（三种方式）---二叉树有4中：先序、后序、中序、层次

·先根（次序）遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树。

·后根（次序）遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点。

·层次遍历：若树不空，则自上而下、自左至右访问树中每个节点。

2、森林的遍历

将森林看做由三部分构成：

(1)森林中第一个树的根节点；（蓝色）

(2)森林中第一颗树的子树森林；（橙色）

(3)森林中其他树构成的森林。（黑色）

·先序遍历：若森林不空，则（1）访问森林中第一颗树的根节点；（2）先序遍历森林中第一颗树的子树森林；（3）先序遍历森林中（除第一颗树之外）其余树构成的森林。---依次从左至右对森林中的每一棵树进行先根遍历

·中序遍历：若森林不空，则（1）中序遍历森林中第一颗树的子树森林；（2）访问森林中第一颗树的根节点；（3）中序遍历森林中（除第一颗树之外）其余树构成的森林。---依次从左至右对森林中的每一棵树进行中根遍历

哈夫曼树

路径：从树中一个节点到另一个节点之间的分支构成这两个节点间的路径。

节点的路径长度：两节点路径上的分支数。

节点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树，但是路径长度最短的未必是完全二叉树。

权：将树中节点赋给一个有着某种含义的数值，则这个数值称为节点的权。

节点的带权路径长度：从根节点到该节点之间的路径长度与该节点的权的乘积。

树的路径长度：从树根到每一个节点的路径长度之和。记作TL。

树的带权路径长度：树中所有叶子节点的带权路径长度之和。记作WPL = ∑=n k W kL

k，

1

其中Wk是权值，Lk是节点到根的路径长度

最优树：带权路径长度最短的树

最优二叉树：带权路径长度最短的二叉树

因为是哈夫曼教授提出的，因此被称为哈夫曼树，相应的算法称为哈夫曼算法。

满二叉树不一定是哈夫曼树；哈夫曼树中权值越大的叶子离根越近；具有相同带权节点的哈夫曼树不唯一。

哈夫曼树的构造算法

（1）根据n个给定的权值{w1,w2,w3...wn}构成n棵二叉树的森林F={T1,T2,T3....Tn},其中Ti只有一个带权为Wi的根节点。------构造森林全是根

（2）在F中选取两个根节点的权值最小的树作为左右子树，构造一个新的二叉树，且设置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。-----选用两小造新树（3）在F中删除这两个树，同时将新得到的二叉树加入森林中。-----删除两小添新人（4）重复（2）和（3），直到森林中只有一个树为止，这棵树即为哈夫曼树。

总结：

·在哈夫曼算法中，初始时有n可二叉树，要经过n-1次合并最终形成哈夫曼树。

·经过n-1次合并并产生n-1个新节点，且这n-1个新节点都是具有两个孩子的分支节点。

可见：哈夫曼树中共有n+n-1 = 2n-1个节点，且其所有的分支节点的度均不为1。

哈夫曼树构造算法实现

采用顺序存储结构-----一维数组

节点类型定义

//哈夫曼树节点

typedef struct{

int weight;

int perent,lch,rch;

}HTNode,*hfmTree;

hfmTree h;

哈夫曼树中共有2*n-1（原本n个，加上新创建的n-1个）个节点，不使用0下标，直接从1开始，因此数组大小为2n（因为数组是从0开始的，0~2n-1=2n）。

【算法】构造哈夫曼编码

void CreatHFMTree(hfmTree ht,int n){

if(n<=1) return ;

m=2*n-1;//

ht = (HTNode*)malloc(sizeof(HTNode));//

for(i=1;i<=m;++i){//将2n-1个元素的lch、rch、parent置为0

ht[i].lch = 0;

ht[i].rch=0;

ht[i].parent = 0;

}

for(i=1;i<=n;++i){//输入前n个元素的weight值

scanf("%d",&ht[i]);

}

//初始化结束，下面开始建立哈夫曼树

for(i=n+1;i<=m;i++){//合并产生

select(ht,i-1,s1,s2);//在ht[k]中选择两个其双亲域为0，且权值最小的节点，并返回他们在ht中的序号s1和s2

ht[s].parent = i;ht.parent=i; //表示从F中删除s1,s2

ht[i].lch=s1; ht[i].rch=s2;//s1,,s2分别作为i的左右孩子

ht[i].weight=ht[s1].weight+ht[s2].weight;//i的权值为左右孩子权值之和

}}

哈夫曼编码

关键：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。

问题：什么样的前缀码能使的电文总长最短？

---------哈夫曼编码

方法：

1、统计字符集中每个字符在电文中出现的平均概率（概率越大，要求编码越短）。

2、利用哈夫曼的特点：权值大的叶子离根越近；将每个字符的概率值作为权值，

构造哈夫曼树。则概率越大的节点，路径越短。

3、在哈夫曼树的每个分支上标上0或1；节点的左分支标0，右分支标1，把从根

到每个叶子的路径上的标号连接起来，作为该叶子代表的字符的编码。

例：要传输的字符集D={C,D,A,E,T, ;}，字符出现频率W={2,5,3,7,9,2}。

以频率作为权值

两个问题：

1、为什么哈夫曼编码能够保证是前缀编码？

因为没有一片树叶是另一片树叶的祖先，所以每个叶节点的编码就不可能是其他叶节点编码的前缀。

2、为什么哈夫曼编码能够保证字符编码总长最短？

因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。

由此可得出：

性质1、哈夫曼编码是前缀码

性质2、哈夫曼编码是最优前缀码

题：设计哈夫曼：

1）构造出一个哈夫曼树-----

2）根节点的左边标记0；右边标记1；

3）写出所有字符集的编码；

夫曼算法的实现

待续.......

编码与解码

·明文

I will go to school on tomorrow! Because the virus is disappear quickly in China.编码：①输入各字符及其权值（包括空格）

②构造哈夫曼树---HT[i]

③进行哈夫曼编码---HC[i]

④查HC[i]，得到各字符的哈夫曼

解码：

①构造哈夫曼树；

②依次读入二进制码

③读入0则走向左孩子；读入1则走向右孩子；

④一旦到达某叶子时，即可译出字符

⑤然后再从根节点继续译码，指导结束。

数据结构-6 树和二叉树

第六章树和二叉树 一．选择题 1. 以下说法错误的是。 A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种"分支层次"结构 2. 如图6-2所示的4 棵二叉树中，不是完全二叉树。 图6-2 4 棵二叉树 3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。 A. t->left == NULL B. t->ltag==1 C. t->ltag==1 且t->left==NULL D .以上都不对 4. 以下说法错误的是。 A.二叉树可以是空集 B.二叉树的任一结点最多有两棵子树 C.二叉树不是一种树 D.二叉树中任一结点的两棵子树有次序之分 5. 以下说法错误的是。 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 6. 如图6-3所示的4 棵二叉树，是平衡二叉树。

图6-3 4 棵二叉树 7. 如图6-4所示二叉树的中序遍历序列是。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6-4 1 棵二叉树 8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。 A. acbed B. decab C. deabc D. cedba 9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。 A. 前序 B.中序 C. 后序 D. 层次序 10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。 A.42 B.40 C.21 D.20 12. 一棵二叉树如图6-5所示，其后序遍历的序列为。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh

第5章--树和二叉树习题

第5章树和二叉树 一．选择题 （1）由3 个结点可以构造出多少种不同的二叉树（ D ） A．2 B．3 C．4 D．5 （2）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B． 500 C．254 D．501 （3）一个具有1025个结点的二叉树的高h为（）。 A．11 B．10 C．11至1025之间 D．10至1024之间 （4）深度为h的满m叉树的第k层有（）个结点。(1=

习题6树和二叉树.docx

习题6树和二叉树 说明： 本文档中，凡红色字标出的题请提交纸质作业，只写题号和答案即可。 6.1单项选择题 1. 由于二叉树屮每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法_B_。 A. 正确 B.错误 2. 假定在一棵二叉树屮，双分支结点数为15,单分支结点数为30个，则叶子结点数为 B_个。 A. 15 B. 16 C. 17 D. 47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有_C_种。 A. 3 B.4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有_C_种。 A.5 B.6 C. 30 D. 32 5. 深度为5的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点 数至少为 B 。 A. 2h B. 2h-l C. 2h+l D. h+l 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h,则_A_。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -l 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序_A_。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如杲某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后 序为_C_。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法_A_。 A.正确 B.错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha 12. 在一非空二叉树的中序遍历序列中, A.只有右子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是_B_。 14. 一棵二叉树如图6.2所示，其中序遍历的序列为 B 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh C. bdgaechf D. gdbehfca 根结点的右边_A_。 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6」

第5章 树与二叉树习题参考答案

习题五参考答案 备注: 红色字体标明的是与书本内容有改动的内容 一、选择题 1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。 A．先根 B. 中根 C. 后根 D. 层次 2．在哈夫曼树中，任何一个结点它的度都是（ C ）。 B．0或1 B. 1或2 C. 0或2 D. 0或1或2 3．对一棵深度为h的二叉树，其结点的个数最多为（ D ）。 A．2h B. 2h-1 C. 2h-1 D. 2h-1 4．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ）A．所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ）B．所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树 6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ） A．2 B. 3 C. 4 D. 5 7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。 A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA 8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ B ）。 A．ABCDEF B. ABDCEF C. ABCDFE D. ABDECF 9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ）A．2 B. 3 C. 4 D. 5 10．在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。 A．n-1 B. n C. n+1 D. 0 二、填空题 1.在一棵度为m的树中，若度为1的结点有n1个，度为2的结点有n2个，……，度为m 的结点有n m个，则这棵树中的叶结点的个数为1+n2+2n3+3n4+…+(m-1)n m。 2.一棵具有n个结点的二叉树，其深度最多为 n ，最少为 [log2n]+1 。 3.一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。 4.以{5，9，12，13，20，30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。 5.有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。

第6章树和二叉树习题

第六章 树和二叉树 一、选择题 1．算术表达式a+b*（c+d/e ）转为后缀表达式后为（ B ） A ．ab+cde/* B ．abcde/+*+ C ．abcde/*++ D ．2. 设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ C ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G ）) D. A*B+C/D*E+F-G 3. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1 ，1 则T 中的叶子数为（ D ） A ．5 B ．6 C ．7 D ．8 4. 在下述结论中，正确的是（ D ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意 交换; ④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A ．①②③ B ．②③④ C ．②④ D ．①④ 5. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n,森林F 中第一棵树的结点个数是（ A ） A ．m-n B ．m-n-1 C ．n+1 D ．条件不足，无法确定 6．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A ．9 B ．11 C ．15 D ．不确定 7．设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ D ）。 A ．M1 B ．M1+M2 C ．M3 D ．M2+M3 8．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ E ） A ． 250 B ． 500 C ．254 D ．505 E ．以上答案都不对 9. 有关二叉树下列说法正确的是（ B ） A ．二叉树的度为2 B ．一棵二叉树的度可以小于2 C ．二叉树中至少有一个结点的度为2 D ．二叉树中任何一个结点的度都为2 10．二叉树的第I 层上最多含有结点数为（ C ） A ．2I B ． 2I-1-1 C ． 2I-1 D ．2I -1 11. 一个具有1025个结点的二叉树的高h 为（ C ） A ．11 B ．10 C ．11至1025之间 D ．10至1024之间 12．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点 A ．2h B ．2h-1 C ．2h+1 D ．h+1 13. 一棵树高为K 的完全二叉树至少有（ C ）个结点 A ．2k –1 B. 2k-1 –1 C. 2k-1 D. 2 k 14．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( C )次序的遍历 实现编号。 A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 15．一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ B ）

第四章-树和二叉树-说课教案

第五章树和二叉树说课教案 姓名：仇环 单位：信息工程系 年级与科目：08级计算机应用《数据结构》 课题：树和二叉树 职称：讲师 教龄：1年 （各位老师下午好，我说课的题目是树和二叉树） 说课的内容包括： 一．教学大纲分析 二．教材分析 三、学情分析 四．教学目标 五、教学重点与难点 六、教学方法 七、教学过程 八、教学效果预测及教学后记 一、教学大纲分析： 高职高专教育的人才培养特征是高级技术应用型人才，具体到计算机专业来说，就是培养从事计算机产品生产、维修和编程和实际应用的技术人才。在计算机专业的课程体系中，《数据结构》不仅是一门重要的专业基础课程，而且是计算机程序设计重要的理论基础，更

是计算机等级、专升本等考试的必考课程之一。它在整个学科体系中具有重要作用，有着不可替代的地位。 本课程的教学不仅重视学生对理论知识的理解和掌握，锻炼学生抽象思维能力和想象能力，更注重实践动手的能力，要求学生能够设计出结构清晰、可读性好、运行效率高的算法，并能够用一种或多种计算机高级程序设计语言实现。学好这门课程，对培养学生程序设计的能力、设计算法的能力和运用计算机进行数据处理的能力有着深远的意义。 其前导课程为：《C语言程序设计》或《C++语言》。 二、教材分析 本教材属于“21世纪高职高专规划教材”，这套教材主要面向高职高专院校学生。教材内容力求体现以应用为主体，强调理论知识的理解和运用，实现专科教学以实践体系及技术应用能力培养为主的目标。 1、教材特点： 本教材的特点可总结为： （1）基础理论知识的阐述由浅入深、通俗易懂。内容的组织和编排以应用为主线，省略了一些理论推导和数学证明过程，淡化了算法的设计分析和复杂的时空分析。 （2）各章都配有应用举例，列举分析了很多实用的例子，且大多数算法都直接给出了相应的C语言程序，以便上机练习和实践。 （3）便于复习和掌握每章的重点，每章的起始处都给出了要点，并在每章结尾处给出了小结。 2、教材内容： 本书共分为8章。第一章叙述数据、数据结构、算法等基本概念。第2~6章分别讨论了线性表、栈和队列、串和数组、树和二叉树、图等的基本数据结构及其应用。第7章和第8章分别讨论了查找和排序的各种实现方法及其应用。因为此教材与我们通用的蔚学敏老师的《数据结构》（清华大学版）内容有一定的区别，所以在教材处理上参考了其他《数据结构》教材，对本教材进行了补充。我说课的内容是第五章第一节。在《数据结构》中，树这一章既是这门课程的难点也是该课程的重点。第一节的内容是对第五章内容的基础，对于第五章内容的学习有很重要的意义。 3、文献资料清单： 扩大学生的知识面并培养学生的自学能力，为学生的研究性学习和自主学习的开展提供下列文献资料清单：

《数据结构》习题汇编06第六章树和二叉树试题

第六章树和二叉树试题 一、单项选择题 1.树中所有结点的度等于所有结点数加（）。 A. 0 B. 1 C. -1 D. 2 2.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 根结点 D. 空结点 3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. -1 4.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。 A. n B. n-1 C. n+1 D. 2*n 5.在一棵具有n个结点的二叉树的第i层上（假定根结点为第0层，i大于等

于0而小于等于树的高度），最多具有（）个结点。 A. 2i B. 2i+1 C. 2i-1 D. 2n 6.在一棵高度为h（假定根结点的层号为0）的完全二叉树中，所含结点个数不 小于（）。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h 7.在一棵具有35个结点的完全二叉树中，该树的高度为（）。假定空树 的高度为-1。 A. 5 B. 6 C. 7 D. 8 8.在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（）。假 定树根结点的编号为0。 A. ?(n-1)/2? B. ?n/2? C. ?n/2? D. ?n/2? -1 9.在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号 为（）。假定根结点的编号为0

A. 2i B. 2i-1 C. 2i+1 D. 2i+2 10.在一棵完全二叉树中，假定根结点的编号为0，则对于编号为i（i＞0）的结 点，其双亲结点的编号为（）。 A. ?(i+1)/2? B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 11.在一棵树的左子女-右兄弟表示法中，一个结点的右孩子是该结点的（） 结点。 A. 兄弟 B. 子女 C. 祖先 D. 子孙 12.在一棵树的静态双亲表示中，每个存储结点包含（）个域。 A. 1 B. 2 C. 3 D. 4 13.已知一棵二叉树的广义表表示为a (b (c), d (e ( , g (h) ), f ) )，则 该二叉树的高度为（）。假定根结点的高度为0。 A. 3 B. 4 C. 5 D. 6

第6-10章--树和二叉树--答案

第6章树和二叉树 一、基础知识题 1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 [解答]二叉树的叶结点有⑥、⑧、⑨。分支结点有①、 ②、③、④、⑤、⑦。结点①的层次为0；结点②、 ③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、 ⑧的层次为3；结点⑨的层次为4。 2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。 [解答] （1）顺序表示 ①②③④⑤⑥⑦ ⑧⑨

（2）二叉链表表示 3．在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ [解答] 结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。 4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 [解答] 具有3个结点的树具有3个结点的二叉树 5．如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。 [解答] 总结点数n=n0+n1+n2+…+n m 总分支数e=n-1= n0+n1+n2+…+n m-1 =m×n m+(m-1)×n m-1+…+2×n2+n1

则有 n 0=∑=+-m i i n i 2 1))1(( 6．试分别找出满足以下条件的所有二叉树： （1） 二叉树的前序序列与中序序列相同； （2） 二叉树的中序序列与后序序列相同； （3） 二叉树的前序序列与后序序列相同。 [解答] （1） 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； （2） 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； （3） 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。 7．填空题 （1）对于一棵具有n 个结点的树，该树中所有结点的度数之和为 n-1 。 （2）假定一棵三叉树的结点个数为50，则它的最小高度为 4 ，最大高度为 49 。 （3）一棵高度为h 的四叉树中，最多含有 (4h+1-1)/3 结点。 （4）在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6 个。 （5）一棵高度为5的满二叉树中的结点数为 63 个，一棵高度为3的满四叉树中的结点数为 85 个。 （6）在一棵二叉树中，假定度为2的结点有5个，度为1的结点有6个，则叶子结点数有 6 个。 （7）对于一棵含有40个结点的理想平衡树，它的高度为 5 。 （8）若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一堆数组a 中，即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左子女结点为2×i+1 ，右子女结点为 2×i+2 ，双亲结点（i ≥1）为??2/)1(-i 。 9．n 个结点可构造出多少种不同形态的二叉树？若有3个数据1，2，3，输入它们构 造出来的中序遍历结果都为1，2，3的不同二叉树有哪些？ [解答] 有n n C 2/ (n+1)种。当n=3时，中序遍历都为1，2，3的不同二叉树有5种：

第6章树和二叉树自测题

第6章树和二叉树自测题 一、填空题 1．树是一种________结构。在树结构中，________结点没有直接前趋。（层次，根） 2．一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________。（子孙结点，祖先） 3．二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______的二叉树、同时有______的二叉树五种基本形态。（空、只有根结点、根和根的左子树、根和根的右子树、根和根的左右子树） 4．树在计算机内的表示方式有_______、_______、_________。（双亲表示法、孩子表示法、双亲孩子表示法） 5．对任何二叉树，若度为2的节点数为n 2，则叶子数n =______。（n =n 2 +1） 6. 高度为k(k>=1)的二叉树至多有______个结点。(2k-1) 7. 二叉树第i(i>=1)层上至多有______个结点。(2i-1) 8. 满二叉树上各层的结点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。（最大值，完全二叉树） 9．具有n个结点的完全二叉树的高度为______。（log 2 n） 10. 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X 有： (1)若i=1，则结点X是______；若i〉1，则X的双亲PARENT(X)的编号为______。(根 结点，[i/2]) (2) 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为 ______。（左孩子，右孩子，2i） (3)若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。（右 孩子，2i+1） 11. 二叉树通常有______存储结构和______存储结构两类存储结构。(顺序，链接) 12．具有n个结点的二叉链表中，一共有________个指针域，其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。(2n，n-1，n+1) 13. 一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。(访问根结点、遍历左子树、遍历右子树) 14. 若以N、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。(NLR、LNR、LRN、先根（或前序）遍历、中根（或中序）遍历、后根（或后序）遍历) 15. 在二叉链表中，指针p所指结点为叶结点的条件是______。(结点的左右孩子域均为空指针) 16. 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶结点。（12） 17．设根结点的层数为１，具有n个结点的二叉树的最大高度是______。(n) 18. 已知二叉树前序序列为ABDEGCF，中序序列为DBGEACF，则后序序列是____。(DGEBFCA) 19. 若一个二叉树的叶结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。(先(前)序) 20. 先根次序遍历树(森林)等同于按______遍历对应的二叉树；后根次序遍历树(森林)等同

第5章+树与二叉树习题解析(答)

习题五树与二叉树 一、选择题 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。 A、所有的结点均无左孩子 B、所有的结点均无 右孩子 C、只有一个叶子结点 D、是任意一棵 二叉树 2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。 A、250 B、500 C、254 D、505 E、以上答案都不对 3、以下说法正确的是。 A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点 B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点 C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点 D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点 4、以下说法错误的是。 A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序 遍历序列中的第一个结点 C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结 点是哪一个

D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后 的 5、一棵有124个叶结点的完全二叉树，最多有个结点。 A、247 B、248 C、249 D、250 E、251 6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。 A、不发生变化 B、发生变化 C、不能确定 7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是。 A、a在b的右方 B、a在b的左方 C、a是b的祖先 D、a 是b的子孙 8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。 A、不确定 B、2k C、2k-1 D、2k+1 9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。 A、13 B、12 C、 26 D、25 10、下面几个符号串编码集合中，不是前缀编码的是。 A、{0，10，110，1111} B、{11，10，001，101，0001} C、{00，010，0110，1000} D、{b,c,aa,ac,aba,abb,abc} 11、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。

数据结构第六章树和二叉树习题及答案

习题六树和二叉树 一、单项选择题 1．以下说法错误的是（） A. 树形结构的特点是一个结点可以有多个直接前趋 B. 线性结构中的一个结点至多只有一个直接后继 C. 树形结构可以表达（组织）更复杂的数据 D. 树（及一切树形结构）是一种”分支层次”结构 E. 任何只含一个结点的集合是一棵树 2. 下列说法中正确的是（） A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中每个结点的度都为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 3. 讨论树、森林和二叉树的关系，目的是为了（） A. 借助二叉树上的运算方法去实现对树的一些运算 B. 将树、森林按二叉树的存储方式进行存储 C. 将树、森林转换成二叉树 D. 体现一种技巧，没有什么实际意义4．树最适合用来表示（） A. 有序数据元素 B .无序数据元素 C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B ．11 C ．15 D ．不确定 6. 设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1, M2和M3与森林F 对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B ．M1+M2 C ．M3 D ．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B ．500 C ．254 D ．505 E ．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为（） A. 不确定 B . 2n C . 2n+1 D . 2n-1 9．二叉树的第I 层上最多含有结点数为（） I I-1 I-1 I A．2I B ．2 I-1 -1 C ．2 I-1 D ．2 I -1 10．一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有（）结点A．2h B ．2h-1 C ．2h+1 D ．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A.指向最左孩子 B .指向最右孩子 C .空D .非空 12．已知一棵二叉树的前序遍历结果为为（）。 A．CBEFDA B ．FEDCBA 13．已知某二叉树的后序遍历序列是（）。 ABCDEF中序遍历结果 为 C ．CBEDFA D dabec, 中序遍历序列是 CBAEDF则后序遍历的结 果 ．不定 debac , 它的前序遍历是

第6章 树和二叉树答案

第六章答案 6． 1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】 具有3个结点的树具有3个结点的二叉树 6.3已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k 的结点，则该树中有多少个叶子结点？ 【解答】设树中结点总数为n,则n=n0 + n1 + …… + n k 树中分支数目为B,则B=n1 + 2n2 + 3n3+ …… + kn k 因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 即n0 + n1 + …… + n k = n1 + 2n2 + 3n3+ …… + kn k + 1 由上式可得叶子结点数为：n0 = n2 + 2n3+ …… + (k-1)n k + 1 6.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1 所以n2=n0 –1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=99 6.6 试分别找出满足以下条件的所有二叉树: (1) 前序序列与中序序列相同; (2) 中序序列与后序序列相同; (3) 前序序列与后序序列相同。 【解答】 (1) 前序与中序相同：空树或缺左子树的单支树； (2) 中序与后序相同：空树或缺右子树的单支树； (3) 前序与后序相同：空树或只有根结点的二叉树。 6.9 假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 【解答】 构造哈夫曼树如下：

第5章-树和二叉树-自测题

第5章树和二叉树自测题 一、下面是有关二叉树的叙述，请判断正误（每小题1分，共10分） （ X ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。（ X ）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （ X ）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ X ）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。 （ X ）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ X ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ X ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i－1个结点。（√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）10. 具有12个结点的完全二叉树有5个度为2的结点。 二、填空（每空1分，共15分） 1．由３个结点所构成的二叉树有 5 种形态。 2. 一棵深度为6的满二叉树有 31 个分支结点和 32 个叶子。 3．一棵具有２５７个结点的完全二叉树，它的深度为 9 。 4.设一棵完全二叉树有700个结点，则共有 350 个叶子结点。 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 6.一棵含有n个结点的k叉树，可能达到的最大深度为 n ，最小深度为 logk(1-n+nk) 。 7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 LRN 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 FEGHDCB 。 8.中序遍历的递归算法平均空间复杂度为 O(n) 。 9. 用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是 33 。

数据结构习题汇编06第六章树和二叉树试题0001

单项选择题 第六章树和二叉树试题 树中所有结点的度等于所有结点数加（ A. 0 B. 1 C. -1 D. 2 在一棵树中，（ A. 分支结点 ）没有前驱结点。 B. 叶结点 C.根结点 D.空结点 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ A. 2 在一棵具有 A. n 在一棵具有 最多具有（ A. 2 i B. 1 C. 0 n 个结点的二叉树中，所有结点的空子树个数等于（ B. n-1 C. n+1 n 个结点的二叉树的第i 层上（假定根结点为第 ） 个结点。 B. 2 在一棵高度为 八 h-1 A. 2 i+1 亠 c i-1 C. 2 )。 D. -1 )。 D. 2*n 0层，i 大于等于0而小于等于树的高度）， f 小 n D. 2 （假定根结点的层号为 B. 2 h+1 0）的完全二叉树中, C. 2 h -1 所含结点个数不小于（ _ _ h D. 2 在一棵具有35个结点的完全二叉树中，该树的高度为（ A. 5 B. 6 C. 7 在一棵具有n 个结点的完全二叉树中，分支结点的最大编号为 A. (n-1)/2 B. n/2 C. n/2 ）。假定空树的高度为-1。 D. 8 ）。假定树根结点的编号为 D. n/2 -1 0。 在一棵完全二叉树中, 的编号为0 A. 2i 在一棵完全二叉树中, （ A. )。 (i+1)/2 在一棵树的左子女 A. 兄弟 若编号为i 的结点存在左孩子, 则左子女结点的编号为 （ ）。假定根结点 B. 2i-1 C. 2i+1 D. 2i+2 假定根结点的编号为 B. (i-1)/2 0,则对于编号为i （i >0） 的结点，其双亲结点的编号为 C. i/2 D. i/2 -1 -右兄弟表示法中，一个结点的右孩子是该结点的（ C.祖先 B.子女 ）结点。 D.子孙 在一棵树的静态双亲表示中，每个存储结点包含（ A. 1 B. 2 ）个 域。 C. 3 D. 4 已知一棵二叉树的广义表表示为 a （b （c ）, d （e （ , g （h ） ）, f ）），则该二叉树的高度为（ 假定根结点的高度为 0。 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

数据结构第6章树和二叉树

第六章树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为 ( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数 为（）A．5 B．6 C．7 D．8 3.在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意 交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 4.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F 中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A．250 B． 254 C．500 D．501 6.设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 7.有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 8．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 9.一个具有1025个结点的二叉树的高h为（） A．11 B．10 C．11至1025之间 D．10至1024之间 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11.一棵具有 n个结点的完全二叉树的树高度（深度）是（） A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-1 12．深度为h的满m叉树的第k层有（）个结点。(1=

第5章--树和二叉树习题

@ 第5章树和二叉树 一．选择题 （1）由3 个结点可以构造出多少种不同的二叉树（ D ） A．2 B．3 C．4 D．5 （2）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B． 500 C．254 D．501 （3）一个具有1025个结点的二叉树的高h为（）。 A．11 B．10 C．11至1025之间 D．10至1024之间$ （4）深度为h的满m叉树的第k层有（）个结点。(1=

第5章+树与二叉树习题解析(答)讲解学习

第5章+树与二叉树习题解析(答)

习题五树与二叉树 一、选择题 1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。 A、所有的结点均无左孩子 B、所有的结点均 无右孩子 C、只有一个叶子结点 D、是任意一 棵二叉树 2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。 A、250 B、500 C、254 D、 505 E、以上答案都不对 3、以下说法正确的是。 A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点 B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点 C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点 D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点 4、以下说法错误的是。 A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后 序遍历序列中的第一个结点

C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根 结点是哪一个 D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之 后的 5、一棵有124个叶结点的完全二叉树，最多有个结点。 A、247 B、248 C、249 D、250 E、251 6、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次 序。 A、不发生变化 B、发生变 化 C、不能确定 7、设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件 是。 A、a在b的右方 B、a在b的左方 C、a是b的祖先 D、a 是b的子孙 8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。 A、不确定 B、 2k C、2k-1 D、2k+1 9、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。 A、13 B、 12 C、26 D、25