簡介
二叉鍊表樹的二叉鍊表實現方式
（孩子兄弟表示法）
以二叉鍊表作為樹的存儲結構。鍊表中結點的兩個鏈域分別指向該結點的第一個孩子結點和第二個孩子結點。
結構描述
typedef struct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；
由於二叉樹的存儲結構比較簡單，處理起來也比較方便，所以有時需要把複雜的樹，轉換為簡單的二叉樹後再作處理。
二叉鍊表的功能定義
bitree.h
//二叉鍊表定義
#include <iostream>
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<r){
p=q[f++]; //出隊
visit(p->data);
if(p->lchild!=NULL)
q[r++]=p->lchild; //入隊
if(p->rchild!=NULL)
q[r++]=p->rchild; //入隊
}
}
