以孩子兄弟链表作为存储结构,求树中节点x的第i个孩子

#include

#include

#define max 20

typedef struct node{

char data;

node *child,*brother;

}Tree;

Tree *Q1[max]; //用于记录父结点Tree *Q2[max]; //用于记录兄弟结点int front1=0,rear1=-1,front2=0,rear2=-1; Tree *Creatree(){ //创建以孩子兄弟链表为存储结构的树

Tree *T,*S;

char pa,ch;

int sign=0;

T=NULL;

printf("建立树，请输入结点信息及其父结点信息：\n");

scanf("%c%c",&ch,&pa);

while(ch!='#'){

int stop=1;

S=(Tree *)malloc(sizeof(Tree));

S->data=ch;

S->child=S->brother=NULL;

rear1++;

Q1[rear1]=S;

if(pa!='@'){ //父结点不为空

rear2++;

Q2[rear2]=S;

while(stop){

if(pa==Q1[front1]->data&&sign==0){

Q1[front1]->child=S;

sign=1;

stop=0;

}

else

if(pa==Q1[front1]->data&&sign!=0){

Q2[front2]->brother=S;

front2++;

stop=0;

}

else{

front1++;

if(Q2[front2]->data!=ch)

front2++;

sign=0;

}

}

scanf("%c%c",&ch,&pa);

}

else{ //父结点为空

T=Q1[front1];

scanf("%c%c",&ch,&pa);

}

}

return T;

}

Tree *WHOLE=NULL; //设置全局变量，来存储树中与结点x值相等的结点

void Seek_root(Tree *T,Tree *x){ //在树中查找与结点x值相等的结点

if(T!=NULL){

if(T->data==x->data)

WHOLE=T;

else{

Seek_root(T->child,x);

Seek_root(T->brother,x);

}

}

}

Tree *Search_child(Tree *T,Tree *x,int i){ //查找结点x的第i个孩子

Tree *p,*q;

int mark=1;

Seek_root(T,x);

if(WHOLE==NULL) //结点x没有第i个孩子

q=WHOLE;

else{ //结点x有第i个孩子

q=WHOLE->child;

while(mark!=i){

q=q->brother;

mark++;

}

}

return q;

}

void main(){

Tree *T,*x,*s;

int i;

char ch;

T=Creatree();

printf("请输入x与i(结点x的第i个孩子):\n");

scanf("%c%d",&ch,&i);

x=(Tree *)malloc(sizeof(Tree));

x->data=ch;

x->child=x->brother=NULL;

s=Search_child(T,x,i);

if(s!=NULL)

printf("结点%c的第%d个孩子是%c!\n",ch,i,s->data);

else

printf("结点%c没有第%d个孩子!\n",ch,i);

}

树-顺序存储完全二叉树先、中、后序遍历-实验内容与要求

数据结构实验报告 知识范畴：树完成日期：2016年04月28日 实验题目：顺序存储完全二叉树先、中、后序遍历 实验内容及要求： 输入一个字符串，存储于一维数组。以该一维数组作为完全二叉树的存储结构，实现先、中、后序遍历，输出遍历结果。 将该完全二叉树转换为二叉链表存储结构，然后基于二叉链表存储结构再次进行先、中、后序遍历并输出遍历结果。 实验目的：掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。 数据结构设计简要描述： 分别以一维数组和二叉链表为存储结构存储二叉树，并实现先序、中序、后序遍历。 算法设计简要描述： 分别以一维数组和二叉链表为存储结构存储二叉树。 以一维数组存储时，假设双亲结点的下标为i，则左儿子、右儿子的下标分别为2*i+1、2*i+2。利用递归算法分别对左子树和右子树进行遍历。 以二叉链表为存储结构时，结点数据域存储结点数据，然后依次递归左子树和右子树。输入/输出设计简要描述： 本实验中输入和输出分别只有一次。 输入：输入一个字符串，存储到一维数组中 输出：分别以一维数组和二叉链表为存储结构存储二叉树时，先序、中序、后序遍历结果。编程语言说明： 1.编程软件，CodeBlocks 16.0； 2.代码均用C++语言实现； 3.输入输出采用C++语言的cout和cin函数； 4.程序注释采用C/C++规范； 5.动态存储分配采用C++的new和delete操作符实现 主要函数说明： void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历void trans_tree(BiT &bt,char *s,int count,int t) //将该完全二叉树存储结构转换void preorder(BiT bt) //以二叉链表前序遍历 void midorder(BiT bt) //以二叉链表中序遍历 void lasorder(BiT bt) //以二叉链表后序遍历 程序测试简要报告：

数据结构求二叉树深度和度为2的节点个数代码实现

/* 求二叉树的深度 求二叉树度为2的节点个数 附带详细注释 */ # include # include //二叉树的节点结构体 typedef struct Tnode { char data; struct Tnode * lchild; struct Tnode * rchild; }NODE, * PTNODE; typedef int Status; //定义一个全局变量,用于统计度为2的节点 int count = 0; # define OK 1 # define ERROR 0 //创建一个二叉树 Status CreatTree( PTNODE & ); //先序遍历二叉树 Status InOrderTraveler( PTNODE & ); //求出树的深度 Status DeepTree( PTNODE & ); //求出树中度为2的节点个数 Status TwoDegreeNode( PTNODE & ); /* 先序创建一颗二叉树 这段代码在前面已经写烂~~( ﹁﹁) ~~~ */ Status CreatTree( PTNODE & T ) { char data; scanf( "%c", &data ); if( ' ' == data ) {

T = NULL; //如果是#，说明是一颗空树 } else { //节点有值，则创建这个节点 T = ( PTNODE )malloc( sizeof( NODE ) ); if( NULL == T ) { printf( "节点动态空间分配失败\n" ); return ERROR; } T -> data = data; CreatTree( T -> lchild ); CreatTree( T -> rchild ); } return OK; } /* 先序遍历二叉树 同样的，这一段代码也同样是写烂了 写这段代码的作用是为了检查刚刚那个二叉树生成了没*/ Status InOrderTraveler( PTNODE &T ) { if( NULL != T ) { printf( "%c", T -> data ); InOrderTraveler( T -> lchild ); InOrderTraveler( T -> rchild ); } return OK; } /* 求出二叉树的深度，这个才是今天的猪脚 */ int DeepTree( PTNODE & T ) { //设置两个整型变量，用于接收左子树和右子树的深度int LDeep, RDeep; if( NULL == T )

《数据结构》习题集：_树和叉树

第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]

小学生趣味数学(低年级)

小学生趣味数学（低年级） 第一册 一、智力训练之一观察填图

20．在右图中找出与左图相反的图形来，填在（）里。 答案：

二、智力训练之二观察填数A组： B组：

16． 17．在图的空格里填一个数字，使横行和竖行中的三个数字的和等于8。 18．在图的空格里填一个数字，使横行和竖行中的三个数字的和都等于9。 19．在图1－43的空格里填一个数字，使横行和竖行中的三个数字的和都等于10。 20．把1、2、3、4、5五个数字分别填入图中的五个方格中，填完后要求横行三个数的和等于竖行三个数的和。

答案： A组：1．？1＝7，？2=3；2．？1=2，？2=8；3．5个；4．3个；5．1至5行分别填3，4，5，6，7；6．8个，16个。 B组：7．10个；8．6个；9．0，1，3，4，6，9；10．2，3，6，8，9；11．？1＝1，？2＝7，？3＝3；12．8。 C组：13．8个；14．10个；15．6个；16．12个；17．1；18．3；19．5。20．有以下几种填法： 三、智力训练之三奇问妙答 A组： 1．鱼缸里有9条金鱼，走近一看死了两条，这时鱼缸里还有几条金鱼？ 2．王爷爷共有三个儿子都结婚了，王爷爷还有几个儿子？ 3．屋内亮着7盏灯，关掉3盏，屋里还有几盏灯？ 4．父子俩对手下棋，每人都下了五盘，他们共下了几盘棋？

