二叉樹的C語言遍歷

① 急求c語言寫二叉樹的遍歷

下面是一個用
遞歸方法
編的二叉樹遍歷程序，供lz參考。
#include
<stdio.h>//頭文件
#include
<stdlib.h>
#include
<malloc.h>
typedef
struct
bitnode
{
char
data;
struct
bitnode
*lchild,*rchild;
}
bitnode,*bitree;//定義結點類型
bitree
createbitree()//創建樹
{
char
p;bitree
t;
scanf("%c",&p);
if(p=='
')
t=null;
else
{
t=(bitnode
*)malloc(sizeof(bitnode));//為結點開辟空間
t->data=p;
t->lchild=createbitree();
t->rchild=createbitree();
}
return
(t);
}
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()//主函數
{
bitree
ta;
ta=createbitree();
printf("先序遍歷:");
printf("\n");
preorder(ta);
printf("\n");
printf("中序遍歷:");
printf("\n");
inorder(ta);
printf("\n");
printf("後序遍歷:");
printf("\n");
postorder(ta);
}

② 求助：在數據結構中，用C語言如何編寫二叉樹的遍歷

#include "dataStructure.h "

typedef struct CharBiTNode {
char data;
struct CharBiTNode *lchild, *rchild;
} CharBiTNode, *CharBiTree;

typedef struct CharBiTQNode {
CharBiTree data;
struct CharBiTQNode *next;
} CharBiTQNode, *CharBiTQueuePtr;

typedef struct CharBiTQueue {
CharBiTQNode *front;
CharBiTQNode *rear;
} CharBiTQueue;

/**************** Char Queue *********************************/
Status initCharBiTQueue(CharBiTQueue& q) {
q.front = q.rear = (CharBiTQNode*)malloc(sizeof(CharBiTQNode));
if (!q.front)
return ERROR;
q.front-> next = NULL;
}

Boolean charBiTQueueEmpty(CharBiTQueue q) {
if (q.front == q.rear)
return TRUE;
else
return FALSE;
}

Status getCharBiTQueueLength(CharBiTQueue q) {

}

Status getCharBiTQueueHead(CharBiTQueue q, CharBiTree& e) {
e = q.front-> next-> data;
return OK;
}

Status enCharBiTQueue(CharBiTQueue& q, CharBiTree e) {

CharBiTQNode *newNode = (CharBiTQNode*)malloc(sizeof(CharBiTQNode));
if (!newNode)
return ERROR;
newNode-> data = e;
newNode-> next = NULL;
q.rear-> next = newNode;
q.rear = newNode;
return OK;
}

Status deCharBiTQueue(CharBiTQueue& q, CharBiTree& e) {

if (charBiTQueueEmpty(q)) {
return ERROR;
}
CharBiTQNode *p = q.front;
e = p-> next-> data;
q.front = q.front-> next;
free(p);
return OK;
}

Status charBiTQueueTraverse(CharBiTQueue q, Status (*visit)(CharBiTree e)) {

if (charBiTQueueEmpty(q)) {
return ERROR;
}
CharBiTQueuePtr p = q.front;
while(p) {
if (visit(p-> data) == ERROR)
return ERROR;
p = p-> next;
}
return OK;
}

/****************************** Char BiTree ****************************/

int depthLeft = 0;
int depthRight = 0;
int depth = 0;

Status initCharBiTree(CharBiTree& t) {
CharBiTNode *root = NULL;
root = (CharBiTNode*)malloc(sizeof(CharBiTNode));
if (!root)
return ERROR;
else
t = root;
t-> lchild = t-> rchild = NULL;
return OK;
}

Status createCharBiTree(CharBiTree& t) {
char ch;
cin > > ch;
if (ch == '# ')
t = NULL;
else {
if ((t = (CharBiTNode*)malloc(sizeof(CharBiTNode))) == ERROR)
return ERROR;
else {
t-> data = ch;
createCharBiTree(t-> lchild);
createCharBiTree(t-> rchild);
}
}
}

Boolean charBiTreeEmpty(CharBiTree t) {

}

Status charPreOrderTraverse(CharBiTree t, Status(*visit)(char e)) {

if (t != NULL){
if (visit(t-> data) == ERROR)
return ERROR;
if (charPreOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (charPreOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
} else
return OK;
}

Status charInOrderTraverse(CharBiTree t, Status(*visit)(char e)) {

if (t != NULL) {
if (charInOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (visit(t-> data) == ERROR)
return ERROR;
if (charInOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
} else
return OK;
}

Status charPostOrderTraverse(CharBiTree t, Status(*visit)(char e)) {

if (t != NULL) {
if (charPostOrderTraverse(t-> lchild, visit) == ERROR)
return ERROR;
if (charPostOrderTraverse(t-> rchild, visit) == ERROR)
return ERROR;
if (visit(t-> data) == ERROR)
return ERROR;
} else
return OK;
}

Status charLevelOrderTraverse(CharBiTree t, Status(*visit)(char e)) {
CharBiTQueue queue;
initCharBiTQueue(queue);
CharBiTree p;

if (t == NULL)
return ERROR;
else
enCharBiTQueue(queue, t);

while(!charBiTQueueEmpty(queue)) {
deCharBiTQueue(queue, p);
visit(p-> data);
if (p-> lchild != NULL) {
enCharBiTQueue(queue, p-> lchild);
}
if (p-> rchild != NULL) {
enCharBiTQueue(queue, p-> rchild);
}
}
}

int getCharBiTNodes(CharBiTree t, int& n) {

if (t != NULL) {
++n;
getCharBiTNodes(t-> lchild, n);
getCharBiTNodes(t-> rchild, n);
} else
return OK;
}

Status getCharBiTLeafs(CharBiTree t, int& n) {
if (t != NULL) {
if ( t-> lchild == NULL && t-> rchild == NULL)
++n;

getCharBiTLeafs(t-> lchild, n);
getCharBiTLeafs(t-> rchild, n);
} else
return OK;
}

int getCharBiTDepth(CharBiTree t) {

if (t == NULL) {
depth = 0;
} else {
depthLeft = getCharBiTDepth(t-> lchild);
depthRight = getCharBiTDepth(t-> rchild);
depth = 1 + (depthLeft > depthRight ? depthLeft:depthRight);
}
return depth;
}

Status printChar(char e) {
cout < <e;
return OK;
}

/* Test of char BiTree */

int main(char args[]) {

CharBiTree tree;
int numOfNode = 0, leafs = 0, depth = 0;
cout < < "請按先序輸入二叉樹元素 " < <endl;
createCharBiTree(tree);

cout < < "T(pre) = ";
charPreOrderTraverse(tree, printChar);
cout < <endl;

cout < < "T(in) = ";
charInOrderTraverse(tree, printChar);
cout < <endl;

cout < < "T(post) = ";
charPostOrderTraverse(tree, printChar);
cout < <endl;

cout < < "T(level) = ";
charLevelOrderTraverse(tree, printChar);
cout < <endl;

cout < < "The nodes of the tree is ";
getCharBiTNodes(tree, numOfNode);
cout < <numOfNode < <endl;

cout < < "The leafs of the tree is ";
getCharBiTLeafs(tree, leafs);
cout < <leafs < <endl;

cout < < "Tree Depth = ";
cout < <getCharBiTDepth(tree) < <endl;

system( "pause ");
}

③ C語言二叉樹的遍歷。

二叉樹的前中後遍歷（遞歸與非遞歸）
#include<stdio.h>
#include<stdlib.h>

typedef struct NODE
{
char value;
struct NODE *LChild;
struct NODE *RChild;
}BiTNode,*BiTree; //二叉樹數據結構
BiTree root;
typedef struct node
{
BiTNode *pointer;
struct node *link;
}LinkStackNode,*LinkStack; //鏈棧數據結構
LinkStack S;
int count = 0;
//BiTNode * InitTree(BiTree Tree);
BiTNode *CreateTree(BiTree Tree); //創建二叉樹
void PreOrder(BiTree Tree); //遞歸前序遍歷二叉樹
void MidOrder(BiTree Tree); //遞歸中序遍歷二叉樹
void PostOrder(BiTree Tree); //遞歸後序遍歷二叉樹
void NPreOrder(BiTree Tree); //非遞歸前序遍歷二叉樹
void NMidOrder(BiTree Tree); //非遞歸中序遍歷二叉樹
void NPostOrder(BiTree Tree); //非遞歸後序遍歷二叉樹
//---------------------------------------------------
LinkStackNode *InitLinkStack(LinkStack top); //初始化鏈棧
void Push(LinkStack top,BiTNode *p); //進棧操作
BiTNode * Pop(LinkStack top); //出棧操作
//int IsEmpty(LinkStack S); //判斷棧是否為空
void main()
{
//BiTree tree;
//root = InitTree(tree);
root = CreateTree(root);
PreOrder(root);
printf("\n");
MidOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
NPreOrder(root);
printf("\n");
NMidOrder(root);
printf("\n");
NPostOrder(root);
printf("\n");
}

/*BiTNode * InitTree(BiTree Tree)
{
//BiTNode *root;
//root = Tree;
Tree = (BiTNode *)malloc(sizeof(BiTNode));
Tree = NULL;
//Tree->LChild = NULL;
//Tree->RChild = NULL;
return Tree;
}*/

//二叉樹的擴展先序遍歷的創建
BiTNode * CreateTree(BiTree Tree)
{
char ch;
ch = getchar();
if(ch == '.')
Tree = NULL;
else
{
Tree = (BiTNode *)malloc(sizeof(BiTNode));
if(Tree)
{
Tree->value = ch;
Tree->LChild = CreateTree(Tree->LChild);
Tree->RChild = CreateTree(Tree->RChild);
}
}
return Tree;
}

//遞歸前序遍歷二叉樹
void PreOrder(BiTree Tree)
{
if(Tree)
{
printf("%c",Tree->value);
PreOrder(Tree->LChild);
PreOrder(Tree->RChild);
}
}

//遞歸中序遍歷二叉樹
void MidOrder(BiTree Tree)
{
if(Tree)
{
MidOrder(Tree->LChild);
printf("%c",Tree->value);
MidOrder(Tree->RChild);
}
}

//遞歸後序遍歷二叉樹
void PostOrder(BiTree Tree)
{
if(Tree)
{
PostOrder(Tree->LChild);
PostOrder(Tree->RChild);
printf("%c",Tree->value);
}
}

//非遞歸前序遍歷二叉樹
void NPreOrder(BiTree Tree)
{
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
if(p->RChild)
Push(S,p->RChild);
printf("%c",p->value);
p = p->LChild;
}
else
p = Pop(S);
}
}

//非遞歸中序遍歷二叉樹
void NMidOrder(BiTree Tree)
{
//char ch;
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = Pop(S);
printf("%c",p->value);
p = p->RChild;
}
}
}

//非遞歸後序遍歷二叉樹
void NPostOrder(BiTree Tree)
{
BiTNode *p,*q = NULL;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = S->link->pointer;
if(p->RChild == NULL || p->RChild == q)
{
p = Pop(S);
printf("%c",p->value);
q = p;
p = NULL;
}
else
{
//p = Pop(S);
p = p->RChild;
}
}
}
}
//初始化鏈棧
LinkStackNode *InitLinkStack(LinkStack top)
{
top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
return top;
}

