高分求二叉树的建立例题,以及三种遍历
前序遍历:1 2 4 8 9 10 11 5 3 6 7 (规律:根在前;子树在根后且左子树比右子树靠前);
中序遍历:8 4 10 9 11 2 5 1 6 3 7 (规律:根在中;左子树在跟左边,右子树在根右边);
后序遍历:8 10 11 9 4 5 2 6 7 3 1 (规律:根在后;子树在根前且左子树比右子树靠前);
其它例子:
前序遍历:ABDECFG
中序遍历:DBEAFCG
后序遍历:DEBFGCA
前序遍历:1 2 4 3 5 7 6
中序遍历:2 4 1 5 7 3 6
后序遍历:4 2 7 5 6 3 1
做类似的题目,你可以先由两个遍历画出二叉树。通过形象的二叉树来写出另一个遍历,写的方法如上(递归)。画出二叉树的方法如下:
已知一棵二叉树的前序序列和中序序列,构造该二叉树的过程如下:
1. 根据前序序列的第一个元素建立根结点;
2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
3. 在前序序列中确定左右子树的前序序列;
4. 由左子树的前序序列和中序序列建立左子树;
5. 由右子树的前序序列和中序序列建立右子树。
已知一棵二叉树的后序序列和中序序列,构造该二叉树的过程如下:
1. 根据后序序列的最后一个元素建立根结点;
2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
3. 在后序序列中确定左右子树的后序序列;
4. 由左子树的后序序列和中序序列建立左子树;
5. 由右子树的后序序列和中序序列建立右子树。
我上机报告的代码和截图
#include<iostream>
using namespace std;
#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;
//构造一棵二叉树,并且按照前序遍历的方式赋值
Status CreateBiTree(BiTree &T)
{
BiElemType ch;
cin>>ch;
if(ch=='#')T=NULL;
else
{
if(!(T=(BiNode *)malloc(sizeof(BiNode))))exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}
//先序遍历
Status preorder(BiTree T)
{
if(T)
{
if(cout<<T->data<<' ')
if(preorder(T->lchild))
if(preorder(T->rchild))return OK;
return ERROR;
}
else return OK;
}
//中序遍历
Status inorder(BiTree T)
{
if(T)
{
if(inorder(T->lchild))
if(cout<<T->data<<' ')
if(inorder(T->rchild))return OK;
return ERROR;
}
else return OK;
}
//后序遍历
Status postorder(BiTree T)
{
if(T)
{
if(postorder(T->lchild))
if(postorder(T->rchild))
if(cout<<T->data<<' ')return OK;
return ERROR;
}
else return OK;
}
int main()
{
BiTree BiT;
cout<<"以先序顺序输入二叉树的数据,以#表示空节点:"<<endl;
CreateBiTree(BiT);
cout<<"以中序遍历输出:";
inorder(BiT);
cout<<endl;
cout<<"以先序遍历输出:";
preorder(BiT);
cout<<endl;
cout<<"以后序遍历输出:";
postorder(BiT);
cout<<endl;
return 0;
}
/* bu用递归法输出中序和后续*/
#include "stdio.h"
#include "stdlib.h"
#define A 25
typedef struct Btree
{ char data;
struct Btree *lchild,*rchild;
}*tree,t2ree;
t2ree *creat()
{ tree t;
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{ t=(t2ree *)malloc(sizeof(t2ree));
t->data=ch;
t->lchild=creat();/* 开始格式不正确啊 ,就是我用了这个creat(r->rchild),所以对导致
指针乱算*/
t->rchild=creat();
}
return t;
}
/*显示用先序遍历*/
void preorder(tree t)
{ t2ree *s[A] ;
int top=0;
do
{ while(t!=NULL)
{ printf("%c",t->data);
if(t->rchild!=NULL)
s[top++]=t->rchild ; /*是右子树的地址*/
t=t->lchild; /* 再就是这个地方我加了一个{}结果导致了错误*/
}
if(top>=0)
t=s[--top];
}while(top>=0);
}
/* 中序遍历*/
void inorder(tree t)
{
tree s[A],p;
int top=0;
p=t;
do
{ while(p!=NULL)
{ s[top++]=p;
p=p->lchild;
}
if(top>=0)
{ p=s[--top];
printf("%c",p->data);
p=p->rchild;
}
}while(top>=0);
}
/* 后续遍历*/
void postorder(tree t)
{ int top=0,s2[A],b;
tree s1[A],p;
p=t;
do
{
while(p!=NULL)
{s1[top]=p;
s2[top++]=0;
p=p->lchild;
}
if(top>=0)
{ b=s2[--top];
p=s1[top];
if(b==0)
{ s1[top]=p;
s2[top++]=1;
p=p->rchild;
}
else
{ printf("%c",p->data);
p=NULL;
}
}
}while(top>0);
}
/* 求深度*/
int deep(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{ i=deep(t->lchild);
j=deep(t->rchild);
}
return((i>j?i:j)+1);
}
/*求叶子的个数*/
int thief(tree t)
{ int i=0,j=0;
if(!t)
return 0;
else
{i=thief(t->lchild);
j=thief(t->rchild);
}
if(i==0&j==0)
return(1);
else
return(i+j);
}
main()
{ tree s;
s=creat();
printf("\XIAN xu shu chu \n");
preorder(s);
printf("\n kai shi zhong xu :\n");
inorder(s);
printf("\n hou xu :\n");
postorder(s);
printf("\n the shen du is %d\n",deep(s));
printf("\n the ye zi is %d\n",thief(s));
getch();
}
#include<stdio.h>
#include<stdlib.h>
#define ELEMTP int
struct node
{
ELEMTP data;
struct node *lc,*rc;
};
struct node *root;
int m=0;
main()
{
int cord;
struct node* creat();
void preorderz(struct node *t);
void inorder(struct node *t);
void postorder(struct node *t);
void deletes(struct node *t,struct node *p,struct node *f);
do
{
printf("\n 主菜单 \n");
printf(" 1 建立二叉树 \n");
printf(" 2 先序非递归遍历 \n");
printf(" 3 中序递归遍历 \n");
printf(" 4 后序递归遍历,求叶节点数 \n");
printf(" 5 删除节点 \n");
printf(" 6 结束程序运行 \n");
printf("---------------------------------------\n");
printf("请输入您的选择(1, 2, 3, 4, 5, 6)");
scanf("%d",&cord);
switch(cord)
{
case 1:
{
root=creat(); // 建立二叉树
printf("建立二叉树程序以执行完,\n");
printf("请返回主菜单,用遍历算法验证程序的正确性 \n");
}break;
case 2:
{
preorderz(root);
}break;
case 3:
{
inorder(root);
}break;
case 4:
{
postorder(root);
}break;
case 5:
{
//deletes(root)
}
case 6:
{
printf("二叉树程序执行完,再见!\n");
exit(0);
}
}
}while(cord<=6);
}
struct node* creat()
{
struct node *t,*q,*s[30];
int i,j,x;
printf("i,x=");
scanf("%d%d",&i,&x);//i是按满二叉树编号,x节点应有的序号,x是节点的数据
while((i!=0)&&(x!=0))
{
q=(struct node*)malloc(sizeof(struct node));
q->data=x;
q->lc=NULL; q->rc=NULL;
s[i]=q;
if(i==1)
t=q; //t代表树根节点
else
{
j=i/2; //双亲节点的编号
if((i%2)==0)
s[j]->lc=q;
else
s[j]->rc=q;
}
printf("i,x=");
scanf("%d%d",&i,&x);
}
return(t);
}
/*void preorderz(struct node* p)//前序非递归算法
{
struct node *q,*s[30]; //s辅助栈
int top,bools;
q=p;top=0; //栈顶指针
bools=1; //bools=1为真值继续循环;bools=0为假时栈空,结束循环
do
{
while(q!=NULL)
{
printf("%6d",q->data); //访问节点
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
q=q->rc;
}
}while(bools);
printf("\n");
}//////////////////////////结束preorderz*/
void preorderz(struct node* p)//前序递归遍历
{
if(p!=NULL)
{
printf("%6d",p->data);
inorder(p->lc);
inorder(p->rc);
}
}
void inorder(struct node* p)//中序非递归遍历
{
struct node *s[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
printf("%6d",q->data);
q=q->rc;
}
}while(bools);
}
/*void inorder(struct node* p)
{
if(p!=NULL)
{
inorder(p->lc);
printf("%6d",p->data);
inorder(p->rc);
}
}//////////////////////////结束inorder*/
void postorder(struct node* p)
{
struct node *s[30],*s2[30],*q;
int top,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
s2[top]=1;
q=q->lc;
}
if(top==0)
bools=0;
else
{
if(s2[top]==1)
{
s2[top]=2;
q=s[top];
q=q->rc;
}
else
{
q=s[top];
s2[top]=0;
top--;
printf("%6d",q->data);
q=NULL;
}
}
}while(bools);
}
void deletes(struct node *t,struct node *p,struct node *f)
{
struct node *s,*q;
int bools=1;
if(p->lc==NULL)
s=p->rc;
else if(p->rc==NULL)
{
s=p->rc;
while(s->lc!=NULL)
{
q=s;
s=s->rc;
}
if(q==p)
q->rc=s->rc;
else
q->lc=s->rc;
p->data=s->data;
free(s);
bools=0;
}
if(bools==1)
{
if(f==NULL)
t=s;
else if(f->lc==p)
f->lc=s;
else
f->rc=s;
free(p);
}
}
/*void postorder(struct node* p)
{
if(p!=NULL)
{
postorder(p->lc);
postorder(p->rc);
printf("%6d",p->data);
if(p->lc==NULL&&p->rc==NULL)
m++; //统计叶子节点
}
}//////////////////////////结束postorder*/
#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node /*二叉树结点定义*/
{
datatype data;
struct node *lchild,*rchild;
}bintnode;
typedef bintnode *bintree;
void createbintree(bintree *t)
{/*按照前序遍历的顺序建立一棵给定的二叉树*/
char ch;
if ((ch=getchar())==' ')
*t=NULL;
else {
*t=(bintnode *)malloc(sizeof(bintnode));
(*t)->data=ch;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}
void preorder(bintree t)
{/*前序遍历二叉树的递归算法*/
if (t) { printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
main() /*主程序*/
{ bintree root;
printf("\n");
createbintree(&root);
printf("\n");
printf("\n前序遍历结果是: ");
preorder(root);
}
我们学校的, 你参考下,或许对你有用
这是前序的,
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
char data;
struct node *lchild;
struct node *rchild;
}node,*BinTree;
void inorder(node *p,int n)
{
if(p!=NULL)
{
int i;
inorder(p->lchild,n+1);
for(i=0;i<n;i++)
printf("----------");
printf("%c",p->data);
printf("\n");
inorder(p->rchild,n+1);
}
}
void create(BinTree *p)
{
char data;
printf("Please input a word:");
scanf("%s",&data);
if(data=='#')
p=NULL;
else
{
*p=(node *)malloc(sizeof(node));
if(*p==NULL)
{
printf("Ask for free faid!\n");
exit(1);
}
(*p)->data=data;
create(&(*p)->lchild);
create(&(*p)->rchild);
}
}
void main()
{
BinTree root;
create(&root);
inorder(root,0);
}
(pascal语言)二叉树如何建立?(广义表方式输入)
6.二叉树的遍历运算(递归定义)(1)先序遍历 访问根;按先序遍历左子树;按先序遍历右子树 (2)中序遍历 按中序遍历左子树;访问根;按中序遍历右子树 (3)后序遍历 按后序遍历左子树;按后序遍历右子树;访问根 例1.用顺序存储方式建立一棵有31个结点的满二叉树,并对其进行先序遍历。program...
建立一棵二叉树,数据以字符串形式从键盘输入。
代码如下:char a[105];int len,i;\/\/i逐渐增加 void build(int s){ if(i==len) return;\/\/已经建完树了 char c=a[i];\/\/当前的字符 i++;if(!tree[s].l) tree[s].l=c;\/\/如果树的左边是空的,就给左边赋值 else tree[s].r=c;\/\/反之 if(c!=' ') build(c);if(c...
求用c++建立一棵二叉树的程序代码
这里基本上包括二叉树所有操作了,楼主自取所需吧:include<iostream>using namespace std;\/\/ 二叉树结点类struct BinTreeNode{\/\/ 数据成员: double data; \/\/ 数据域 BinTreeNode *leftChild; \/\/ 左孩子指针域 BinTreeNode *rightChild; \/\/ 右孩子指针域 BinTreeNode(){ leftChild = rightChild...
是的,是已知前序遍历和中序遍历,建立二叉树具体应该怎么办呢
ECF是右子树。这样就先建立A,然后开始二分。以左右分别为一种情况,左子树先序是DB,中序是BD,所以B是D的左孩子,然后另一边也是一样,就可以得出C是A的右孩子,然后再以C二分。得出C的左孩子是E,右孩子是F,所以后续遍历就是DBEFCA.无论如何复杂的二叉树都是用这种方法、...
二叉树的建立
define NULL 0 include "stdio.h"include "stdlib.h"\/\/二叉链表结点定义 struct tree { int data;struct tree *lchild;struct tree *rchild;};\/\/ 先序建立二叉树 struct tree *create(struct tree *BT,int k){ struct tree *p;int x;p=(struct tree *)malloc(sizeof(struct tree));printf...
请问C语言如何创建二叉树???
创建二叉树的源程序如下:include <cstdlib> include <stdio.h> typedef struct node { \/\/树的结点 int data;struct node* left;struct node* right;} Node;typedef struct { \/\/树根 Node* root;} Tree;void insert(Tree* tree, int value)\/\/创建树 { Node* node=(Node*)malloc(sizeof(...
数据结构中关于用c++语言建立二叉树的问题,求代码,急!!!
printf("建立二叉树,请输入序列:\\n");CreateBiTree(&T);printf("\\n输出前序序列为:");preOrder(T);printf("\\n输出中序序列为:");inOrder(T);printf("\\n输出后序序列为:");postOrder(T);getch();} (2)include "bitree.h"int leaf(BiTree root)\/\/求二叉树中叶子结点的数目 { in...
二叉树的建立,二叉树的遍历。
typedef struct BiTNode { char data; \/*结点的数据域*\/ struct BiTNode *lchild , *rchild; \/*指向左孩子和右孩子*\/ } BiTNode , *BiTree;\/*创建一棵二叉树*\/ CreatBiTree(BiTree *T){ char c;c = getch();printf("get = %c\\n",c);if(c == ' ')T = NULL;else { T ...
二叉树的建立
\/\/ 中序遍历伪代码:非递归版本,用栈实现,版本2 void InOrder2(TNode* root){ Stack S;if( root != NULL ){ S.push(root);} while ( !S.empty() ){ TNode* node = S.pop();if ( node->bPushed ){ \/\/ 如果标识位为true,则表示其左右子树都已经入栈,那么现在就需要访问该...
已知二叉树的先序序列,怎么建立二叉树并求其叶子结点和深度???~_百度...
二叉树的建立与遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述 已知一个按先序序列输入的字符序列,如abc,,de,g,,f,,,(其中逗号表示空节点)。请建立二叉树并按中序和后序方式遍历二叉树,最后求出叶子节点个数和二叉树深度。 输入 输入一个... 展开 kate...
充邹盐酸: #include typedef struct TP{ int data; struct TP *TLC; struct TP *TRC; }TNode; TNode *MTree()//先序遍历创建二叉树 { TNode *h; int temp; scanf("%d",&temp); if(temp==0) { h=NULL; } else { h=(TNode *)malloc(sizeof(TNode)); h->data=temp; h->...
越西县17110133299: 高分求一个二叉树的创建和遍历?
充邹盐酸: 说明:输入时按前序遍历方式依次输入各节点值,默认的结束符为0.即当一个节点为叶子节点时,把它的左子节点和右子节点都输为0,当然你可以自己修改为加别的值.例如某棵树的形状如下:A/ \B C/ \ \ D E F 则按如下输入:ABD00E...
越西县17110133299: 二叉树的创建和遍历 - ?
充邹盐酸: 我写了一个二叉树 你给看看 一定能行的 我自己用了 #include "stdio.h" #include "malloc.h" #include "string.h" #include "stdlib.h" #define Max 20 //结点的最大个数 typedef struct BinTNode{char data;struct BinTNode *lchild,*rchild; }...
越西县17110133299: 1.编写程序任意输入二叉树的结点个数和结点值,构造一棵二叉树,采用三种递归遍历算法(前序、中序、后序) - ?
充邹盐酸: tree.h#include<stdio.h> #include<malloc.h> #define MAX_NODE 50 typedef struct BiTNode {char data;BiTNode *lchild,*rchild;}BiTNode,*BiTree; BiTree CreateBiTree(); void InorderTraverse( BiTree T);creatTree.cpp #include"tree.h"BiTree...
越西县17110133299: 二叉树的建立,二叉树的遍历. - ?
充邹盐酸: #include "stdio.h"//二叉树的练习 typedef struct BiTNode { char data; /*结点的数据域*/ struct BiTNode *lchild , *rchild; /*指向左孩子和右孩子*/ } BiTNode , *BiTree;/*创建一棵二叉树*/ CreatBiTree(BiTree *T) { char c; c = getch(); printf("get = ...
越西县17110133299: 二叉树的三种遍历序列(先根次序,中根次序,后跟次序,)求结构图 - ?
充邹盐酸: /*先序递归遍历*/ void DLR(BTNode *bt) { if(bt){ printf("%c",bt->data);DLR(bt->lchild);DLR(bt->rchild);} } /*中序递归遍历*/ void LDR(BTNode *bt) { if(bt){ LDR(bt->lchild);printf("%c",bt->data);LDR(bt->rchild);} }/*后序递归遍历*/ void ...
越西县17110133299: 已知二叉树的前序和中序,构造该二叉树的方法是什么 - ?
充邹盐酸: 以下面的例题为例进行讲解: 已知一棵二叉树的先序遍历序列和中序遍历序列分别是ABDCEF、BDAECF,求二叉树及后序遍历序列. 分析:先序遍历序列的第一个字符为根结点.对于中序遍历,根结点在中序遍历序列的中间,左边部分是根...
越西县17110133299: 关于二叉树的建立和输出查找,有例题. - ?
充邹盐酸: // c#include #include typedef struct node { int x; struct node *l, *r; }node; node * newnode(int x) { node *t = (node *)malloc(sizeof(node)); t->x = x; t->l = t->r = NULL; return t; } int main() { int N, x; char dir; node *Tree = NULL, *p, *q; scanf("%d", &N); ...
越西县17110133299: 急求 C语言写的“二叉树的建立和后序遍历的演示” - ?
充邹盐酸: 楼上 你那是C么? #include <stdlib.h> struct tree /* 树的结构宣告 */ { int data; /* 节点数据 */ struct tree *left; /* 指向左子树的指标 */ struct tree *right; /* 指向右子树的指标 */ }; typedef struct tree treenode; /* 树的结构新型态 */ typedef treenode ...
越西县17110133299: 一个简单二叉树的建立与遍历问题?
充邹盐酸: #include <stdlib.h> #include <stdio.h> typedef char ElemType; typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;/*定义二叉链表结点结构*/ void CreateBiTree(BiTree *T) {/* 输入二叉树的先序遍历序列,创建...