如何按中序、后序建立一棵二叉树? 10C

图片说明
用空格表示空节点。
如果不空格的话,怎么做?

0

4个回答

0
0

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef struct lNode
{
char data;
struct lNode *lchild;
struct lNode *rchild;
}LNODE,*Tree;

typedef struct Node
{
Tree data;
struct Node * Next;
}NODE, * PNODE;

typedef struct Stack
{
PNODE pBottom;
PNODE pTop;
}STACK, * PSTACK;

//函数声明
PSTACK initStack(void);//创建栈
void push(PSTACK S,Tree val);//压栈
void pop(PSTACK S);//出栈
bool stackEmpty(PSTACK pS);

Tree CreateBiTree();//建树
void pretraverse(Tree T);//先序递归遍历
void Intraverse(Tree T);//中序递归遍历
void posttraverse(Tree T);//后序递归遍历
void NoIntraverse(Tree T);//中序非递归遍历

int main()
{
Tree T;
T=CreateBiTree();

pretraverse(T);printf("\n");

Intraverse(T);
printf("\n");

posttraverse(T);printf("\n");

NoIntraverse(T);printf("\n");

return 0;
}
//建树
Tree CreateBiTree()
{
char ch;
Tree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (Tree)malloc(sizeof(LNODE));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}

//先序递归遍历(遍历顺序:根左右)
void pretraverse(Tree T)
{
if(T!=NULL)
{
printf("%c",T->data);//输出根节点数据
pretraverse(T->lchild);//遍历左子树
pretraverse(T->rchild);//遍历右子树
}
}
//中序递归遍历(遍历顺序:左根右)
void Intraverse(Tree T)
{
if(T!=NULL)
{
Intraverse(T->lchild);//遍历左子树
printf("%c",T->data);//输出根节点数据
Intraverse(T->rchild);//遍历右子树

}
}
//后序递归遍历(遍历顺序:左右根)
void posttraverse(Tree T)
{
if(T!=NULL)
{
posttraverse(T->lchild);//遍历左子树
posttraverse(T->rchild);//遍历右子树
printf("%c",T->data);//输出根节点数据

}
}

//中序遍历(非递归遍历)
void NoIntraverse(Tree T)
{
PSTACK s;
s=initStack();
Tree p=T;
while(p!=NULL||!stackEmpty(s))
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(!stackEmpty(s))
{
pop(s);

p=p->rchild;
}
}
}
PSTACK initStack(void)
{
PSTACK pS;
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
pS->pBottom=pS->pTop;
pS->pBottom->Next=NULL;

}
return pS;
}
void push(PSTACK pS,Tree val)
{
PNODE q;
q=(PNODE)malloc(sizeof(NODE));
if(q==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q->data=val;
q->Next=pS->pTop;
pS->pTop=q;
}

}
void pop(PSTACK pS)
{
PNODE q;
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q=pS->pTop;
printf("%c",q->data);
pS->pTop=q->Next;
free(q);

}

}
bool stackEmpty(PSTACK pS)
{
if(pS->pTop==pS->pBottom)
{
return true;
}
return false;
}

希望对你有帮助,如有疑问一起学习

0

#include"stdio.h"
#include"malloc.h"
#include"stdlib.h"
typedef struct lNode
{
char data;
struct lNode *lchild;
struct lNode *rchild;
}LNODE,*Tree;

typedef struct Node
{
Tree data;
struct Node * Next;
}NODE, * PNODE;

typedef struct Stack
{
PNODE pBottom;
PNODE pTop;
}STACK, * PSTACK;

//函数声明
PSTACK initStack(void);//创建栈
void push(PSTACK S,Tree val);//压栈
void pop(PSTACK S);//出栈
bool stackEmpty(PSTACK pS);

Tree CreateBiTree();//建树
void pretraverse(Tree T);//先序递归遍历
void Intraverse(Tree T);//中序递归遍历
void posttraverse(Tree T);//后序递归遍历
void NoIntraverse(Tree T);//中序非递归遍历

int main()
{
Tree T;
T=CreateBiTree();

pretraverse(T);printf("\n");

Intraverse(T);
printf("\n");

posttraverse(T);printf("\n");

NoIntraverse(T);printf("\n");

return 0;
}
//建树
Tree CreateBiTree()
{
char ch;
Tree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (Tree)malloc(sizeof(LNODE));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}