//進棧操作
void Push(LinkStack top,BiTNode *p)
{
LinkStackNode *temp;
temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp)
{
temp->pointer = p;
temp->link = top->link;
top->link = temp;
count++;
}
}

//出棧操作
BiTNode * Pop(LinkStack top)
{
//char ch;
BiTNode *p;
LinkStackNode *temp;
p = (BiTNode *)malloc(sizeof(BiTNode));
temp = top->link;
if(temp)
{
top->link = temp->link;
p = temp->pointer;
free(temp);
count--;
}
return p;
}

④ C語言遞歸遍歷二叉樹

voidpreorder(binTreebt){

if(bt!=NULL)//如果到了葉子後（bt=null），就結束函數調用
{
printf("%c",bt->data);//先輸出節點內容
preorder(bt->lchild);//調用函數，去遍歷當前節點的左子樹
preorder(bt->rchild);//上面左樹執行完成後，調用函數，去遍歷當前節點的右子樹
}
}
以上代碼，就是遞歸的特點，和語言無關

⑤ 如何用C語言實現層次遍歷二叉樹

下面是c語言的前序遍歷二叉樹的演算法，在這里假設的節點元素值假設的為字元型，
說明：演算法中用到了結構體，也用到了遞歸的方法，你看看怎麼樣，祝你好運！
#include"stdio.h"
typedef
char
elemtype;
typedef
struct
node
//定義鏈表結構
{
elemtype
data;
//定義節點值
struct
note
*lchild;
//定義左子節點值
struct
note
*rchild;
//定義右節點值
}btree;
preorder(btree
*root)
//前序遍歷
{
if(roof!=null)
//如果不是空節點
{
printf("%c\n",root->data);
//輸出當前節點
preorder(root->lchild);
//遞歸前序遍歷左子節點
preorder(root->rchild);
//遞歸前序遍歷右子節點
}
return;
//結束
}

