建立一棵二叉树,要求分别用递归和非递归方法实现二叉树的先序、中序和后序遍历。
#define LEN sizeof(struct tree)
#define NULL 0
#include
#include
struct tree
{
char data;
struct tree *lchild,*rchild;
};
//创建二叉树
struct tree *creat()
{
char c;
struct tree *t;
c=getchar();
if(c==' ')
t=NULL;
else
{
t=(struct tree*)malloc(LEN);
t->data=c;
t->lchild=creat();
t->rchild=creat();
}
return t;
}
//前序遍历
void Preprint(struct tree*t)
{
if(t!=NULL)
{
printf("%c->",t->data);
Preprint(t->lchild);
Preprint(t->rchild);
}
}
//中序遍历
void Inprint(struct tree*t)
{
if(t!=NULL)
{
Inprint(t->lchild);
printf("%c->",t->data);
Inprint(t->rchild);
}
}
//后序遍历
void Postprint(struct tree*t)
{
if(t!=NULL)
{
Postprint(t->lchild);
Postprint(t->rchild);
printf("%c->",t->data);
}
}
main()
{
struct tree *t;
printf("Please input tree in order:
");
t=creat();
printf("The result of Preorder traversal is
");
Preprint(t);
printf("^
The result of Inorder traversal is
");
Inprint(t);
printf("^
The result of Postorder traversal is
");
Postprint(t);
printf("^
");
getch();
}
#include"stdio.h"
#include"string.h"
#include"stdlib.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); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0,即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"(FIFO)队列,按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队,输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("
");
printf("Creat Bin_Tree;Input preorder:"); //输入完全二叉树的先序序列,
// 用#代表虚结点,如ABD###CE##F##
root=CreatBinTree(); //创建二叉树,返回根结点
//do { //从菜单中选择遍历方式,输入序号。
printf("********** select ************
");
printf("1: Preorder Traversal
");
printf("2: Iorder Traversal
");
printf("3: Postorder traversal
");
printf("4: PostTreeDepth,Node number,Leaf number
");
printf("5: Level Depth
"); //按层次遍历之前,先选择4,求出该树的结点数。
printf("0: Exit
");
printf("*******************************
");
do { //从菜单中选择遍历方式,输入序号。
scanf("%d",&i); //输入菜单序号(0-5)
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("
");
} while(i!=0);
}
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
有谁能够告诉我c语言的实验报告怎么写?
实验题目:编程实现:二叉树采用二叉链表存储,要求建立一棵二叉树,并输出要求的树状形式与结点编号。结点结构为:lchiedData numrchied 其中二叉树的num编号域为整数类型,data数据域为字符类型,要求生成二叉树中编号,从1开始进行连续编号,每个结点的编号大于其左右子树中孩子的编号,同一个结点的左右...
二叉树的度是什么意思?
二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2,因为二叉树的定义要求二叉树中任意结点的度数(结点的分支数)小于等于2。通俗的讲二叉树中连接节点和节点的线就是度,有n个节点,就有n-1个度,节点数总是比度要多一个,那么度为0的节点一定是叶子节点,因为该节点的下面不再...
...c语言版二叉树(1) 建立一棵含有n个结点的二叉树,采用二叉链表存储...
;} } void main(){ printf("构建一个二叉树(结点数为n):\\n");root=create(root);printf("前序遍历二叉树:\\n");preorder(root);printf("\\n");printf("中序遍历二叉树:\\n");inorder(root);printf("\\n");printf("后序遍历二叉树:\\n");postorder(root);printf("\\n");} ...
什么是二叉树?
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点;深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。 一棵深度为k,且有2^k-1个节点的二叉树,...
用C++开发一个二叉树类
利用学习数据结构关于二叉树的知识,建立一棵二叉树C++类,基本功能要求:a)包括根据关键字生成、插入节点,删除节点等功能。b)提供遍历功能。c)统计数叶子结点的个数。d)求二叉树的深... 利用学习数据结构关于二叉树的知识,建立一棵二叉树C++类,基本功能要求:a) 包括根据关键字生成、插入节点,删除节点等功能。b) ...
高分求二叉树的建立例题,以及三种遍历
define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE -1 define OVERFLOW -2 typedef int Status;typedef char BiElemType;\/\/ 二叉树的数据结构定义 typedef struct BiNode { BiElemType data;BiNode *lchild,*rchild;}BiNode,*BiTree;\/\/构造一棵二叉树,并且按照前序遍历...
二叉树有几个度?
只有一个根,没有孩子的二叉树度为0,所有节点只有一个孩子的二叉树的度为1,节点中有两个孩子的二叉树的度为2。树所包含的节点中,拥有最大的分支的数目为该树的度。二叉树的度小于等于2,因为二叉树的定义要求二叉树中任意结点的度数(结点的分支数)小于等于2 ,并且两个子树有左右之分,顺序...
给定权1,4,9,16,25,36,49,64,81,100,要求:给出一棵最优二叉树
【答案】:解:1,4,9,16,25,36,49,64,81,100 1+4=5 重新排序 5,9,16,25,36,49,64,81,100 5+9=14重新排序 14,16,25,36,49,64,81,100 14+16=30 重新排序 25,30,36,49,64,81,100 25+30=55重新排序 36,49,55,64,81,100 36+49=85重新排序 55,64,81,85,100 55+64=...
完全二叉树的定义
3、如果2*i+1>n,则结点i肯定没有右孩子;否则右孩子是结点2*i+1。完全二叉树的应用 完全二叉树的好处在于使用完全二叉树,我们可以直击在不修改数组形态的状态下,直接将一个数组映射成一棵树,然后通过这棵树对数组操作,同时很多其他结构的树也都要求这棵树是完全二叉树,如堆就要求堆是一棵...
数据结构,我想创建一颗任意的二叉树,不一定是完全二叉树,不知道应该...
这个是输入结点个数和和树的先序中序构造二叉树 include<stdio.h> include<malloc.h> define NULL 0 typedef struct node { int data;node *left;node *right;}node;node *CreateTree(int *pre,int *in,int n){ if(n==0)return NULL;node *root;root=(node *)malloc(sizeof(node));ro...
进饼必兰: 我们的数据结构实验也是这题,需要我把我的实验报告给你参考下么! 我这里就只发这部分的代码.Status PreOrderTraverse(BiTree T) { //先序遍历二叉树T的递归算法 if (T) { printf("%d ",T->data); if(T->lchild) PreOrderTraverse(T->lchild); if(T->...
安龙县19525475727: 二叉树的遍历c++代码,要求同时使用递归和非递归 - ?
进饼必兰: 递归的:#include <stdlib.h>#include <stdio.h>#define STACK_INIT_SIZE 50 /*MAXSIZE 存储空间初始分配量*/#define STACKINCREMENT 10 #define OK 1#define ERROR 0 #define OVERFLOW 0 typedef int Status; typedef char TElemType; ...
安龙县19525475727: 求一个二叉树的前序,中序,后序的算法.分别用递归和非递归的方法来实现.一共六个算法,求IT届的大神! - ?
进饼必兰: 二叉树的遍历是指按照一定次序访问二叉树中的所有节点,且每个节点仅被访问一次的过程.是最基本的运算,是其他运算的基础. 二叉树有两种存储结构:顺序存储和链式存储 顺序存储: (对完全二叉树来说,可以充分利用存储空间,但对...
安龙县19525475727: 递归方式建立一棵二叉树和非递归方式建立一棵二叉树有什么区别啊? - ?
进饼必兰: 区别在于,递归的算法简单但效率不高,非递归的算法复杂些但效率高.动态输入树节点的值,是要求在程序运行的时候用户才从键盘输入要加入到树中的数据,程序根据用户输入的数据来创建节点插入到树中.跟它相对的是,有些程序在源代码里就已经固定好要加入树中的数据了.
安龙县19525475727: 数据结构试验(用C语言)建立一棵二叉树,并用递归或者非递归的算法分别用先序.中序和后序遍历、谢谢 - ?
进饼必兰: #define LEN sizeof(struct tree)#define NULL 0#include#include struct tree { char data; struct tree *lchild,*rchild; };//创建二叉树 struct tree *creat() { char c; struct tree *t; c=getchar(); if(c==' ') t=NULL; else { t=(struct tree*)malloc(LEN); t->data=c; t->...
安龙县19525475727: 怎样用非递归的方法建立一颗二叉树 - ?
进饼必兰: 先把根节点丢进栈 while (栈不空) { 从栈取1个节点 输入数字 if (输入正确) { new 左右2个节点,左右指针指向2个节点,然后先右后左进栈 } else { 判断其父节点是否存在,以及是父节点的左还是右 把父节点相应指针设置NULL delete 当前节点 } }
安龙县19525475727: 建立二叉树,层序、先序遍历( 用递归或非递归的方法都可以) - ?
进饼必兰: //声明类BiTree及定义结构BiNode,文件名为bitree.h #ifndef BITREE_H #define BITREE_H template <class T> struct BiNode //二叉树的结点结构 { T data; BiNode<T> *lchild, *rchild; }; template <class T> class BiTree { public: BiTree( ); //构造函...
安龙县19525475727: 请问怎么用非递归算法建立一棵二叉树? - ?
进饼必兰: 我是用C++模板写的,希望可以帮助你.构造方法是:输入一串字符;如果直接输入#,则是空树;否则则是AB###;即以前序顺序输入;代码:void Tree<T>::creat_tree(TreeNode<T> * &pointer) { //递归实现对森林的赋值;********************** /*...
安龙县19525475727: 二叉树的非递归遍历 - ?
进饼必兰: 哈,我们数据结构的实验: typedef int Status; typedef int TElemType; typedef struct BiTNode {TElemType data;struct BiTNode *lchild, * rchild;//左右孩子指针 }BiTNode, *BiTree; typedef struct SqQueue {TElemType front ,rear ;BiTree data[...
安龙县19525475727: [问题描述] 建立一棵二叉树,并对其进行递归与非递归遍历(先序、中序、后序),打印输出遍历结果. [ - ?
进饼必兰: 错误相当多,很显然你应该从基础的开始写起,不要一上来就写如此复杂的程序1. choice函数最后少了右括号2. main函数中6条打印语句,\n都不在引号中3. main函数 第5条打印语句前面多了一个符号4 4. nrpostorder 函数中最后的while(top>0); ...