//先序递归遍历(遍历顺序:根左右)
void pretraverse(Tree T)
{
if(T!=NULL)
{
printf("%c",T->data);//输出根节点数据
pretraverse(T->lchild);//遍历左子树
pretraverse(T->rchild);//遍历右子树
}
}
//中序递归遍历(遍历顺序:左根右)
void Intraverse(Tree T)
{
if(T!=NULL)
{
Intraverse(T->lchild);//遍历左子树
printf("%c",T->data);//输出根节点数据
Intraverse(T->rchild);//遍历右子树

}
}
//后序递归遍历(遍历顺序:左右根)
void posttraverse(Tree T)
{
if(T!=NULL)
{
posttraverse(T->lchild);//遍历左子树
posttraverse(T->rchild);//遍历右子树
printf("%c",T->data);//输出根节点数据

}
}

//中序遍历(非递归遍历)
void NoIntraverse(Tree T)
{
PSTACK s;
s=initStack();
Tree p=T;
while(p!=NULL||!stackEmpty(s))
{
while(p)
{
push(s,p);
p=p->lchild;
}
if(!stackEmpty(s))
{
pop(s);

p=p->rchild;
}
}
}
PSTACK initStack(void)
{
PSTACK pS;
pS->pTop=(PNODE)malloc(sizeof(NODE));
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
pS->pBottom=pS->pTop;
pS->pBottom->Next=NULL;

}
return pS;
}
void push(PSTACK pS,Tree val)
{
PNODE q;
q=(PNODE)malloc(sizeof(NODE));
if(q==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q->data=val;
q->Next=pS->pTop;
pS->pTop=q;
}

}
void pop(PSTACK pS)
{
PNODE q;
if(pS->pTop==NULL)
{
printf("动态内存分配失败!");
exit(-1);
}
else
{
q=pS->pTop;
printf("%c",q->data);
pS->pTop=q->Next;
free(q);

}

}
bool stackEmpty(PSTACK pS)
{
if(pS->pTop==pS->pBottom)
{
return true;
}
return false;
}

