686
王者榮耀
創建二叉樹並遍曆二叉樹
剛剛接觸二叉樹的同學一很想學習如何構建一顆簡單的二叉樹，下麵我用C語言來實現一個簡單的二叉樹，並且用先序、中序和後序的方法來遍曆它。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
typedef struct node
//定義二叉樹的節點
/*
可能有人不知道typedef是幹什麼用的
寫了typedef後在定義結構體時就不用寫struct node a；
直接寫node a；就行了，比較方便
*/
{
int data;
struct node *ltree,*rtree;
}node;
node *cNode(int n)
{
node *p;
p=(node*)malloc(sizeof(node));//申請內存空間
p->data=n;
p->ltree=p->rtree=0;//左孩子與右孩子都為空
return p;// 返回所創建節點（結構體）的指針
}
void mtree(node *par,node *lc,node *rc)//par父節點，lc左孩子，rc右孩子
{
par->ltree=lc;
par->rtree=rc;
}
void ztr(node *t)//中序遍曆
{
/*
因為遍曆左子樹的方式與遍曆左子樹的左子樹方式類似，所以可以用遞歸很方便的寫出來
代碼很少，想著也簡單，但計算機執行的過程是很複雜的
*/
if (t!=0)
{
ztr(t->ltree);//遍曆左子樹
printf("%d",t->data);//輸出根節點
ztr(t->rtree);//遍曆右子樹
}
}
void xtr(node *t)//先序遍曆
{
if (t!=0)
{
printf("%d",t->data); //輸出根節點
xtr(t->ltree);//遍曆左子樹
xtr(t->rtree);//遍曆右子樹
}
}
void htr(node *t)//後序遍曆
{
if (t!=0)
{
htr(t->ltree);//遍曆左子樹
htr(t->rtree);//遍曆右子樹
printf("%d",t->data);//輸出根節點
}
}
int main()
{
int i,j,n;
node *a,*b,*c,*d,*e,*f,*g;
a=cNode(1);//創建一個節點，值為1；
b=cNode(2);
c=cNode(3);
d=cNode(4);
e=cNode(5);
f=cNode(6);
g=cNode(7);
mtree(e,0,g); //e的做孩子為空，右孩子為g
mtree(d,e,f);//將e和f分別作為d的左右孩子
mtree(b,c,d);
mtree(a,b,0);
/*
二叉樹的樣子應該是下麵的樣子（不知道能不能正常顯示）：
a=1
/
b=2
/ \
c=3 d=4
/ \
e=5 f=6
\
g=7
*/
printf("中序遍曆:");
ztr(a);puts("");//中序遍曆，再輸出一個回車 ，puts("");是換行
//////////////////////////////////////////
printf("先序遍曆:");
xtr(a);puts("");
//////////////////////////////////////////
printf("後序遍曆:");
htr(a);puts("");
system("pause");
return 0;
}
最後更新：2017-04-03 12:54:45