一下是二叉鏈表的定義和部分基本操作的函數(shù)原型說明：
#ifndef BINARY_LINKED_LIST_TREE_H#define BINARY_LINKED_LIST_TREE_H//---------二叉樹的二叉鏈表儲存表示-----------#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define MYOVERFLOW -2typedef int Status;typedef char TElemType;typedef struct BiTNode{ TElemType data; BiTNode *lchild, *rchild;}*BiTree; //------------基本操作的函數(shù)原型說明（部分）------------Status CreateBiTree(BiTree &T);//T表示這個樹的根節(jié)點的指針//按先序次序輸入二叉樹中結(jié)點的值（一個字符），空格字符表示空樹，//構(gòu)造二叉鏈表表示的二叉樹TStatus VisitBiTree(BiTree);//輸出結(jié)點的數(shù)據(jù)域Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree));//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//先序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree));//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//中序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree));//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)VisitStatus InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree));//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)VisitStatus PostOrderTraverse(BiTree T, Status(*Visit)(BiTree));//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//后序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree));//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//層序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗
Status Destroy(BiTree T);//摧毀T這個節(jié)點
Status DestroyBiTree(BiTree &T);
//摧毀二叉樹T
#endif在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對樹中全部結(jié)點逐一進行某種處理。這就提出了一個遍歷二叉樹的問題，即如何按某條搜索路徑尋訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。二叉樹的遍歷又有很多情況，其中先序、中序、后序、層序遍歷是常見的情況
上述操作的實現(xiàn)：
#include"stdafx.h"#include"ADT.h"#include<deque>#include<stack>//------------基本操作的函數(shù)原型說明（部分）------------Status CreateBiTree(BiTree &T)//T表示這個樹的根節(jié)點的指針//按先序次序輸入二叉樹中結(jié)點的值（一個字符），字符為空表示空樹，//構(gòu)造二叉鏈表表示的二叉樹T{ char ch; ch = getchar(); if (ch == ' '){ T = NULL; return OK; } else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))exit(MYOVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK;}Status VisitBiTree(BiTree T)//輸出結(jié)點的數(shù)據(jù)域{ cout << T->data << " "; return OK;}Status Destroy(BiTree T){//摧毀T這個節(jié)點 if (T){ free(T); } return OK;}Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree))//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//先序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗{ if (T){ BiTree lchild = T->lchild, rchild = T->rchild; if(Visit(T)) if (PreOrderTraverse(lchild,Visit)) if (PreOrderTraverse(rchild, Visit))return OK; return ERROR; } return OK;}Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree))//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//中序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗{ if (T){ BiTree lchild = T->lchild, rchild = T->rchild; if (InOrderTraverse(lchild, Visit)) if (Visit(T)) if (InOrderTraverse(rchild, Visit))return OK; return ERROR; } return OK;}Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree))//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit{ stack<BiTree> sta; sta.push(T); BiTree p; while (!sta.empty()){ while (p = sta.top())sta.push(p->lchild); sta.pop(); if (!sta.empty()){ p = sta.top(); sta.pop(); if (!Visit(p))return ERROR; sta.push(p->rchild); } } return OK;}Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree))//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。//中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit{ stack<BiTree> sta; BiTree p = T; while (p || !sta.empty()){ if (p){ sta.push(p); p = p->lchild; } else{ p = sta.top(); sta.pop(); if (!Visit(p))return ERROR; p = p->rchild; } } return OK;}Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree))//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//后序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗{ if (T){ BiTree lchild = T->lchild, rchild = T->rchild; if (PostOrderTraverse(lchild, Visit)) if (PostOrderTraverse(rchild, Visit)) if (Visit(T))return OK; return ERROR; } return OK;}Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree))//T表示這個樹的根節(jié)點的指針//采用二叉鏈表儲存結(jié)構(gòu)，Visit是對結(jié)點操作的對應(yīng)函數(shù)//層序遍歷二叉樹T,對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一次。//一旦visit（）失敗，則操作失敗{ deque<BiTree> deq; if (T){ deq.push_back(T); while (!deq.empty()){ auto temp = deq.at(0); Visit(temp); if (temp->lchild) deq.push_back(temp->lchild); if (temp->rchild) deq.push_back(temp->rchild); deq.pop_front(); } } cout << endl; return OK;}Status DestroyBiTree(BiTree &T)//摧毀二叉樹T{ if (PreOrderTraverse(T, Destroy))return OK; return FALSE;}
主函數(shù)：
// 二叉鏈表.cpp : 定義控制臺應(yīng)用程序的入口點。//#include "stdafx.h"int _tmain(int argc, _TCHAR* argv[]){ BiTree T; cout << "中序輸入二叉樹，如果某個節(jié)點的左右子樹為空，則輸入兩個空格：" << endl; CreateBiTree(T); cout << "先序遍歷" << endl; PreOrderTraverse(T, VisitBiTree); cout << endl; cout << "中序遍歷"<<endl; InOrderTraverse(T, VisitBiTree); cout << endl; InOrderTraverse_2(T, VisitBiTree); cout << endl; InOrderTraverse_3(T, VisitBiTree); cout << endl; cout << "后序遍歷"<<endl; PostOrderTraverse(T, VisitBiTree); cout << endl; cout << "層序遍歷"<<endl; LevelOrderTraverse(T, VisitBiTree); DestroyBiTree(T); return 0;}
結(jié)果：（在vs2013中實現(xiàn)，注意要在stadfx.h中包含相應(yīng)的頭文件）