希望对你有帮助,如有疑问一起学习

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
二叉树的建立(后序+中序)
106. Construct Binary Tree from Inorder and Postorder Traversal/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeN
中序后序建立二叉树
求二叉树的先序遍历 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description  已知一棵二叉树的中序遍历和后序遍历,求二叉树的先序遍历 Input  输入数据有多组,第一行是一个整数t (t Output  输出二叉树的先序遍历序列 Example
后序中序建立二叉树
#include using namespace std; char post[20],ins[20]; typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Build_tree(int post_begin,int post_end,
如何利用中序和后序构建一棵二叉树
结构体: typedef struct Node{ int value; struct Node *left; struct Node *right; }Node; int Find(char array[], int size, char v){//找的始终是中序 for (int i = 0; i < size; i++){ i...
二叉树前序中序建立和后序中序建立
已知二叉树的前序序列和中序序列,求解树。 1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。 2、求解树的子树。找出根节点在中序遍历中的位置,根左边的所有元素就是左子树,根右边的所有元素就是右子树。若根节点左边或右边为空,则该方向子树为空;若根节点 边和右边都为空,则根节点已经为叶子节点。 3、递归求解树。将左子树和右子树分别看成一棵二叉树,重复1、2、
二叉树的建立&中序&后序&深度
/***************************************** Author :Crazy_AC(JamesQi) Time :2015 File Name : *****************************************/ // #pragma comment(linker, "/STACK:1024000000,10240
通过中序后序建立二叉树
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node { char data; struct node *Lchild; struct node *Rchild; }*BiTree,BiNode;int Mark_Root_Pos(char in[], c
根据后序和中序建立二叉树
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node* tree_pointer; typedef struct node{ tree_pointer left_child; tree_pointer right_child; char data; }tree; int find
中序加后序建立二叉树
L2-006 树的遍历(25 分)#include&amp;lt;stdio.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;#include&amp;lt;iostream&amp;gt;#include&amp;lt;queue&amp;gt;#include&amp;lt;string.h&amp;gt;#include&amp;lt;stdlib.h&amp;gt;using namespace std;typedef struct Node{   ...
由中序和后序确定一棵二叉树
#include #include "queue" using namespace std; class BinaryTreeNode { public: char data; BinaryTreeNode * lc; BinaryTreeNode * rc; BinaryTreeNode(char C){ data = C ;lc = rc = NULL;} }; cla
由前序(后序)和中序确定一棵二叉树
由给定的前序和中序或者给定的中序和后序确定一棵二叉树的算法
前序中序、中序后序二叉树的建立
上了大学刚开始学编程语言,一开始忙头乱脚,什么都不会。之前看到一篇关于求职的文章,提到说写博客,然后应试者与主考官聊到博客,说自己写了很多有关于编程的东西,今天我也要开始写了! /*关于二叉树,怎么去建树,一开始自己想来想去,给你一个前序和中序,或者后序中序,到底该怎么建,一开始自己也非常的糊涂,自己想了大概天,实在是不太明白,结果在网上一查,哦,原来是这样的,采用递归的方法去建树,
已知前序和中序、后序和中序建立二叉树
首先明确先序遍历的顺序为:根结点→左结点→右结点;中序遍历的顺序为:左结点→根结点→右结点;后序遍历的顺序为:左结点→右结点→根结点。 1.        给定先序和中序建立二叉树。 1)        函数原型: void CreateByPreAndIn(BinaryTree &T,charpreorder[],char inorder[],int first,int last) 2)
后序和中序建立二叉树或者先序和中序建立二叉树
代码实现 #include #include #include typedef struct node {   char data;//节点数据元素   struct node *lchild;//指向左孩子   struct node *rchild;//指向右孩子 }BiNode,*BTree; void GetPreOrder(char *last,char *mi
二叉树的 先序+中序=后序,后序+中序=先序
#include using namespace std; typedef int ElemType; struct BTNode{ ElemType data; BTNode * lchild; BTNode * rchild; }; //先序+中序=建树 BTNode * PreInCreate(ElemType pre[],ElemType in[],int len)
前序中序,中序后序建立二叉树及二叉树的深度
#include&amp;lt;bits/stdc++.h&amp;gt; using namespace std; struct tree { char data; tree *l,*r; }; char a[55],b[55];//a前序b中序 int l1,h1,l2,h2; tree *creat() //前序建立 { tree *root; char c; c ...
二叉树的前序中序后序按层遍历
#include #include using namespace std; #include typedef struct BiTNode{ char data ; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void Visit(char data){ cout<<" "<<data ; } void PreOrderTrav
二叉树前序 中序 后序
1. 前序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树。 ABDHECFG 2.中序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树。 HDBEAFCG 3.后序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点。 HDEBFGCA
二叉树 --先序 中序 后序
#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;malloc.h&amp;gt; struct node{//建树 过程中输入这个树 char info; struct node *llink,*rlink; }; typedef struct node NODE; NODE *creat(){ char x; NODE *p; scanf(&quot;%c&quot;,&amp;a...
二叉树(先序中序后序)
二叉树(先序中序后序),代码适合初学者,学习数据结构用
后序中序还原二叉树
根据后序遍历结果和中序遍历结构还原二叉树
二叉树中序,后序非递归遍历
二叉树中序,后序非递归遍历,可以直接运行。
二叉树前序中序后序
int last[maxn], mid[maxn], first[maxn], lc[maxn], rc[maxn], tot, val[maxn]; int newnode() { tot++; lc[tot] = rc[tot] = val[tot] = -1; return tot; } //已知中序 前序 //l1,r1是中序的指针,l2,r2是前序的指针 void build(...
二叉树 前序+中序>>后序
#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;string&amp;gt; //using namespace std; struct Node{     Node *lch;     Node *rch;     char c; }tree[50]; int n;//静态内存中已经分配的节点个数 Node *create(){//申请节点空间并返回其指针     tree[...
二叉树前序,中序,后序
主要是自我的总结 前序遍历:根结点->左子树->右子树 中序遍历:左子树->根结点->右子树 后序遍历:左子树->右子树->根结点 二叉树的定义(为了输出好看,定义char类型): struct binarytree{ char value; binarytree* leftnode; binarytree* rightnode; binarytree(){ valu
中序和后序构建二叉树
题目描述 Given inorder and postorder traversal of a tree, construct the binary tree. 题目解答解题思路 在inorder找到root,然后划分左右 递归构建 代码实现public class ConstructTreeFromInAndPost { public TreeNode buildTree(int[] i
二叉树,前序+中序=>后序
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn = 1000+10; char p[maxn], m[maxn], b[maxn]; int n;struct node { struct node *l, *r; cha
二叉树的建立以及先序中序后序递归遍历
#include #include #define ElemType char typedef struct BiTNode *BiTree; struct BiTNode{ ElemType data; BiTree lchild,rchild; }; BiTree CreateBiTree(){ ElemType ch; BiTree T; scan
已知树的中序+后序/先序遍历,建立二叉树
已知树的中序和后序遍历,建立二叉树(个人感觉理解不了可以直接硬记,慢慢就能理解,知道思想不能理解也无所谓,会用就行) #include #include #include #include using namespace std; int n; int hou[50]; int zhong[50]; typedef struct Btree { int data; str
二叉树的建立与遍历(先序,中序,后序,层次)
#include&amp;lt;stdio.h&amp;gt; #include&amp;lt;stdlib.h&amp;gt; typedef struct BitNode { char data; struct BitNode *lchild,*rchild; }BitNode; BitNode* CreateBiT() //建立二叉树 { char ch;...
二叉树的建立和三种遍历(先序、中序和后序)
这两天清明放假,学习效率很低,二叉树的建立中指针的使用让我颇为不爽,我对指针的理解还是肤浅。待解决的问题:http://bbs.51cto.com/viewthread.php?tid=1103326&amp;extra=page%3D1&amp;frombbs=1 还望高人指点迷津。 二叉树的存储使用二叉链表结构:typedef struct node{ ...
中序和后序生成二叉树
package tree.test; import java.util.LinkedList; import tree.domian.TreeNode; public class Test {     public static void main(String[] args) {         String hx = "KBFDCAE";         Strin
二叉树的建立与先序,后序,中序输出
假设二叉树为:                               a              b                                 c                      d                                 e 因为程序中要知道叶子结点(终点),所以要讲上面的二叉树变成扩展二叉树(把叶子结点的孩子补成#,用作标
二叉树(建立与访问)(先序,中序,后序)
二叉树的建立(先序建立) 二叉树的访问(递归与非递归 先序)(递归与非递归中序)(递归与非递归 后序) #include&amp;lt;iostream&amp;gt; #include&amp;lt;stack&amp;gt; using namespace std; struct Tree_Node ///结点的结构 { char data; ///每个结点的数据 Tree_Node * left; ...
二叉树的建立和遍历(前序、中序、后序)
自己写的,拿来和大家一起分享一下....
递归:二叉树的建立及前序中序后序--JAVA
/** * 实现二叉树的创建、前序遍历、中序遍历和后序遍历 **/ package DataStructure; /** * Copyright 2014 by Ruiqin Sun * All right reserved * created on 2014-9-9 下午2:34:15 **/ public class BinTreeInt { pr...
二叉树的建立与遍历(前序,中序,后序)
二叉树(Binary Tree): 定义:二叉树是n(n>=0)个结点的优先集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。 链式存储结构(二叉链表):由一个数据域(data)和两个指针域构成(lchild,rchild分别指向左右孩子)。如下图: 例如: 二叉链表的结点结构定义代码: typedef stru
二叉树的建立 前序中序后序递归遍历及非递归遍历
#include   #include #include #include #include #include #include using namespace std; struct TreeNode { char val; TreeNode *left; TreeNode *right; }; int i = 1; TreeNode* create(){ Tree
二叉树建立 先序 中序 后序输出
#include<iostream> using namespace std; struct tree { tree *left; tree *right; char on; }; void createtree(tree *w) { char x; cin>>x; if(x=='#') { w=NULL; }
二叉树 中序+后序->还原二叉树
#include #include typedef struct k { int data; struct k *lc,*rc; }Btree; void inputin(int in[],int n) { int i; for(i=0;i<n;i++) scanf("%d",&in[i]); } void inputpost(int post[