⑥ 二叉樹遍歷(c語言實現)

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

typedef struct node{
int data;
struct node *lchild,*rchild;
}*treetp,tree;
treetp create (treetp t,int c);
void print1(treetp);
void print2(treetp);
void print3(treetp);
int number=0;
void main()
{
treetp t=0,r;
r=create (t,0);
printf("前序排列 ：");
print1 (r);
printf("\n中序排列 ：");
print2 (r);
printf("\n後序排列 ：");
print3 (r);
}

treetp create(treetp t,int c)
{
treetp p,di;
do{
scanf("%d",&c);
if (t==0)
{
t=(treetp)malloc(sizeof(tree));
t->lchild=t->rchild=0;
t->data=c;
}
else
{ p=t;
while(p!=0)
{
di=p;
if(c<(p->data))
p=p->lchild;
else
p=p->rchild;
}
if(c<(di->data))
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->lchild=NEWdi;
}
else
{
treetp NEWdi=(treetp) malloc(sizeof(tree));
NEWdi->lchild=NEWdi->rchild=0;
NEWdi->data=c;
di->rchild=NEWdi;
}
}
++number;
}while(c!=0);
printf("葉子的數量：%d",number);
return t;
}
void print1(treetp t)
{
if (t!=0)
{
printf("%d ",t->data);
print1(t->lchild);
print1(t->rchild);
}
}
void print2(treetp t)
{
if (t!=0)
{
print2(t->lchild);
printf("%d ",t->data);
print2(t->rchild);
}
}
void print3(treetp t)
{
if (t!=0)
{
print3(t->lchild);
print3(t->rchild);
printf("%d ",t->data);
}
}
希望對你有幫助

