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
}