5．一面五星红旗上有两种颜色（红、黄），10面五星红旗上共有多少种颜色？ 6．《趣味数学》这本书叫什么名字？ B组： 7．一个人唱完《学雷锋》这支歌用2分钟，3个人唱完《学雷锋》这支歌最少用几分钟？ 8．妈妈煮熟一个鸡蛋要用8分钟，煮熟三个鸡蛋最少要用几分钟？ 9．划着一根火柴用1秒钟，划着4根火柴最少用几秒钟？10．3个人合下了3小时跳棋，每人下了几小时？ 11．三匹马拉着一台大车向前跑了6米，每匹马向前跑了多少米？ 12．一位老师到学生家去家访，看到妈妈面前有3个女孩，便问：“你只有这三个女儿吗？”妈妈说：“何止这3个，她们每人都有一个哥哥。”请问这家共有几个孩子？ C组： 13．树上落了3只鸟，猎人开枪打下一只，树上还有几只？ 14．沙滩上落了3只鸟，猎人开枪打死一只，沙滩上还有几只鸟？ 15．平放的桌面上落了3只苍蝇，有人打死了一只，桌面上还有几只？

树结构习题及答案

第5章树 【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 解： （1）叶子结点有：B 、D 、F 、G 、H 、I 、 J 。 （2）非终端结点有：A 、C 、E 。 （3）每个结点的度分别是：A 的度为4，C 的度为2，E 的度为3，其余结点的度为0。 （4）树的深度为3。 【例5-7】如图5-5所示的二叉树，要求： （1）写出按先序、中序、后序遍历得到的结点序列。 （2）画出该二叉树的后序线索二叉树。 解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA b a c d e f 图5-5 A B C D E F G H I J 图5-4

（2）其后序线索二叉树如图5-6所示。 5％、、G 、H 的 3.假定一棵三叉树的结点数为50，则它的最小高度为（3.C ）。 A.3 B.4 C.5 D.6 4.在一棵二叉树上第4层的结点数最多为（4.D ）。 第六步： 25 30 9 9 18 7 12 8 15 27 43 图5-13

A.2 B.4 C.6 D.8 5.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（5.B）。 A.R[2i+1] B.R[2i] C.R[i/2] D.R[2i-1] 6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（6.D）。 A.24 B.48 C.72 D.53 7.线索二叉树是一种（7.C）结构。 A.逻辑 B.逻辑和存储 C.物理 D.线性 8.线索二叉树中，结点p没有左子树的充要条件是（8.B）。 A.p->lc=NULL B.p->ltag=1 C.p->ltag=1且p->lc=NULL D.以上都不对 9.设 10. A. 11. A. 12. A. B. C. D. 13. A. C. 14. A. 15. A. C. 1. 2. 3. 4. 5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（5.×） 6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（6.√） 7.根据任意一种遍历序列即可唯一确定对应的二叉树。（7.√） 8.满二叉树也是完全二叉树。（8.√） 9.哈夫曼树一定是完全二叉树。（9.×） 10.树的子树是无序的。（10.×） 三、填空题 1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。1.3，4，6，1，1，2，A，F，G

二叉树的顺序存储结构

#include #include #define VirNode ' ' /* 用空格符描述“虚结点”*/ #define MAXSIZE 64 typedef char ElemType; typedefElemTypeSqBitTree[MAXSIZE]; void crebitree(SqBitTreeBT,int n) /* n为二叉树真实结点数*/ { inti,j,m; i=1; m=0; while(m

{ inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]==VirNode&&BT[2*i+1]==VirNode) n++; for(;i<=BT[0];i++) if(BT[i]!=VirNode) n++; return n; } int countn1(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&(BT[2*i]==VirNode&&BT[2*i+1]!=VirNode|| BT[2*i]!=VirNode&&BT[2*i+1]==VirNode)) n++; return n; } int countn2(SqBitTree BT) { inti,n=0; for(i=1;i<=BT[0]/2;i++) if(BT[i]!=VirNode&&BT[2*i]!=VirNode&&BT[2*i+1]!=VirNode) n++; return n; } //主函数 void main() { SqBitTree T; int n; crebitree(T,5); levellist(T); printf("High=%d\n",high(T)); levellist(T); printf("n2=%d\n",countn2(T)); getch(); }

