/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数
求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/
#include
#include
#define Maxsize 100
/*创建二叉树的节点*/
typedef struct BTNode //结构体 struct 是关键字不能省略结构体名字可以省略（为无名结构体）
//成员类型可以是基本型或者构造形，最后的为结构体变量。
{
char data;
struct BTNode *lchild,*rchild;
}*Bitree;
/*使用先序建立二叉树*/
Bitree Createtree() //树的建立
{
char ch;
Bitree T;
ch=getchar(); //输入一个二叉树数据
if(ch==' ') //' '中间有一个空格的。
T=NULL;
else
{ T=(Bitree)malloc(sizeof(Bitree)); //生成二叉树 (分配类型 *)malloc(分配元素个数 *sizeof(分配类型))
T->data=ch;
T->lchild=Createtree(); //递归创建左子树
T->rchild=Createtree(); //地柜创建右子树
}
return T;//返回根节点
}
/*下面先序遍历二叉树*/
/*void preorder(Bitree T) //先序遍历
{
if(T)
{
printf("%c-",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
} */
/*下面先序遍历二叉树非递归算法设计*/
void preorder(Bitree T) //先序遍历非递归算法设计{
Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p;
int top=-1; //栈置空
if(T)
{
top++;
st[top]=T; //根节点进栈
while(top>-1) //栈不空时循环
{
p=st[top]; //栈顶指针出栈
top--;
printf("%c-",p->data );
if(p->rchild !=NULL) //右孩子存在进栈
{
top++;
st[top]=p->rchild ;
}
if(p->lchild !=NULL) //左孩子存在进栈
{
top++;
st[top]=p->lchild ;
}
}
printf("\n");
}
}
/*下面中序遍历二叉树*/
/*void inorder(Bitree T) //中序遍历
{
if(T)
{
inorder(T->lchild);
printf("%c-",T->data);
inorder(T->rchild);
}
}
*/
/*下面中序遍历二叉树非递归算法设计*/
void inorder(Bitree T) //中序遍历
{
Bitree st[Maxsize]; //定义循环队列，存放节点的指针
Bitree p;
int top=-1;
if(T)
{
p=T;
while (top>-1||p!=NULL) //栈不空或者*不空是循环
{
while(p!=NULL) //扫描*p的所有左孩子并进栈
{
top++;
st[top]=p;
p=p->lchild ;
}
if(top>-1)
{
p=st[top]; //出栈*p节点，它没有右孩子或右孩子已被访问。
top--;
printf("%c-",p->data ); //访问
p=p->rchild ; //扫描*p的右孩子节点}
}
printf("\n");
}
}
/*下面后序遍历二叉树*/
/*void postorder(Bitree T) //后序遍历
{
if(T)
{
postorder(T->lchild);
postorder(T->rchild);
printf("%c-",T->data);
}
}
*/
/*二叉树后序遍历非递归算法设计*/
void postorder(Bitree T) //后序遍历非递归
{
Bitree st[Maxsize];
Bitree p=T,q;
int flag; //作为一个标志处理栈定时候用
int top=-1; //栈置空
if(T)
{
do
{
while(p) //将*p所在的左节点进栈
{
top++;
st[top]=p;
p=p->lchild ;
}
q=NULL;
flag=1; //设置flag=1表示处理栈顶节点
while(top!=-1&&flag==1)
{
p=st[top];
if(p->rchild==q) //右孩子不存在或者右孩子已被访问，访问之
{
printf("%c-",p->data );
top--;
q=p; //让q指向刚被访问的节点
}
else
{
p=p->rchild ; //p指向右孩子
flag=0; //设置flag=0表示栈顶节点处理完毕
}
}
}while(top!=-1) ;//栈不空是循环
printf("\n");
}
}
/*下面层序遍历二叉树*/ //（层序遍历的模板）
void levelorder(Bitree T) //层序遍历二叉树
{
Bitree p;
Bitree qu[Maxsize]; //定义一个循环队列
int front, rear; //定义队头队尾指针
front=0; //队列置空
rear=0;
rear++; //根节点进队
qu[rear]=T;
while(front!=rear) //队列不空
front=(front+1)%Maxsize; //对头出队列
p=qu[front];
printf("%C-",p->data ); //访问对头节点
if(p->lchild !=NULL) //左子树不空进队
{
rear=(rear+1)%Maxsize;
qu[rear]=p->lchild ;
}
if(p->rchild !=NULL) //右子树不空进队
{
rear=(rear+1)%Maxsize;
qu[rear]=p->rchild ;
}
}
}
/*计算二叉树节点数*/
/*方法一*/
/*int num(Bitree T)
{
if(T==NULL)
return 0;
else
{
return num(T->lchild )+num(T->rchild )+1;
}
}
*/
/*方法二*/
int num (Bitree T)
if(T!=NULL)
return num(T->lchild )+num(T->rchild )+1;
return 0;
}
/*下面程序段计算二叉树的叶子节点个数*/
int countleaf(Bitree T)
{
if(T==NULL) //如果节点为空，则返回0
return 0;
else if((T->lchild==NULL) && (T->rchild==NULL))//否则如果节点左右孩子有一个为空，另一个存在，则返回1
return 1;
else
return(countleaf(T->lchild)+countleaf(T->rchild));//否则返回左右子树叶子节点之和
}
/*下面程序段计算二叉树的单分支节点个数*/
int Sfenzhi(Bitree T)
{
if(T==NULL)
return 0;
else if (T->lchild==NULL&&T->rchild!=NULL||T->lchild!=NULL&&T->rchild==NULL) //为单分支节点
return Sfenzhi(T->lchild )+Sfenzhi(T->rchild )+1;
else
return Sfenzhi(T->lchild )+Sfenzhi(T->rchild );
}
/*下面程序段计算二叉树的双分支节点个数*/
int Dfenzhi(Bitree T)
{
if(T==NULL)
return 0;
else if (T->lchild!=NULL&&T->rchild!=NULL||T->lchild!=NULL&&T->rchild!=NULL) //为单分支节点
return Dfenzhi(T->lchild )+Dfenzhi(T->rchild )+1;
else
return Dfenzhi(T->lchild )+Dfenzhi(T->rchild );
}
/*计算二叉树的高度(深度*/
int depth (Bitree T)
{
int lh,rh;
if (T==NULL)
return 0;
else
{
lh=depth(T->lchild); //递归左子树
rh=depth(T->rchild); //递归右子树
return (lh>rh)?(lh+1):(rh+1); //高度等于左子树和右子树中大者加1 }
}
/*下面为主函数*/
void main()
{
Bitree T;
printf("先序创建二叉树,用空格代表虚结点：\n");
T=Createtree();
printf("先序遍历：\n");
preorder(T);
printf("\n");
printf("中序遍历：\n");
inorder(T);
printf("\n");
printf("后序遍历：\n");
postorder(T);
printf("\n");
printf("层序遍历：\n");
levelorder(T);
printf("\n");
printf("二叉树的节点数为:");
printf("%d个",num(T));
printf("\n");
printf("二叉树的叶子节点数为:"); printf("%d个",countleaf(T));
printf("\n");
printf("二叉树的单分支节点数为:"); printf("%d个",Sfenzhi(T));
printf("\n");
printf("二叉树的双分支节点数为:"); printf("%d个",Dfenzhi(T));
printf("\n");
printf("二叉树的高度（深度）为:"); printf("%d",depth(T));
printf("\n");
}
树与二叉树复习 一、填空 1、由二叉树的（中）序和（前、后）序遍历序列可以唯一确定一棵二叉树。 2、任意一棵二叉树，若度为0的结点个数为n0，度为2的结点个数为n2，则n0等于（n0=n2+1 ）。 3、一棵二叉树的第i（i≥1）层最多有（2i-1 ）个结点。 4、一棵有n个结点的二叉树，若它有n0个叶子结点，则该二叉树上度为1的结点个数n1=（n-2n0+1 ）。 5、在一棵高度为5的完全二叉树中，最少含有（ 16 ）个结点。 6、 2．有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当折半查找值为82的结点时，（ C ）次比较后查找成功。 A． 11 B 5 C 4 D 8 7、在有n个叶结点的哈夫曼树中，总结点数（ 2n-1 ）。 8、若一个问题的求解既可以用递归算法，也可以用递推算法，则往往用（递推）算法，因为（递推算法效率高）。 9、设一棵完全二叉树有700个结点，则共有（ 350 ）叶子结点。 10、设一棵完全二叉树具有1000个结点，该树有（500）个叶子结点，有（499 ）个度为2的结点，有（ 1 ）个结点只有非空左子树。 二、判断 1、( × )在哈夫曼树中，权值最小的结点离根结点最近。 2、( √ ) 完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。 3、( √ )二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 4、( × ) 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最大值一定在叶结点上。 5、( √ )若以二叉链表作为树和二叉树的存储结构，则给定任一棵树都可以找到唯一的一棵二叉树与之对应。 6、( √ )若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小
课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能： （1）建立二叉排序树； （2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 排序二叉树的建立及其遍历的实现
摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据 组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。 关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言 我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。 该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归 调用，这将极大的方便算法设计。 1．需求分析 建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。 该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。
一、下面是有关二叉树的叙述，请判断正误（） （）. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （）.二叉树中每个结点的两棵子树的高度差等于1。 （）.二叉树中每个结点的两棵子树是有序的。 （）.二叉树中每个结点有两棵非空子树或有两棵空子树。 （）二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点） （）.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （）.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （）.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1）（）用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n2=n0-1=5 二、填空（） 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n1+n2=0+ n2= n0-1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用 log2(n) +1= +1=9 4.设一棵完全二叉树有700个结点，则共有350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350
C语言实现二叉树的前序遍历算法实现一： #include
#include
数据结构第6章二叉树作业及答案教材
第六章树及二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n 2=n -1=5 ( ) 11、哈夫曼树中没有度为1的结点，所以必为满二叉树。 ( )12、在哈夫曼树中，权值最小的结点离根结点最近。 ( )13、线索二叉树是一种逻辑结构。 （√）14、深度为K的完全二叉树至少有2K-1个结点。 (√ )15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )16、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )17、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n 1+n 2 =0+ n 2 = n -1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用? log 2 (n) ?+1= ? 8.xx ?+1=9 4.设一棵完全二叉树有700个结点，则共有 350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。
实践三：树的应用 1.实验目的要求 通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。 实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。 能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。 2.实验主要内容 2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。 2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。 3．实验步骤 2.1实验步骤 ●输入p127二叉链表的定义 ●录入调试p131算法6.4，实现二叉树的构造函数 ●编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的 形式，以方便观察树的结构。 ●参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。 为简化编程，可以将visit函数直接使用printf函数输出结点内容来 代替。 #include
typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; // 构造栈的结构体 typedef BiTree SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack &S){ //构造一个空栈 S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S){ //若栈S为空栈，则返回TRUE,否则返回FALSE if(S.top==S.base) return 1; else return 0; }
二叉树前序、中序、后序遍历相互求法今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们分别说明。 首先，我们看看前序、中序、后序遍历的特性： 前序遍历： 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点 一、已知前序、中序遍历，求后序遍历 例： 前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下： 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。
实现二叉树中所有节点左右子树的交换 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】
数据结构课程设计 实验报告 题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院 专业班级：计算机科学与技术1003班 姓名：叶成功 学号： 指导教师：陈国良教授李立三教授 日期：2012年7月3日 目录
一、问题描述 二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。在二叉树的一些应用中，常常要求在树中查找具有某些特征的结点或者对树中全部结点逐一进行某种处理，这就提出了遍历二叉树。根据遍历的方向的不同，有前序遍历、中序遍历、后序遍历以及层序遍历。在本次课程设计中，要求学生通过编写程序完成对二叉树的一些操作，比如可以构造二叉树、打印二叉树、遍历二叉树以及对左右子树进行交换等等。
二、基本要求 要求：。构造一颗20个节点的完全二叉树或者20个节点以上的满二叉树。 实现如下步骤： （1）实现二叉树的构造过程，并打印出二叉树 （2）对该二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历； （3）将该二叉树的所有左右子树进行交换，得到新的二叉树，并打印出该二叉树； （4）对新获得的二叉树分别用层序、前序、中序和后序四种不同的方法进行遍历。 三、数据结构的设计 由数据结构中二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成，所以在本程序二叉树的构造是采用二叉链表的链式存储结构，链表中的结点应包含三个域：数据域和左、右孩子的指针域。这种存储结构可以方便二叉树的建立以及遍历。 1、结点的数据结构 structnode { chardata; structnode*lchild,*rchild; } 2、基本操作 voidCreate(BiTNode**p) 初始条件：按照结点的结构体构造二叉树； 操作结果：构造一棵二叉树。 voidPreOrderTraverse(BiTreeT)
#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************
#include
一、判断题 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）6.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）7.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i —1个结点。（应2i-1） （√）8.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）9.具有12个结点的完全二叉树有5个度为2的结点。 ( ) 10、哈夫曼树中没有度为1的结点，所以必为满二叉树。 ( )11、在哈夫曼树中，权值最小的结点离根结点最近。 ( )12、线索二叉树是一种逻辑结构。 （√）13、深度为K的完全二叉树至少有2K-1个结点。 (√ )14、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )15、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )16、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 （√）17、在二叉树结点的先序序列和后序序列中，所有叶子结点的先后顺序完全相同。（√）18、二叉树的遍历操作实际上是将非线性结构线性化的过程 （√）19、树的先根遍历序列与其所转化的二叉树的先序遍历序列相同。 （╳）20、树的后根遍历序列与其所转化的二叉树的后序遍历序列相同。 二、填空 1．由３个结点所构成的二叉树有 5 种形态。 2. 线索二叉树的左线索指向其_前驱_____，右线索指向其__后继____。 3．一棵具有257个结点的完全二叉树，它的深度为 9 。 4、如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数 为_69_____。 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。另外，最后一结点为2i属于 左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空 右不空的情况，所以非空右子树数＝0. 6. 一棵含有n个结点的k叉树，可能达到的最大深度为n，最小深度为 2 。
#include
二叉树的前序遍历、中序遍历、后续遍历 （递归法） 1、前序遍历（递归）： 算法实现一： #include
算法实现二： #include
习题五树与二叉树 一、选择题 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、欲实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳的方案是二叉树采用存储结构。 A、三叉链表 B、广义表 C、二叉链表 D、顺序表 12、以下说法错误的是。 A、存在这样的二叉树，对它采用任何次序遍历其结点访问序列均相同 B、二叉树是树的特殊情形 C、由树转换成二叉树，其根结点的右子树总是空的 D、在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树
实验二叉树及其先序遍历 一、实验目的： 1．明确了解二叉树的链表存储结构。 2．熟练掌握二叉树的先序遍历算法。 一、实验内容： 1．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算 机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的 语法结构，在数据库系统中，数形结构也是信息的重要组织形式。 2．节点的有限集合（N大于等于0）。在一棵非空数里：（1）、有且仅 有 一个特定的根节点；（2）、当N大于1时，其余结点可分为M（M大于0） 个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树 的定义是以递归形式给出的。 3．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉 树的子树有左右之分，其次序不能颠倒。 4．二叉树的结点存储结果示意图如下： 二叉树的存储（以五个结点为例）：
三、实验步骤 1．理解实验原理，读懂实验参考程序。 2． （1）在纸上画出一棵二叉树。 A B E C D G F (2) 输入各个结点的数据。 (3) 验证结果的正确性。 四、程序流程图 先序遍历
五、参考程序 # define bitreptr struct type1 /*二叉树及其先序边历*/ # define null 0 # define len sizeof(bitreptr) bitreptr *bt; int f,g; bitreptr /*二叉树结点类型说明*/ { char data; bitreptr *lchild,*rchild; }; preorder(bitreptr *bt) /*先序遍历二叉树*/ { if(g==1) printf("先序遍历序列为：\n"); g=g+1; if(bt) { printf("%6c",bt->data); preorder(bt->lchild); preorder(bt->rchild); } else if(g==2) printf("空树\n");
习题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-1 C. 2h+1 D. h+1 7. 对一个满二叉树，m 个树叶，n 个结点，深度为h ，则__A__ 。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2 h -1 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 C. bdgaechf D. gdbehfca 12. 在一非空二叉树的中序遍历序列中，根结点的右边__A__。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 13.如图6.1所示二叉树的中序遍历序列是__B__。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图 6.1 14. 一棵二叉树如图6.2所示，其中序遍历的序列为__B__。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 15．设a,b 为一棵二叉树上的两个结点，在中序遍历时，a 在b 前的条件是B 。 图6.2
习题六树和二叉树 一、单项选择题 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层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数 求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/ #include
/*void preorder(Bitree T) //先序遍历 { if(T) { printf("%c-",T->data); preorder(T->lchild); preorder(T->rchild); } } */ /*下面先序遍历二叉树非递归算法设计*/ void preorder(Bitree T) //先序遍历非递归算法设计{ Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p; int top=-1; //栈置空 if(T) { top++; st[top]=T; //根节点进栈 while(top>-1) //栈不空时循环 { p=st[top]; //栈顶指针出栈 top--; printf("%c-",p->data ); if(p->rchild !=NULL) //右孩子存在进栈 { top++; st[top]=p->rchild ; } if(p->lchild !=NULL) //左孩子存在进栈 { top++; st[top]=p->lchild ; } } printf("\n"); } }