1. 用c语言实现前序和中序恢复二叉树
按照你题目要求做的。。。
由于我不知道你的TNode类是怎么定义的，所以我就直接输出结果了
voidInPreToTree(charpreord[],charinord[],intpreleft,intpreright,intinleft,intinright)
{
/*请在BEGIN和END之间实现你的代码*/
/*****BEGIN*****/
introot2n,leftsize,rightsize;
if(preleft<=preright&&inleft<=inright)
{
for(root2n=inleft;root2n<=inright;root2n++)
if(preord[preleft]==inord[root2n])break;
leftsize=root2n-inleft;
rightsize=inright-root2n;
if(leftsize>0)
InPreToTree(preord,inord,preleft+1,preleft+leftsize,inleft,root2n-1);
if(rightsize>0)
InPreToTree(preord,inord,preleft+leftsize+1,preright,root2n+1,inright);
printf("%c",inord[root2n]);
}
/******END******/
/*请不要修改[BEGIN,END]区域外的代码*/
}
望采纳，谢谢
2. 建立二叉树的先序遍历（用递归的方法）c语言源代码
#include<iostream.h>
#include<stdio.h>
struct tree
{
char d;
struct tree *lc,*rc;
};
struct tree* create()
{
struct tree*p;
char c;
cout<<"请输入结点:";
fflush(stdin);
cin>>c;
if(c=='#') return 0;
p=new struct tree;
p->d=c;
p->lc=create();
p->rc=create();
return p;
}
void first(struct tree*q)
{
if(!q) return;
cout<<q->d<<",";
first(q->lc);
first(q->rc);
}
void last(struct tree*q)
{
if(!q) return;
last(q->lc);
last(q->rc);
cout<<q->d<<",";
}
void mid(struct tree*q)
{
if(!q) return;
mid(q->lc);
cout<<q->d<<",";
mid(q->rc);
}
int heigh(struct tree*q)
{
int lh,rh;
if(q==0) return 0;
lh=heigh(q->lc);
rh=heigh(q->rc);
return (lh>rh?lh:rh)+1;
}
void main()
{
struct tree*head;
head=create();
cout<<"树的高为:"<<heigh(head)<<endl;
cout<<"前序排列为:";
first(head);
cout<<endl;
cout<<"中序排列为:";
mid(head);
cout<<endl;
cout<<"后序排列为:";
last(head);
cout<<endl;
}
如果子为空记的输入‘#’代表空呀
哈哈
3. 二叉树c语言实现
#include<iostream.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char data;
struct node *lchild,*rchild;//
}BiTNode,*BiTree;
void CreatBiTree(BiTree &T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode*)malloc(sizeof(BiTNode));
T->data=ch;//生成根节点
CreatBiTree(T->lchild);//构造左子树
CreatBiTree(T->rchild);//构造右子树
}
}
void preorder(BiTree T)//前序遍历
{
if (T!=NULL){
printf ("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
void inorder(BiTree T)//中序遍历
{
if (T!=NULL){
inorder(T->lchild);
printf ("%c",T->data);
inorder(T->rchild);
}
}
void postorder(BiTree T)//后序遍历
{
if (T!=NULL){
postorder(T->lchild);
postorder(T->rchild);
printf ("%c",T->data);
}
}
void main ()
{
cout<<"请输入要创建的二叉树包括空格:"<<endl ;
BiTree T;
CreatBiTree(T);//创建二叉树
cout<<"前序遍历的结果为:"<<endl;
preorder(T);
cout<<endl;
cout<<"中序遍历的结果为:"<<endl;
inorder(T);
cout<<endl;
cout<<"后序遍历的结果为:"<<endl;
postorder(T);
}
4. 二叉树先序非递归遍历C语言算法
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}
5. 关于二叉树的建立与前序遍历问题（c语言）
x=getchar();
getchar();你输入的俩位数第二个字符不是“#”， if (x=='#') break;这个是不会结束的，而且底下的程序有问题，p=(struct node*)malloc(sizeof(struct node));
p->data=x;
p->llink=NULL;
p->rlink=NULL;
if (x<p->data) q->llink=p;
else q->rlink=p;
x都付给了p->data,下面还进行比较干嘛？if (x<p->data)。
6. 二级C栈，二叉树，前序中序后序的概念及例题（二级考试中实用的）
一楼和二楼滴筒子，栈是后进先出（先进后出）的线性表，即LIFO结构，队列才是先进先出的线性表，即FIFO结构。
三楼滴筒子，栈是限制仅在“表尾”进行插入或删除操作的。
栈：
1）栈stack是限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾有特殊的含义，称为栈顶top，表头端称为栈底bottom。不含元素的空表称为空栈。
2）栈的修改按后进先出的原则进行，总是插入或删除“栈顶元素”。
3）栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。
如，另附：
栈的初始化操作：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置。若base的值为NULL，则表示栈结构不存在。top为栈顶指针，当其初值指向栈底，即top=base时可作为栈空的标记。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的“下一个位置”上。
遍历二叉树：
先告诉LZ一个概念，二叉树由根结点、左子树、右子树三个基本单元组成，因此，若能依次遍历这三个部分，便是遍历了整个二叉树。所以，遍历方案要定下执行“遍历左子树”“访问根结点”“遍历右子树”这三个部分的次序。总结所有的方案后，分为以下三种情况：
先序遍历二叉树~~
若二叉树为空，则空操作，否则
1.访问根结点；
2.先序遍历左子树；
3.先序遍历右子树。
中序遍历二叉树~~
若二叉树为空，则空操作，否则
1.中序遍历左子树；
2.访问根结点；
3.中序遍历右子树。
后序遍历二叉树~~
若二叉树为空，则空操作，否则
1.后序遍历左子树；
2.后序遍历右子树；
3.访问根结点。
在数据结构学中规定，限定在执行“遍历左子树”和“遍历右子树”时先左后右，所以，三种情况实质上是因为“访问根结点”的次序不同。因此，三种方法又称作：先根序遍历、中根序遍历、后根序遍历。
7. 二叉树的先序遍历算法------将其用c语言编写程序
void preorder(BiTree T)
{
if(p!=NULL)
{
printf("%c",T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
8. c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}