二叉树的建立与先序中序后序遍历 求叶子节点个数 求分支节点个数 求二叉树的高度

/*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数 求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/ #include //c语言的头文件 #include//c语言的头文件stdlib.h千万别写错了 #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"); } }

31构建二叉树的二叉链表存储结构

Computer Education教育与教学研究 文章编号：1672-5913(2008)06-0066-03 构建二叉树的二叉链表存储结构 王岁花，岳冬利 (河南师范大学 计算机与信息技术学院，新乡 453007) 摘要：本文根据笔者多年的教学经验，介绍了四种构建二叉树的二叉链表存储结构的方法。 关键词：二叉树；链表；存储结构；递归 中图分类号：G642 文献标识码：B 1 引言 《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》中将“计算机科学与技术”专业名称下的人才培养规格归纳为三种类型、四个不同的专业方向：科学型(计算机科学专业方向)、工程型(包括计算机工程专业方向和软件工程专业方向)、应用型(信息技术专业方向)。“数据结构”课程出现在四个专业方向的核心课程中，而树型结构同样无一例外的出现在了四个专业方向的核心知识单元中。 树型结构描述的是研究对象之间一对多的关系。在存储树时，如果用指针来描述元素之间的父子关系，则由于对每个元素的孩子数量没有限制(最小可以是0，最多可以是树的度d)，若结点的结构定义为一个数据域data和d个指针域，则可以证明，有n个结点、度为d的树的多重链表存储结构中，有n*(d-1)+1个空链域，采用这样的存储将造成很大的浪费。 二叉树是树型结构的一种特殊情况，对于它的操作和存储要比树简单的多，且树和森林可以用二叉链表做媒介同二叉树进行相互转换，所以对二叉树的研究就显得特别重要。 二叉树的二叉链表存储是二叉树的一种重要的存储结构，在每一本“数据结构”教材中都占据了一定的篇幅，但对于怎样建立一棵二叉树的二叉链表存储结构，却很少提及。笔者从事“数据结构”课程教学已二十余年，总结出了以下四种构建方法，希望能对同仁和学数据结构的学生有所帮助。通过本文的学习，学生将会对二叉链表和递归有更深入的理解。 2 二叉树的二叉链表存储结构构建方法 假设有关二叉树的二叉链表存储的类型定义如下： typedef struct BiTNode{ // 结点结构ElemType data ；//数据域 struct BiTNode *Lchild ；//左孩子指针 struct BiTNode *Rchild；//右孩子指针} BiTNode ，*BiTree ； 说明：ElemType为二叉树的元素值类型，根据具体情况进行定义，本文假设为char型；BiTNode为结点类型；BiTree为指向BiTNode的指针类型。下面的算法均用类C 描述。 2.1 利用扩展二叉树的先序序列构建 只根据二叉树的先序序列是不能唯一确定一棵二叉树的。针对这一问题，可做如下处理：对二叉树中每个结点的空指针引出一个虚结点，设其值为#，表示为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树的先序序列可唯一确定这棵二叉树。如图1所示，给出了一棵二叉树的扩展二叉树，以及该扩展二叉树的先序序列。 收稿日期：2007-12-15 作者简介：王岁花，副教授，主要研究方向是语义Web和课程教学论。 项目资助：河南师范大学教学研究基金资助 66

数据结构(树与图部分)练习题

1 数据结构(树与图部分)练习题 一、填空题 1. 不考虑顺序的3个结点可构成种不同形态的树，种不同形态的二叉树。 2. 已知某棵完全二叉树的第4层有5个结点，则该完全二叉树叶子结点的总数为：。 3. 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是。 4. 一棵具有110个结点的完全二叉树，若i ＝54，则结点i 的双亲编号是；结点i 的左孩 子结点的编号是，结点i 的右孩子结点的编号是。 5. 一棵具有48个结点的完全二叉树，若i ＝20，则结点i 的双亲编号是______；结点i 的左孩子结点编号是______，右孩子结点编号是______。 6. 在有n 个叶子结点的Huffman 树中，总的结点数是：______。 7. 图是一种非线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的非空有限 集合，E(G)是______的有限集合。 8. 遍历图的基本方法有优先搜索和优先搜索两种方法。 9. 图的遍历基本方法中是一个递归过程。 10. n 个顶点的有向图最多有条弧；n 个顶点的无向图最多有条边。 11. 在二叉树的二叉链表中，判断某指针p 所指结点是叶子结点的条件是。 12. 在无向图G 的邻接矩阵A 中，若A[i,j]等于1，则A[j,i]等于。 二、单项选择题 1. 树型结构的特点是：任意一个结点：（ ） A 、可以有多个直接前趋 B 、可以有多个直接后继 C 、至少有1个前趋 D 、只有一个后继 2. 如下图所示的4棵二叉树中，（ ）不是完全二叉树。 A B C D 3. 深度为5的二叉树至多有（ ）个结点。 A 、16 B 、32 C 、31 D 、10 4. 64个结点的完全二叉树的深度为：（ ）。 A 、8 B 、7 C 、6 D 、5 5. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编 号，根结点编号为1，则编号为49的结点的左孩子的编号为：（ ）。 A 、98 B 、99 C 、50 D 、48 6. 在一个无向图中，所有顶点的度之和等于边数的（ ）倍。 A 、1/2 B 、1 C 、2 D 、4 7. 设有13个值，用它们组成一棵Huffman 树，则该Huffman 树中共有()个结点。

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质

二叉树的单分支结点个数(精)

# include # include typedef char TElemType;//把二叉树的类型定义为字符型 typedef struct node { TElemType data; struct node *lchild,*rchild; }BiTNode,*BiTree; void InitBiTree(BiTree *root) { (*root)=NULL; } //递归的方法创建一棵二叉树 void Create(BiTree *root) { TElemType x; scanf("%c",&x); getchar(); if(x=='0') return ; else { (*root)=(BiTNode*)malloc(sizeof(BiTNode)); (*root)->data=x; (*root)->lchild=(*root)->rchild=NULL; Create(&((*root)->lchild)); Create(&((*root)->rchild)); } } void PreOrder(BiTree root)//先序遍历二叉树，root为指向二叉树根结点{ if(root!=NULL) { printf("%c ",root->data);//访问根结点 PreOrder(root->lchild);//先序遍历左子树 PreOrder(root->rchild);//先序遍历右子树 } } int OncechildNum(BiTree root) { if(root==NULL) return 0; else if(root->lchild==NULL&&root->rchild==NULL) return 0; else

小学数学三年级下册思维训练

三年级（下册）数学思维训练习题 单元目录 第一单元除数是一位数的除法 第二单元除数是一位数除法的应用题 第三单元年、月、日 第四单元年、月、日的应用题 第五单元平移和旋转 第六单元两位数乘两位数的乘法 第七单元两位数乘两位数的乘法应用题 第八单元认识千米 第九单元认识吨 第十单元轴对称图形 第十一单元认识分数（一） 第十二单元认识分数（二） 第十三单元长方形和正方形面积（一） 第十四单元长方形和正方形面积（二） 第十五单元统计与平均数 第十六单元认识小数（一） 第十七单元认识小数（二） 第十八单元观察物体

第一单元除数是一位数的除法 1、要使□36÷4的商是三位数，□里最小填（）。 要使□36÷4的商是两位数，□里最大填（）。 要使2□8÷8的商是三十多，□里可能填（）。 2、一个三位数除以7商是75，有余数，余数最大是（），这时 被除数是（）。 3、在□里填上什么数，商中间有0？ 6）6□2 4、在□÷7=9……□中，被除数可能有几个？其中最大是几？最小是几？ 5、 3 □ □）3 □□ □□ □□ □ 3 8 6、 7 □ 5）□□□ □ 5 □□ 4 5

第二单元除数是一位数除法的应用题 8、养殖场有300只鸡，鸡的只数是兔的3倍，把兔放在4个笼子里，平均每个笼子里有多少只兔？ 9、两个水桶共盛水60千克，如果第一桶水倒出4千克则两个桶中的水同样多，求第一桶里原来盛水多少千克？ 10、小明与小华共有图书160本，已知小明图书的本数是小华的3倍，求小明、小华各有图书多少本？ 11、王庄有小麦、水稻田共180亩，小麦的亩数是水稻的2倍。王庄有小麦、水稻各多少亩？ 12、学校图书馆有科技书和文艺书共2400本，文艺书的本数是科技书的4倍。两种书各有多少本？ 13、爸爸与儿子的年龄和是45岁，又知爸爸的年龄是儿子的4倍，爸爸与儿子今年各多少岁? 第三单元年、月、日 14、从上午8时到下午5时经过（）。

树结构习题及答案

【例5-1】写出如图5-1所示的树的叶子结点、非终端结点、每个结点的度及树深度。 A B C D E F G H I J 图5-1 解： （1）叶子结点有：B、D、F、G、H、I、J。 （2）非终端结点有：A、C、E。 （3）每个结点的度分别是：A的度为4，C的度为2，E的度为3，其余结点的度为0。 （4）树的深度为3。 【例5-2】一棵度为2的树与一棵二叉树有什么区别？ 解：度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。 【例5-3】树与二叉树有什么区别？ 解：区别有两点： （1）二叉树的一个结点至多有两个子树，树则不然； （2）二叉树的一个结点的子树有左右之分，而树的子树没有次序。 【例5-4】分别画出具有3个结点的树和三个结点的二叉树的所有不同形态。 解：如图5-2(a)所示，具有3个结点的树有两种不同形态。 图5-2(a) 如图5-2(B)所示，具有3个结点的二叉树有以下五种不同形态。 图5-2(b) 【例5-5】如图5-3所示的二叉树，试分别写出它的顺序表示和链接表示（二叉链表）。 解： （2）该二叉树的二叉链表表示如图5-4所示。

【例5-6】试找出满足下列条件的所有二叉树： （1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。 解： （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 【例5-7】如图5-5所示的二叉树，要求： （1）写出按先序、中序、后序遍历得到的结点序列。 （2）画出该二叉树的后序线索二叉树。 解： （1） 先序遍历序列：ABDEFC 中序遍历序列：DEFBAC 后序遍历序列：FEDBCA （2）其后序线索二叉树如图5-6所示。 b a c d e f 图5-5 图5-6

二叉树叶子结点个数计算

计算二叉树叶子结点 1.程序设计简介 已知一棵二叉树，求该二叉树中叶子结点的个数。 2.基本要求 （1）设计二叉树的二叉链表为存储结构 （2）设计求叶子结点个数的递归算法 （3）输入：一颗二叉树 （4）输出：二叉树中叶子结点的个数 3.实现提示 （1）存储设计 二叉树采用二叉链表为存储结构 (2)算法设计 求二叉树中叶子结点个数，即求二叉树的所有结点中左、右子树均为空的结点个数之和。可以将此问题转化为遍历问题，在遍历中“访问一个结点”时判断该结点是不是叶子，若是则将计数器累加。 4.源程序 #include #include using namespace std;

struct BiNode 行与测试 6.调试感想 非递归算法求叶子结点的个数 #include #include using namespace std; struct node { int data; node *lchild; node *rchild; }; node *root=NULL; void mid(node*root,int key=500) { int sum=0; stacks; while(NULL!=root || !()) { if(NULL!=root) {

(root); root=root->lchild; } else { root=(); // cout<data<<" "; if(NULL==root->lchild && NULL==root->rchild) ++sum; (); root=root->rchild; } } cout<data=100; node *a=new node; node *b=new node; node *a1=new node; node *a2=new node; node *b1=new node; node *b2=new node; a->data=200; b->data=300; a1->data=400; a2->data=500; b1->data=600; b2->data=700; root->lchild=a; root->rchild=b; a->lchild=a1; a->rchild=a2;

实验报告二叉树求叶子结点数目(内容清晰)

实验叶子结点的计算 姓名：xxx 班级：xxx） 学号：16130xxxxx 时间2017.10.22 1 问题描述 二叉树叶子节点的计算 1.二叉树的创建 2.二叉树的图形显示 3.二叉树叶子节点的计算 2 结构设计 二叉树叶子结点的计算主要是二叉树的创建，在这里选择的存储结构是一个链式存Data lchild rchild struct BTNode{ int data; BTNode*lchild; BTNode*rchild; }; 3 算法设计 在程序正式编写之前我定义了几个功能函数 （1）指针清空函数，预定义一个指针bt 使lchild和rchild的值分别赋予bt并且使其为空 static int clear(BTNode *bt) { if (bt) { clear(bt->lchild ); clear(bt->rchild ); cout<<"释放了指针"<

{ if(p->lchild==NULL&&p->rchild==NULL)count++; Leaf(p->lchild,count); Leaf(p->rchild,count); } return count; } （2）二叉树的创建 同样是利用递归的方式，输入参数包括指针，左右判断，以及判空条件static int create(BTNode *p,int k ,int end) { BTNode *q; int x; cin>>x; if(x!=end) { q=new BTNode; q->data =x; q->lchild=NULL; q->rchild=NULL; if(k==1)p->lchild=q; if(k==2)p->rchild=q; create(q,1,end); create(q,2,end); } return 0; }; （3）类的构造函数创建树并且输入各结点数值 在这里，采用的时先序遍历法依次输入树中的各结点数值 Step 1:定义新的结构体指针， Step 2:申请动态存储空间； Step 3:输入节点元素，并且指针后移到输入结点的后继结点，end作为结点结束标志； Step 4:重复步骤3，直到输入结束； void BinaryTree::CreateBiTree (int end) { cout<<"请按照先序序列的顺序输入二叉树，-1为空指针域标志："<>x; if(x==end)return; p=new BTNode;

希望杯培训题

希望杯培训题 一．选择题（以下每题的四个选择中，仅有一个是正确的） 1．－7的绝对值是（） （A）－7 （B）7 （C）－（D） 2．1999－的值等于（） （A）－2001 （B）1997 （C）2001 （D）1999 3．下面有4个命题： ①存在并且只存在一个正整数和它的相反数相同。 ②存在并且只存在一个有理数和它的相反数相同。 ③存在并且只存在一个正整数和它的倒数相同。 ④存在并且只存在一个有理数和它的倒数相同。 其中正确的命题是：（） （A）①和②（B）②和③ （C）③和④（D）④和① 4.4ab c的同类项是（） （A）4bc a（B）4ca b（C）ac b（D）ac b 5．某工厂七月份生产某产品的产量比六月份减少了20％，若八月份产品要达到六月份的产量，则八月份的产量比七月份要增加（） （A）20％（B）25％（C）80％（D）75％ 6．，，，四个数中，与的差的绝对值最小的数是（）（A）（B）（C）（D） 7．如果x=?, Y=0.5,那么X?Y?2X的值是( )

(A)0 (B) (C) (D) ? 8.ax+b=0和mx+n=0关于未知数x的同解方程，则有（） （A）a+m>0. （B）mb≥an. （C）mb≤an.（D）mb=an. 9．（－1）＋（－1）－（－1）×（－1）÷（－1）的结果是（）（A）－1 （B）1 （C）0 （D）2 10．下列运算中，错误的是（） （A）2X＋3X＝5X（B）2X－3X＝－1 （C）2X?3X＝6X（D）2X÷4X＝ 11．已知a<0,化简，得( ) (A) 2 (B) 1 (C) 0 (D) －2 12．计算（－1）＋（－1）÷|－1|的结果是（）（A）0 （B）1 （C）－1 （D）2 13．下列式子中，正确的是（） （A）a?a=a. （B）(x)=x. （C）3=9. （D）3b?3c=9bc. 14.－|－3|的相反数的负倒数是（）

数据结构习题 树 数据机构c语言版

1.设二叉树bt 的存储结构如下，其中bt为树根结点指针，left，right分别为结 点的左、右孩子指针，dada为结点的数据域。请完成下列各题： 1）画出二叉树bt的逻辑结构 2）写出按先序、中序、后序遍历二叉树所得到的结点序列 3）画出二叉树bt的后序线索化树 1 2 3 4 5 6 7 8 9 10 2.二叉树结点数值采用顺序存储结构，如图所示， 1）画出二叉树表示 2）写出前序遍历，中序遍历和后序遍历的结果 3）写出结点值c的父结点，其左、右孩子。 4）画出将此二叉树还原成森林的图

3.已知一棵二叉树的中序序列为cbedahgijk，后序序列为cedbhjifa，画出该二叉 树的先序线索二叉树。 4.有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、 2、9，试画出对应的Huffman树（请按左子树根结点的权小于等于右子树根结点 的权的次序构造），求出每个字符的Huffman编码。 5.设给定权集w={2，3，4，8，9}，试构造关于w的一棵哈夫曼树，并求其加权路 径长度WPL。 6.假设二叉树采用链接存储方式存储，编写一个中序遍历二叉树的非递归过程。 7.假设二叉树采用链接存储方式存储，root指向根结点，p所指结点为任一给定的 结点。编写一个求出从根结点到p所指结点之间路径的函数。 8.在二叉树中查找值为x的结点，试设计打印值为x的结点的所有祖先的算法，假 设值为x的结点不多于1个。 9.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的所有 结点数。 10.假设二叉树采用链接存储方式存储，试设计一个算法计算一棵给定二叉树的单孩 子结点数。

数据结构练习(二叉树)

数据结构练习（二叉树） 学号31301374 姓名张一博班级软件工程1301 . 一、选择题 1．按照二叉树定义，具有3个结点的二叉树共有 C 种形态。 (A) 3 (B) 4 (C) 5 (D) 6 2．具有五层结点的完全二叉树至少有 D 个结点。 (A) 9 (B) 15 (C) 31 (D) 16 3．以下有关二叉树的说法正确的是 B 。 (A) 二叉树的度为2 (B)一棵二叉树的度可以小于2 (C) 至少有一个结点的度为2 (D)任一结点的度均为2 4．已知二叉树的后序遍历是dabec，中序遍历是debac，则其前序遍历是 D 。 （A）acbed （B）decab (C) deabc (D) cedba 5．将一棵有1000个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为 B 。 (A) 98 (B) 99 (C) 50 (D) 没有右孩子 6．对具有100个结点的二叉树，若有二叉链表存储，则其指针域共有 D 为空。 (A) 50 (B) 99 (C) 100 (D) 101 7．设二叉树的深度为h，且只有度为1和0的结点，则此二叉树的结点总数为 C 。 (A) 2h (B) 2h-1 (C) h (D) h+1 8．对一棵满二叉树，m个树叶，n个结点，深度为h，则 D 。 (A) n=h+m (B) h+m=2n (C)m=h-1 (D)n=2h-1 9．某二叉树的先序序列和后序序列正好相反，则下列说法错误的是 A 。 (A) 二叉树不存在 (B) 若二叉树不为空，则二叉树的深度等于结点数 (C) 若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子 (D) 若二叉树不为空，则任一结点的度均为1 10．对二叉树的结点从1开始进行编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 A 遍历实现编号。 (A) 先序(B)中序(C)后序(D)层序 11．一个具有1025个结点的二叉树的高h为 C 。 (A) 10 (B)11 (C)11~1025 (D)10~1024 12．设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 C 。 ( A) n在m右方(B)n是m祖先 (C) n在m左方(D) n是m子孙 13．实现对任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用 C 存储结构。 (A) 二叉链表(B) 广义表(C)三叉链表(D)顺序 14. 一棵树可转换成为与其对应的二叉树，则下面叙述正确的是 A 。 (A) 树的先根遍历序列与其对应的二叉树的先序遍历相同 (B) 树的后根遍历序列与其对应的二叉树的后序遍历相同 (C) 树的先根遍历序列与其对应的二叉树的中序遍历相同 (D) 以上都不对 二、填空题 1．对一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度；当它为单分支二叉树时，具有最大高度。