二叉树建立、遍历、树形输出（c++）实现
#include
#include
static int figure=0;//所含结点个数
char result[100]={0};//记录层次遍历的结果
class BTreeNode //二叉树结点
{ char data;
BTreeNode *leftchild,*rightchild;
public:
friend class QNode;
friend class BTree;
BTreeNode(char &e,BTreeNode *l=NULL,BTreeNode *r=NULL) {data=e;leftchild=l;rightchild=r;}
};//BTreeNode
class QNode //队列结点
{ BTreeNode* node;
QNode *next;
public:
friend class LinkQuene;
QNode(BTreeNode *t=NULL)
{node=t;next=NULL;}
};//QNode
class LinkQuene //队列类定义
{ QNode *front,*rear;
public:
LinkQuene(){ rear=front=new QNode();}
voidInQuene(BTreeNode*);
BTreeNode *OutQuene();
};//LinkQuene
voidLinkQuene::InQuene(BTreeNode* item=NULL)
{ rear->next=new QNode(item);
rear=rear->next;
}
BTreeNode *LinkQuene::OutQuene() //队列返回结点{ QNode *p;
p=front->next;
BTreeNode *t=p->node;
front->next=p->next;
delete p;
if(!front->next)
rear=front;
return t;
}
class BTree{ //二叉树类定义
public:
void CreateBTree(BTreeNode *&);//建立二叉树intGetLeavesNum(BTreeNode *&);//计算二叉树的叶结点个数void InOrder(BTreeNode *&);//中序遍历
int Height(BTreeNode *&);//计算二叉树高度
void DrawTree(BTreeNode *&);//画二叉树
};
void BTree::CreateBTree(BTreeNode *&t)//建立二叉树实现
{ char u;
cin>>u;
if(u=='*')
{figure++;t=NULL;}
else
{ t=new BTreeNode(u);
figure++;
CreateBTree(t->leftchild);
CreateBTree(t->rightchild);
}
}
intBTree::Height(BTreeNode *&t)//计算二叉树高度实现
{ if(!t)return 0;
inthl,hr;
hl=Height(t->leftchild);
hr=Height(t->rightchild);
return hl>hr?++hl:++hr;
}
void BTree::InOrder(BTreeNode *&t)//中序遍历二叉树实现
{ if(t)
{ InOrder(t->leftchild);
cout<
InOrder(t->rightchild);
}
}
intBTree::GetLeavesNum(BTreeNode *&t)//求叶节点个数实现{ if(!t)
return 0;
else if(t->leftchild==NULL&&t->rightchild==NULL)
return 1;
else
return (GetLeavesNum(t->leftchild)+GetLeavesNum(t->rightchild)); }
void BTree::DrawTree(BTreeNode *&t)//画二叉树实现
{ char c='*';
LinkQuenequene;
BTreeNode *q=new BTreeNode(c);
BTreeNode *p=t;
if(p)quene.InQuene(p);
for(int i=0;i { p=quene.OutQuene(); result[i]=p->data; if(p->data) { if(p->leftchild) quene.InQuene(p->leftchild); else quene.InQuene(q); if(p->rightchild) quene.InQuene(p->rightchild); else quene.InQuene(q); } } } void main() { BTreebinarytree; int h=0,times=1,r=0;//times表示层次，h高度 BTreeNode *root=NULL; cout<<"输入二叉树各结点的值（“*”表示遇到空指针）："< if(!root) cout<<"空二叉树！"< else { cout<<"中序遍历结果输出："< binarytree.InOrder(root); cout<<"\n叶结点个数为：\n"; cout< cout<<"二叉树的高度是：\n"< h=binarytree.Height(root); cout<<"\n画出二叉树：\n"; binarytree.DrawTree(root); while(times<=h)//控制输出 { for(int i=0;i cout<<" ";//控制每行开头的空格 for(int j=0;j cout< else cout<<" "; for(int k=0;k cout<<" ";//每行内部空格控制} cout< times++; }//while } } 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型 (提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include 课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）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．数据结构设计 本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。 第六章 树和二叉树 一、选择题 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 ） 实验课题一：将下图中得二叉树用二叉链表表示： 1用三种遍历算法遍历该二叉树，给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点，根据其就是否属于该树，输出tｒｕe或者f ａｌse。 3写函数完成习题4、31(Ｃ＋+版)或4、2８（C版教科书）。 #iｎclｕde "stdio、h＂ ＃incluｄe”mallｏc、h" typedｅfｓtruct BｉTＮode ｛ cｈar data; sｔrucｔBiTＮode *lｃｈild,*rｃhiｌd; }ＢiTＮodｅ，*BiTrｅe； BｉＴree Creaｔe（BｉTｒeｅT) ｛ char ch； ch=getchａｒ(）; ｉｆ(ch=='#’） T=NULL; elｓe { T=(BiＴNode *）maｌloc(sｉｚｅｏf（ＢiTNｏｄe)）; Ｔ-〉data=ｃh； Ｔ-＞lｃｈiｌd=Creaｔe(T—〉lchilｄ); T—〉rchild=Creａte(Ｔ－〉rchｉld）； ｝ retuｒn Ｔ； } ｉnt node(BiＴrｅe Ｔ) { int sum1=0，a,b; ?iｆ（T) ｛ if（Ｔ！=ＮUＬL） ??sｕm1++; ?ａ=ｎode（Ｔ->lchiｌd); sｕm1＋=ａ； b=node(T—>rchｉld)； sum1+=b; ?} ｒetｕrn sum1； } int mｎode（BiTree T） { ?int sum２=0,ｅ，ｆ； if（T) { ?ｉf（（T->lcｈiｌd!=NULL）&＆(T－〉rchild!=NULL）)?sum2++； ?e=ｍnoｄｅ（Ｔ－〉lchild); suｍ2＋=e; f＝mnoｄｅ（T－〉rchｉｌd)； sum２+=f； ?｝ retｕrn sum2; ｝ void Preorｄer（BiTree T) { ｉf(Ｔ） { pｒintf（＂%c”，T－>daｔa)； Ｐreoｒder(Ｔ—>lchiｌｄ）； Ｐreorder（T－〉rchｉld）； ｝ } iｎt Sumｌeaｆ（BiTｒｅe T) { int suｍ=0,m，n; if（T） { if((！T-〉lchild）&&（!T-〉rｃhiｌd)) sum++； m=Ｓuｍleaf（T－>lchｉld)； suｍ+=m； n=Sumleaf(T—＞rｃhｉｌd); suｍ+＝ｎ； ｝ retuｒn ｓum； } 二叉树层次遍历算法实现 问题描述 对任意输入的表示某二叉树的字符序列，完成二叉树的层次遍历算法，并输出其遍历结果。 注：所需Queue ADT的实现见附录。 输入描述 从键盘上输入一串字符串，该字符串为二叉树的先序遍历结果，其中如果遍历到空树时用字符”#”代替。 输出描述 从显示器上输出二叉树的按层次遍历结果。 输入与输出示例 输入： +A##/*B##C##D## 输出： +A/*DBC 输入： ABD##GJ###CFH##I### 输出： ABCDGFJHI 附录(仅供参考)： #include //注：需要定义ElementType类型，如果是二叉树， // 则应定义为指向二叉树中结点的指针类型 //格式如: // typedef Tree ElementType; // 队列存储结构采用循环队列 struct QueueRecord; typedef struct QueueRecord *Queue; int IsEmpty(Queue Q); int IsFull(Queue Q); Queue CreateQueue(int MaxElements); void DisposeQueue(Queue Q); void MakeEmpty(Queue Q); int Enqueue(ElementType X, Queue Q); ElementType Front(Queue Q); int Dequeue(Queue Q, ElementType &X); #define MinQueueSize ( 5 ) struct QueueRecord { int Capacity; int Front; int Rear; ElementType *Array; }; int IsEmpty(Queue Q) { return ((Q->Rear + 1)% Q->Capacity == Q->Front); } int IsFull(Queue Q) { return ((Q->Rear + 2) % Q->Capacity == Q->Front); } Queue CreateQueue(int MaxElements) { Queue Q; if (MaxElements < MinQueueSize) return NULL; Q = (Queue)malloc(sizeof(struct QueueRecord)); #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); //*************************************************** 二叉树遍历算法的实现 题目：编制二叉树遍历算法的实现的程序 一．需求分析 1.本演示程序中，二叉树的数据元素定义为非负的整型（unsigned int）数据，输 入-1表示该处没有节点 2.本演示程序输入二叉树数据均是按先序顺序依次输入 3.演示程序以用户和计算机对话方式执行，即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运 算结果显示在其后 4.本实验一共包括三个主要程序，分别是：1）二叉树前序，中序，后序遍历递归 算法实现2）二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现 5.本程序执行命令包括：1）构建二叉树2）二叉树前序递归遍历3）二叉树中序 递归遍历4）二叉树后序递归遍历5）二叉树前序非递归遍历6）二叉树中序非 递归遍历7）二叉树层次遍历 6.测试数据 （1）7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1 （2）1 -1 -1 （3）7 8 -1 -1 9 -1 -1 二．概要设计 1.为实现二叉树的遍历算法，我们首先给出如下抽象数据类型 1）二叉树的抽象数据类型 ADT BiTree{ 数据对象D:D是具有相同特性的数据元素的集合 数据关系R： 若D=Φ，则R=Φ，称BiTree是空二叉树； 若D≠Φ，则R={H}，H是如下二元关系： (1)在D中存在唯一的成为根的数据元素root，它在关系H下无前驱； (2)若D-{H}≠Φ，则存在D-{root}={D1,D r}，且D1∩D r=Φ (3)若D1≠Φ，则D1中存在唯一的元素x1， 掌握二叉树的二叉链表存储结构；掌握二叉树的遍历规则；利用二叉树的二叉链表存储结构实现二叉树的建树操作；利用二叉树的二叉链表存储结构实现二叉树层次遍历操作 二叉树采用二叉链表结构表示。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树----队列形式 #include int EmptyQueue(Queue *Q) { if(Q->front==Q->rear) return 1; else return 0; } void EnQueue(Queue *Q,BitNode *e) { Q->base[Q->rear].data=e; Q->rear++; } BiTree DeQueue(Queue *Q) { int m; m=Q->front; Q->front++; return (Q->base[m].data); } char a[50]; BiTree CreatBiTree(BiTree T) { BiTree p; BiTree s[STACK_MAX_SIZE]; int top = -1; int flag; int i = 0; T=NULL; while(a[i]!='#') { switch(a[i]) {case' ':break; case '(': top++; 数据结构课程设计--按层次遍历二叉树学号： 题目按层次遍历二叉树学院计算机科学与技术专业计算机科学与技术 班级 姓名 指导教师 2013年6月20日 1 1问题描述及要求 (4) 1.1问题描述 (4) 1.2任务要求.................................. 4 2 开发平台及所使用软件.............................. 4 3 程序设计思路.. (5) 3.1二叉树存储结构设计 (5) 3.2题目算法设 计 (5) 3.2.1 建立二叉树 (5) 3.2.2 遍历二叉树 (5) 3.3.3 按要求格式输出已建立的二叉 树 (6) 3.3 测试程序................................ 6 4 调试 报告.................................... 6 5 经验和体会.................................. 6 6 源程序清单及运行结果 (7) 6.1 源程序清单 (7) 6.2 运行结果................................ 9 7 参考文献................................... 10 本科生课程设计成绩评定表 (11) 2 课程设计任务书 学生姓名：专业班级：计科ZY1102班指导教师：工作单位：计算机科学系题目: 按层次遍历二叉树 初始条件: 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （1）二叉树采用二叉链表作为存储结构。 ⑵按严蔚敏《数据结构习题集（C语言版）》p44面题6.69所指定的格式输出建立的二叉树。 （3）输出层次遍历结果。 （4）自行设计测试用例。 要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1.问题描述 简述题目要解决的问题是什么。 2. 设计 存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计; 3. 调试报告 调试过程中遇到的问题是如何解决的; 对设计和编码的讨论和分析。 4. 经验和体会（包括对算法改进的设想） 5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结 果要包含这些测试数据和运行输出。 说明： 1. 设计报告、程序不得相互抄袭和拷贝; 若有雷同，则所有雷同者成绩均为0 分。 2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0 分记。时间安排： 1（第17周完成，验收时间由指导教师指定 课程设计 题目按层次遍历二叉树 学院计算机科学与技术 专业计算机科学与技术 班级0801 姓名陈新 指导教师孙玉芬 2012 年 6 月20 日 课程设计任务书 学生姓名：专业班级： 指导教师：孙玉芬工作单位：计算机科学系 题目: 按层次遍历二叉树 初始条件： 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （1）二叉树采用二叉链表作为存储结构。 （2）按题集p44面题6.69所指定的格式输出建立的二叉树。 （3）输出层次遍历结果。 （4）测试用例自己设计。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、问题描述 简述题目要解决的问题是什么。 2、设计 存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计； 3、调试报告 调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4、经验和体会（包括对算法改进的设想） 5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出， 6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。 时间安排： 1、第19周完成。 2、6月21日8：00到计算中心检查程序、交课程设计报告、源程序。 指导教师签名： 系主任（或责任教师）签名：年月日 数据结构课程设计 ——按层次遍历二叉树 1问题描述及要求 1.1问题描述 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 1.2任务要求 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （1）二叉树采用二叉链表作为存储结构。 （2）按题集p44面题6.69所指定的格式输出建立的二叉树。 （3）输出层次遍历结果。 （4）测试用例自己设计。 2开发平台及所使用软件 Windows 7.0 , Visual C++6.0 3程序设计思路 3.1二叉树存储结构设计 typedef char ElemType; //二叉树结点值的类型为字符型 typedef struct BiTNode{ //二叉树的二叉链表存储表示 ElemType date; struct BiTNode *lchild,*rchild; //左右孩子指针 } BiTNode，*BiTree; 3.2题目算法设计 3.2.1建立二叉树 void CreateBinTree(BinTree &T){ //按先序次序输入，构造二叉链表表示的二叉树T char ch; ch=getchar(); //输入函数。 if(ch==’’) T=NULL; //输入空格时为空 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("%c" "结点建立失败!") ; T->data=ch; CreateBinTree(T->lchild); CreateBinTree(T->rchild); 二叉树三种遍历算法的源码 二叉树三种遍历算法的源码背诵版 本文给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。 1.先序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void PreOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec 2.中序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void InOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历}//endif }//endwhile }//InOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]; int top; }SqStack; void PostOrderUnrec(Bitree t) 数据结构实验四树与二叉树 班级学号姓名分数 一、实验目的： 1、掌握二叉树的定义、性质及存储方式，各种遍历算法。 2、掌握这种存储结构的构造算法以及基于每一种结构上的算法设计 3、初步掌握算法分析方法并对已设计出的算法进行分析，给出相应的结果。 二、实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。 三、实验内容及分析： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。 四、程序的调试及运行结果 先序遍历 中序遍历 后序遍历 树的深度及叶子树 层次遍历 五、程序代码 #include"stdio.h" #include"stdlib.h" #include"string.h" #define Max 20 //结点的最大个数 typedef struct node{ char data; struct node *lchild,*rchild; }BinTNode; //自定义二叉树的结点类型 typedef BinTNode *BinTree; //定义二叉树的指针 int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数 //==========基于先序遍历算法创建二叉树============== //=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置========== BinTree CreatBinTree(void) { BinTree T; char ch; if((ch=getchar())=='#') return(NULL); //读入#，返回空指针 else{ T= (BinTNode *)malloc(sizeof(BinTNode)); //生成结点 T->data=ch; T->lchild=CreatBinTree(); //构造左子树 T->rchild=CreatBinTree(); //构造右子树 return(T); } } //========NLR 先序遍历============= void Preorder(BinTree T) { if(T) { printf("%c",T->data); //访问结点 Preorder(T->lchild); //先序遍历左子树 Preorder(T->rchild); //先序遍历右子树 } } //========LNR 中序遍历=============== void Inorder(BinTree T) { if(T) { Inorder(T->lchild); //中序遍历左子树 printf("%c",T->data); //访问结点 Inorder(T->rchild); //中序遍历右子树 } } //==========LRN 后序遍历============ void Postorder(BinTree T) { if(T) { Postorder(T->lchild); //后序遍历左子树 目录 一．选题背景 (1) 二．问题描述 (1) 三．概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四．详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五．测试数据与分析 (6) 六．源代码 (6) 总结 (10) 参考文献: (11) 一．选题背景 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为 由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。 然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。 二．问题描述 对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。 三．概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图 图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图 图3.3二叉树中序遍历示意图 #include printf("%c",T->data); } void PreOrder(BiTree T)//先序遍历 { if(T) { visit(T); PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T)//中序遍历 { if(T) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } void PostOrder(BiTree T)//后序遍历 { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } } void InitQueue(LinkQueue *Q){ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if((*Q).front) (*Q).front->next=NULL; } int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear)return 0; return 1; } ○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用 二. 实验要求（题目） 说明：以下题目中（一）为全体必做，（二）（三）任选其一完成 （一）从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二）分别用递归和非递归算法实现二叉树的三种遍历； （三）模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。 四. 概要设计 实现算法，需要链表的抽象数据类型： ADT Binarytree { 数据对象：D是具有相同特性的数据元素的集合 数据关系R： 若D为空集，则R为空集，称binarytree为空二叉树； 若D不为空集，则R为{H}，H是如下二元关系； （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D－{root}不为空，则存在D－{root}＝{D1，Dr}，且D1∩Dr为空集； （3）若D1不为空，则D1中存在唯一的元素x1， 问题一：二叉树遍历 1.问题描述 设输入该二叉树的前序序列为： ABC##DE#G##F##HI##J#K##（#代表空子树） 请编程完成下列任务： ⑴请根据此输入来建立该二叉树，并输出该二叉树的前序、中序和后序序列； ⑵按层次遍历的方法来输出该二叉树按层次遍历的序列； ⑶求该二叉树的高度。 2.设计描述 （1）二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。采用递归方式就可以容易的实现二叉树的遍历，算法简单且直观。 （2）此外，二叉树的层次遍历即按照二叉树的层次结构进行遍历，按照从上到下，同一层从左到右的次序访问各节点。遍历算法可以利用队列来实现，开始时将整个树的根节点入队，然后每从队列中删除一个节点并输出该节点的值时，都将它的非空的左右子树入队，当队列结束时算法结束。 （3）计算二叉树高度也是利用递归来实现：若一颗二叉树为空，则它的深度为0，否则深度等于左右子树的最大深度加一。 3．源程序 1 2 3 4 5 6 7 8#include <> #include <> #include <> #define ElemType char struct BTreeNode { ElemType data; struct BTreeNode* left; struct BTreeNode* right; 青岛理工大学数据结构课程实验报告 void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(T){ Visit(T->data);//首先访问根结点 PreOrderTraverse(T->lchild,Visit);//然后递归遍历左子树 PreOrderTraverse(T->rchild,Visit);//最后递归遍历右子树}} //中序遍历时先递归遍历左子树，然后访问根结点，最后递归遍历右子树；后序遍历时先递归遍历左子树，然后递归遍历右子树，最后 访问根结点 3、//先把栈及队列相关操作的头文件包括进来 1）根指针入栈， 2）向左走到左尽头（入栈操作） 3）出栈，访问结点 4）向右走一步，入栈，循环到第二步，直到栈空 //层次遍历时，若树不空，则首先访问根结点，然后，依照其双亲结 点访问的顺序，依次访问它们的左、右孩子结点; 4.首先建立二叉线索存储：包含数据域，左右孩子指针以及左右标志 typedef enum { Link=0,Thread=1 } PointerTag; typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild;//左右孩子指针 PointerTag LTag,RTag;//左右标志 }BiThrNode, *BiThrTree; 建立前驱线索和后继线索，并用中序遍历进行中序线索化，然后最 后一个结点线索化 调 试 过 程 及 实 验 结 果 把测试数据放在f:\\file\\data.txt里，测试数据为：1 2 4 0 0 0 3 5 0 0 0 总访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型创建一个二叉树并输出三种遍历结果
二叉排序树的建立及遍历的实现
第6章树和二叉树习题
数据结构C语言实现二叉树三种遍历
二叉树的层次遍历算法
二叉树的建立及几种简单的遍历方法
二叉树遍历算法的实现
输入某棵二叉树的广义表形式,建立该二叉树并按层次遍历该二叉树队列形式
数据结构课程设计--按层次遍历二叉树
层次遍历二叉树
二叉树三种遍历算法代码_
数据结构实验四 树与二叉树
二叉树遍历课程设计心得【模版】
队列实现二叉树遍历
用递归和非递归算法实现二叉树的三种遍历
数据结构二叉树遍历实验报告
二叉树的遍历及线索化
相关主题
文本预览