A. 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
}
B. C語言 層次遍歷二叉樹
//隊列的操作代碼你自己寫吧？
void
HierarchyBiTree(BiTree
Root){
LinkQueue
*Q;
//
保存當前節點的左右孩子的隊列
InitQueue(Q);
//
初始化隊列
if
(Root
==
NULL)
return
;
//樹為空則返回
BiNode
*p
=
Root;
//
臨時保存樹根Root到指針p中
Visit(p->data);
//
訪問根節點
if
(p->lchild)
EnQueue(Q,
p->lchild);
//
若存在左孩子，左孩子進隊列
if
(p->rchild)
EnQueue(Q,
p->rchild);
//
若存在右孩子，右孩子進隊列
while
(!QueueEmpty(Q))
//
若隊列不空，則層序遍歷
{
DeQueue(Q,
p);
//
出隊列
Visit(p->data);//
訪問當前節點
if
(p->lchild)
EnQueue(Q,
p->lchild);
//
若存在左孩子，左孩子進隊列
if
(p->rchild)
EnQueue(Q,
p->rchild);
//
若存在右孩子，右孩子進隊列
}
DestroyQueue(Q);
//
釋放隊列空間
return
;
}
C. 請幫忙寫一下二叉樹的層序遍歷，用C語言實現
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef struct tnode
{
struct tnode *lchild;
struct tnode *rchild;
char data;
}TNode;
typedef struct node
{
TNode **front;
TNode **rear;
}QNode;
/*
**創建二叉樹
*/
void
init_tree(TNode *&p)
{
char data;
scanf("%c",&data);
if(data!='#'){
p=(TNode *)malloc(sizeof(TNode));
assert(p!=NULL);
p->data=data;
init_tree(p->lchild);
init_tree(p->rchild);
}
else p=NULL;
}
/*
**廣度遍歷二叉樹
*/
void
guang_show(TNode *p)
{
QNode Q;
Q.front=Q.rear=(TNode **)malloc(N*sizeof(TNode *));
assert(Q.rear!=NULL);
*Q.rear++=p;
while(Q.front!=Q.rear){
printf("%c",(*(Q.front))->data);
p=*Q.front++;
if(p->lchild!=NULL)*Q.rear++=p->lchild;
if(p->rchild!=NULL)*Q.rear++=p->rchild;
}
printf("\n");
}
int
main()
{
TNode *p;
init_tree(p);
guang_show(p);
return 0;
}
D. 用c語言實現二叉樹的層次遍歷（用非遞歸方法）
使用隊列，每出一個節點，將該節點的子節點入隊。so easy
E. 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);
}
兄弟你看看 不懂再往下留言 記得給我的勞動成果一點點獎勵哦！！
F. 如何用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;
//結束
}
G. 求一個c語言遍歷二叉樹的演算法
#include <stdio.h>
#include <stdlib.h>
//1 根據二叉樹的性質5，結點按完全二叉樹來編號，則根據結點編號，
// 就可算出其雙親結點的編號，以及該結點是左孩子還是右孩子，
// 這樣一來，就可把該結點的指針賦予雙親結點的相應指針域。
// 怎樣找到雙親結點呢？，在輸入雙親結點的同時要把結點的指針
// 保存起來。也就是說，要設計一個指針數組，來保存每個結點指針。
// 這樣，當輸入下層結點時，才能找到它的雙親。
//2 回想單鏈表的建立過程，單鏈表建立過程中，只需把當前結點，
// 當成前驅結點,故只需設計一個指針變數即可。
typedef char ElementType;
typedef struct node //二叉樹鏈表結點
{
ElementType data;
struct node *lchild,*rchild;//左、右孩子指針
}BinNode,*BinTree; //結點和結點指針的標識符
BinNode * creat(void) //建二叉樹鏈表(返回根結點的指針)
{
int i,j;
ElementType x;
BinNode *q,*s[20];//結點指針、輔助數組(存放結點的指針,該結點有可能是雙親結點)
BinNode *t=NULL; //根結點指針(目前是空樹,生成樹後要返回根結點指針)
printf("\n 請輸入結點編號i和結點值x");
printf("\n 如：1A 2B 3C 4D 5E 7F 00(全為0，輸入結束)");
printf("\n 或：1A 2B 3C 4D 6F 7G 00(全為0，輸入結束)");
printf("\n 或：1A 2B 3C 5E 7G 15M 00(全為0，輸入結束)\n");
scanf("%d%c",&i,&x); //輸入結點編號及結點值
while((i!=0)&&(x!=0))
{
q=(BinNode *)malloc(sizeof(BinNode));//申請結點內存
q->data=x; //保存數據
q->lchild=NULL;
q->rchild=NULL;
s[i]=q; //s[i]存放第i號結點的指針
if(i==1) //1號結點是根結點
t=q; //保存根結點指針,以備返回
else
{
j=i/2; //由該結點號求雙親結點號
if((i%2)==0)
s[j]->lchild=q; //i為偶數是左孩子,該結點指針存入雙親結點的左孩子指針
else
s[j]->rchild=q; //i為奇數是右孩子,該結點指針存入雙親結點的右孩子指針
}
scanf("%d%c",&i,&x);//繼續輸入結點編號和結點值
}
return t; //返回根結點的指針(二叉鏈表的指針)
}
void DisplayBinTree(BinTree T)//用縮進表示二叉樹
{
BinTree stack[100],p; //棧(結點指針數組)、當前結點指針
int level[100]; //棧(每層根結點對應的空格 數 )
int flag[100]; //棧（flag[]=0,1,2分別表示是根結點、左子樹、右子樹 ）
int top,n,i; //棧頂指針，空格個數，循環變數
if(T!=NULL) //若有根結點
{
top=1; //1號結點(根結點 )
stack[top]=T; //入棧(保存根結點指針)
level[top]=1; //顯示空格的個數
flag[top]=0; //根結點
while(top>0) //有根結點
{
p=stack[top]; //取根結點指針
n=level[top]; //取顯示空格的個數
for(i=1;i<=n;i++)//顯示空格(縮進)
printf(" ");
if(flag[top]==0) //若是根結點
printf("T:%c\n",p->data); //顯示根結點
else //不是根結點
{
if(flag[top]==2) //是右子樹根結點
printf("R:%c\n",p->data); //顯示右子樹根結點
if(flag[top]==1) //是左子樹根結點
printf("L:%c\n",p->data,top); //顯示左子樹根結點
}
top--; //顯示一個(出棧一個)結點，top-1
if(p->rchild!=NULL)//若有右孩子
{
top++; //保存一個根結點,top+1
stack[top]=p->rchild;//保存右子樹根結點
level[top]=n+3;
flag[top]=2;
}
if(p->lchild!=NULL)//若有左孩子
{
top++;
stack[top]=p->lchild;//保存左子樹根結點
level[top]=n+3;
flag[top]=1;
}
// printf("level[top]=%d\n",level[top]);
}
}
}
main()
{
BinNode *T; //根結點的指針
T=creat(); //建二叉樹
printf("\n用縮進表示二叉樹的層次(如ppt62所示):\n");
DisplayBinTree(T);
getch();
}
H. 求用C語言實現二叉樹層次遍歷的遞歸演算法，謝謝！！！
演算法思想：層次遍歷目前最普遍用的就是隊列的那種方式，不是遞歸，但是用到while循環，既然題目要求用遞歸，可以用遞歸實現該while循環功能。演算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//測試程序，創建樹輸入例如ABD##E##C##,根左右創建的方式。
如下代碼是測試通過的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}