⑦ C語言二叉樹的創建和遍歷

我寫了一個二叉樹 你給看看 一定能行的 我自己用了
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //結點的最大個數
typedef struct BinTNode{
char data;
struct BinTNode *lchild,*rchild;
}BinTNode,*BinTree; //自定義二叉樹的結點類型
//定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數

//==========以廣義表顯示二叉樹==============
void DisTree(BinTree T)
{
if(T)
{
printf("%c",T->data);
if((T->lchild)||(T->rchild))
{
if(T->lchild)
{
printf("%c",'(');
DisTree(T->lchild);
}
if(T->rchild)
{
printf("%c",',');
DisTree(T->rchild);
printf("%c",')');
}
}
}
}
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(BinTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))
printf("Error!");
T->data=ch;
T->lchild=CreatBinTree(T->lchild);
T->rchild=CreatBinTree(T->rchild);
}
return T;
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0)
leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree T,root;
int i,depth;
printf("\n");
printf("輸入完全二叉樹的先序序列:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(T); //創建二叉樹，返回根結點
DisTree(root);
printf("\n");
do //從菜單中選擇遍歷方式，輸入序號。
{
printf("\t********** 菜單 ************\n");
printf("\n");
printf("\t1: 先序遍歷\n");
printf("\t2: 中序遍歷\n");
printf("\t3: 後序遍歷\n");
printf("\t4: 該樹的深度,結點數,葉子數\n");
printf("\t5: 層次遍歷\n"); //按層次遍歷之前，先選擇4，求出該樹的結點數。
printf("\t0: 退出\n");
printf("\t*******************************\n");
scanf("%d",&i);
//輸入菜單序號（0-5）
switch(i)
{
case 1: {printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
}break;
case 2: {printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
}break;
case 3: {printf("Print Bin_Tree Postorder: ");
Postorder(root); //後序遍歷
}break;
case 4: {depth=TreeDepth(root); //求樹的深度及葉子數
printf("樹深=%d 樹總結點數=%d",depth,NodeNum);
printf(" 樹葉子數=%d",leaf);
}break;
case 5: {printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
}break;
default: exit(1);
}
}while(i>=0&&i<6);
}

兄弟你看看 不懂再往下留言 記得給我的勞動成果一點點獎勵哦！！

⑧ 怎麼用c語言實現二叉樹的遍歷

這是用廣義表建立二叉樹並先序和中序遍歷二叉樹
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode,*BiTree;

void creategeneralizelist(BiTree *b,char *str)
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,flag,j;
char ch;
for(j=0;(ch=str[j])!='#';j++)
{
switch(ch)
{
case '(':
top++;
St[top]=p;
flag=1;
break;

case ')':
top--;
break;

case ',':
flag=2;
break;

default:
p=(BiTree)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=NULL;
p->rchild=NULL;
if(*b==NULL)
*b=p;
else
{
switch(flag)
{
case 1:
St[top]->lchild=p;
break;

case 2:
St[top]->rchild=p;
break;
}
}
}
}
}

void PreOrder(BiTree T)
{
if(T)
{
printf("%2c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}

void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
printf("%2c",T->data);
InOrder(T->rchild);
}
}

int main(void)
{
BiTree T=NULL;
char str[MaxSize];/*用於保存用戶輸入的字元*/
printf("please input a string end with #:\n");
scanf("%s",str);
creategeneralize_list(&T,str);
printf("the result ofInOrder BiTree is:\n");
/* PreOrder(T);*/
InOrder(T);
getch();
return 1;

}

⑨ C語言 二叉樹遍歷

因為沒有遞歸出口，而一開始while(T)會一直為真，進而一直執行 binlitree(T);，會一直遞歸下去。
//二叉樹的先序遍歷
int PreOrder(TreeNode *root)
{
if(!root)return 0;
printf("%c",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
return 1;
}

⑩ 求二叉樹遍歷演算法C語言實現的

Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構，Visit
是對數據元素操作的應用函數，先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//
若
T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse