二叉鏈表

樹的二叉鏈表實現方式（孩子兄弟表示法）以二叉鏈表作為樹的存儲結構。鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和第二個孩子結點。

typedef　struct CSNode{

ElemType data；

struct CSNode *firstchild ， *netsibling；

} CSNode，* CSTree；

由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把複雜的樹，轉換為簡單的二叉樹后再作處理。

bitree.h

//二叉鏈表定義

#include

using namespace std;

typedef char TElemType;

struct BiTNode{

TElemType data;

BiTNode *lchild,*rchild;

};

typedef BiTNode *BiTree;

void initBiTree(BiTree &T);

void createBiTree(BiTree &T);

void preOrderTraverse(BiTree T,void (*visit)(TElemType)); //遞歸前序遍歷

void preOrderTraverse1(BiTree T,void (*visit)(TElemType)); //非遞歸前序遍歷

void inOrderTraverse(BiTree T,void (*visit)(TElemType)); //遞歸中序遍歷

void postOrderTraverse(BiTree T,void (*visit)(TElemType)); //遞歸後序遍歷

void levelOrderTraverse(BiTree T,void (*visit)(TElemType)); //層序遍歷

bitree.cpp

#include "bitree.h"

void initBiTree(BiTree &T){ //構造空二叉樹T

T=NULL;

}

void createBiTree(BiTree &T){

//按先序次序輸入二叉樹中結點的值（'#'表示空格），構造二叉鏈表表示的二叉樹T。

TElemType ch;

cin>>ch;

if(ch=='#') // 空

T=NULL;

else{

T=new BiTNode;

if(!T)

exit(1);

T->data=ch; // 生成根結點

createBiTree(T->lchild); // 構造左子樹

createBiTree(T->rchild); // 構造右子樹

}

}

void preOrderTraverse(BiTree T,void (*visit)(TElemType)){

// 先序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次

if(T){ // T不空

visit(T->data); // 先訪問根結點

preOrderTraverse(T->lchild,visit); // 再先序遍歷左子樹

preOrderTraverse(T->rchild,visit); // 最後先序遍歷右子樹

}

}

void preOrderTraverse1(BiTree T,void (*visit)(TElemType)){

//前序遍歷二叉樹T的非遞歸演演算法(利用棧)，對每個數據元素調用函數Visit

BiTree s[100];

int top=0; //top為棧頂指針

while((T!=NULL)||(top>0)){

while(T!=NULL){

visit(T->data);

s[top++]=T;

T=T->lchild;

}

T=s[--top];

T=T->rchild;

}

}

void inOrderTraverse(BiTree T,void (*visit)(TElemType)){

//中序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次

if(T){

inOrderTraverse(T->lchild,visit); // 先中序遍歷左子樹

visit(T->data); // 再訪問根結點

inOrderTraverse(T->rchild,visit); // 最後中序遍歷右子樹

}

}

void postOrderTraverse(BiTree T,void (*visit)(TElemType)){

//後序遞歸遍歷T,對每個結點調用函數Visit一次且僅一次

if(T){

inOrderTraverse(T->lchild,visit); // 後序遍歷左子樹

inOrderTraverse(T->rchild,visit); // 再後序遍歷右子樹

visit(T->data); // 最後訪問根結點

}

}

void levelOrderTraverse(BiTree T,void (*visit)(TElemType)){

//層序遍歷T(利用隊列),對每個結點調用函數Visit一次且僅一次

BiTree q[100],p;

int f,r; // f,r類似於頭尾指針

q[0]=T;

f=0;

r=1;

while(f

p=q[f++]; //出隊

visit(p->data);

if(p->lchild!=NULL)

q[r++]=p->lchild; //入隊

if(p->rchild!=NULL)

q[r++]=p->rchild; //入隊

}

}