中序遍歷二叉樹c語言

❶ 編程實現以上二叉樹中序遍歷操作，輸出遍歷序列，求寫代碼~~

#include<stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define OVERFLOW 0

typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree;

BiTree CreateBiTree(BiTree T) //先序遍歷構造二叉樹
{
char ch;
scanf("%c",&ch);
if(ch=='#') //#代表空指針
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //申請結點
if(!T)
exit(OVERFLOW);
T->data=ch; //生成根結點
T->lchild=CreateBiTree(T->lchild); //構造左子樹
T->rchild=CreateBiTree(T->rchild); //構造右子樹
}
return T;
}

Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍歷二叉樹
if(T)
{
if(InOrderTraverse(T->lchild,visit))
if(visit(T->data))
if(InOrderTraverse(T->rchild,visit))
return OK;
return ERROR;
}
else
return OK;
}

Status PrintElement(TElemType e)
{
printf("%-2c",e);
return OK;
}

void main()
{
BiTree T=NULL;
printf("請輸入構造二叉樹的字元序列：");
T=CreateBiTree(T);
if(T)
printf("二叉樹建立成功！ ");
else
printf("二叉樹構造失敗！！！ ");
printf("中序遍歷二叉樹：");
InOrderTraverse(T,PrintElement);
printf(" ");
}

❷ c語言 關於二叉樹的創建和遍歷(中序遍歷)

這個還是我學《數據結構》時做的有關二叉樹的練習呢，本來是全的，包括樹的初始化，建立，遍歷（中序、前序、後序和層次），還有輸出，復制，刪除節點，求深度，樹的刪除等等，看你只問了有關創建和中序遍歷的，所以選了一部分給你，供你參考吧！
#include <stdio.h>
#include <malloc.h>
#define MaxSize 10
#define Number 30
struct BiTNode{//定義數據結構
char data;
BiTNode *lchild,*rchild;
};
void InitBtree(BiTNode * &BT){//初始化二叉樹
BT=NULL;
}
void CreateBiTree(BiTNode *&BT,char *str){//建立二叉樹
BiTNode *s[MaxSize];//這里定義了一個數組用作堆棧方便檢查輸入和操作
int top=-1;
BT=NULL;
BiTNode *p=NULL;
int k, j=0;
char ch;
ch=str[j];
while(ch!='\0'){
switch(ch){
case '(':
top++;
s[top]=p;
k=1;
break;
case ')':
top--;
break;
case ',':
k=2;
break;
default:
p=(struct BiTNode *) malloc(sizeof(struct BiTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(BT==NULL)
BT=p;
else{
if(k==1)
s[top]->lchild=p;
else
s[top]->rchild=p;
}
}
j++;
ch=str[j];
}
}
void inorder(BiTNode *BT){//中序遍歷二叉樹——遞歸形式
if(BT!=NULL){
inorder(BT->lchild );
printf("%c ",BT->data);
inorder(BT->rchild );
}
}

void main(){
BiTNode *BT;
printf("以廣義表形式表示輸入的二叉數 （如A(B(C,D),E(,F))的形式）\n\n");
char string[Number]="A(B(,C),D(E(F),G(,H)))";
//如果想要自己輸入，可以將下邊的注釋去掉，然後自己按照廣義表形式輸入，
//（如上例的形式）此處為了方便查看，用了默認的數值
//這里之所以用此種形式（廣義表形式輸入）是為了保證輸入的數組成的二叉樹完全符合你所定義的樹的形狀
/*char string[Number],ch;
int i=0;
ch=getchar();
while(ch!='\n' && i<Number){
string[i]=ch;
i++;
ch=getchar();
}
string[i]='\0';
*/

InitBtree(BT);//初始化二叉樹
CreateBiTree(BT,string);//創建二叉樹
printf("\n中序遍歷二叉樹順序為： ");
inorder(BT);//中序遍歷二叉樹
printf("\n");
}
程序不復雜，所以只是加了必要和最簡單的注釋，相信你看看應該完全可以理解的，祝你進步！

❸ 用遞歸演算法先序中序後序遍歷二叉樹

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

棗蘆 printf(「%d 」, BT->Data); //對節點做些訪問比如列印

PreOrderTraversal(BT->Left); //訪問左兒子

PreOrderTraversal(BT->Right); //訪問右兒子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、後序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(3)中序遍歷二叉樹c語言擴展閱讀：

注意事項

1、前序遍歷

從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。

2、中序遍歷

從整棵凳滑帶二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若讓襲LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。

3、後序遍歷

將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。

❹ 用C語言建立一棵含有n個結點的二叉樹，採用二叉鏈表存儲，然後分別實現前序，中序，後序遍歷該二叉樹

#include <stdio.h>
#include <stdlib.h>
#define max 100

typedef struct node{ //二叉樹結構
char data;
struct node *lc,*rc; //左右子樹
}bt,*list;
/*
二叉樹
A
/ \
B C
/ \ \
D E F
/ / \
K G H

input
ABDK000E00C0FG00H00

ouput
ABDKECFGH
KDBEACGFH
KDEBGHFCA
*/

int creat(list*root){ //創建一棵二叉樹，root使用的是二維指針
char n;
scanf(" %c",&n); //注%C前面加空格是為了起間隔作用 scanf不讀入空格
if (n=='0') //0為間隔
{
*root=NULL; return 0; //輸入結束
}
*root=(list)malloc(sizeof(bt));
if (!*root) return 0;
(*root)->data=n;
creat(&(*root)->lc);
creat(&(*root)->rc);
return 1;
}

int pre(list root){ //先序遍歷
if (!root) return 0;
printf("%c",root->data);
pre(root->lc);
pre(root->rc);
return 1;
}
int mid(list root){ //中序遍歷
if (!root) return 0;
mid(root->lc);
printf("%c",root->data);
mid(root->rc);
return 1;
}

int bh(list root){ //後序遍歷
if (!root) return 0;
bh(root->lc);
bh(root->rc);
printf("%c",root->data);
return 1;
}
int sum(list root,int *cnt){ //求結點的個數sum
if(root){
(*cnt)++;
sum(root->lc,cnt);
sum(root->rc,cnt);
return 1;
}
return 0;
}
int sumleaf(list root,int *cnt){ //求葉子節點的個數
if (root)
{
if ((!root->lc)&&(!root->rc))
{ (*cnt)++; }
sumleaf(root->lc,cnt);
sumleaf(root->rc,cnt);
return 1;
}
return 0;
}
int deep(list root,int *cnt){ //求深度
if (!root)
{
*cnt=0; return 0;
}
int m,n;
n=m=*cnt;
deep(root->lc,&m);
deep(root->rc,&n);
*cnt=m+1;
if(m<n) *cnt=n+1;
return 1;
}
int floor(list root){ //層次遍歷
if(root)
{
list s[max]; int front,rear; //用隊進行存儲
front=-1; rear=0; s[rear]=root; //初始化
while (rear!=front) //當隊為空時結束
{
printf("%c",s[++front]->data);
if (s[rear]->lc)
{s[1+rear]=s[rear]->lc; rear++; } //將左子樹存入隊列中
if (s[rear]->rc)
{s[1+rear]=s[rear]->rc; rear++; } //將右子書存入隊列中
}
return 1;
}
return 0;
}
int scop(list *r,list *p){ //樹的復制
if(*r){
*p=(list)malloc(sizeof(bt));
if(*p){
(*p)->data=(*r)->data;
scop(&(*r)->lc,&(*p)->lc);
scop(&(*r)->rc,&(*p)->rc);
return 1;
}
}
*p=NULL;
return 0;
}
int sepect(list root,list *p,char e){ //查找節點返回指針*p p為二級指針
if(root){
if (root->data==e)
{ *p=root; return 1;
}
sepect(root->lc,p,e);
sepect(root->rc,p,e);
}
return 0;
}
void main(){
list b,s,m;
int n,t=1;
char ch='\0';
printf("***********Bitree************\n");
while(t){ //循環操作
printf("input a tree(int):\n");
s=m=b=NULL; //二叉樹的初始化
creat(&b);
//按三種遍歷輸出二叉樹
printf("\npre "); pre(b);
printf("\nmid "); mid(b);
printf("\nbh "); bh(b); printf("\n");
//求節點數目，葉子節點的個數，深度
n=0; sum(b,&n); printf("sumdata: %d\n",n);
n=0; sumleaf(b,&n); printf("sumleaf: %d\n",n);
n=0; deep(b,&n); printf("deep: %d\n",n);
//二叉樹的復制
scop(&b,&s);
printf("\ns tree:\npre ");
pre(s); printf("\nmid ");
mid(s); printf("\nbh ");
bh(s); printf("\n");
//查找節點
printf("sepect a data:\n");
scanf(" %c",&ch); //注%C前面加空格是為了起間隔作用 scanf不讀入空格
sepect(b,&m,ch);
if(m)
printf("sepect : %c \n",m->data);
else
printf("Error,no this data: %c\n",ch);
//繼續則輸入 1，退出輸入 0
printf("continue input 1,break input 0:\n");
scanf("%d",&t);
}
}