設計不同的結點結構可構成不同形式的鏈式儲存結構。由二叉樹的結點由一個數據元素和分別指向其左、右子樹的兩個分支構成，則表示二叉樹的鏈表中的結點至少包含三個域：數據域和左、右指針域
一下是二叉鏈表的定義和部分基本操作的函數原型說明：
#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 -2
typedef int Status;
typedef char TElemType;
typedef struct BiTNode
{
TElemType data;
BiTNode *lchild, *rchild;
}*BiTree;
//------------基本操作的函數原型說明（部分）------------
Status CreateBiTree(BiTree &T);
//T表示這個樹的根節點的指針
//按先序次序輸入二叉樹中結點的值（一個字符），空格字符表示空樹，
//構造二叉鏈表表示的二叉樹T
Status VisitBiTree(BiTree);
//輸出結點的數據域
Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//先序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。
//一旦visit（）失敗，則操作失敗
Status InOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//中序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。
//一旦visit（）失敗，則操作失敗
Status InOrderTraverse_2(BiTree T, Status(*Visit)(BiTree));
//采用二叉鏈表儲存結構，Visit是對數據元素操作的應用函數。
//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit
Status InOrderTraverse_3(BiTree T, Status(*Visit)(BiTree));
//采用二叉鏈表儲存結構，Visit是對數據元素操作的應用函數。
//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數Visit
Status PostOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//後序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。
//一旦visit（）失敗，則操作失敗
Status LevelOrderTraverse(BiTree T, Status(*Visit)(BiTree));
//T表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//層序遍歷二叉樹T,對每個結點調用函數Visit一次且僅一次。
//一旦visit（）失敗，則操作失敗
Status Destroy(BiTree T);//摧毀T這個節點
Status DestroyBiTree(BiTree &T);
//摧毀二叉樹T
#endif
在二叉樹的一些應用中，常常要求在樹中查找具有某種特征的結點，或者對樹中全部結點逐一進行某種處理。這就提出了一個遍歷二叉樹的問題，即如何按某條搜索路徑尋訪樹中每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。二叉樹的遍歷又有很多情況，其中先序、中序、後序、層序遍歷是常見的情況
上述操作的實現：
#include"stdafx.h"
#include"ADT.h"
#include<deque>
#include<stack>
//------------基本操作的函數原型說明（部分）------------
Status CreateBiTree(BiTree &T)
//T表示這個樹的根節點的指針
//按先序次序輸入二叉樹中結點的值（一個字符），字符為空表示空樹，
//構造二叉鏈表表示的二叉樹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)
//輸出結點的數據域
{
cout << T->data << " ";
return OK;
}
Status Destroy(BiTree T){//摧毀T這個節點
if (T){
free(T);
}
return OK;
}
Status PreOrderTraverse(BiTree T, Status(*Visit)(BiTree))
//T表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//先序遍歷二叉樹T,對每個結點調用函數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表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//中序遍歷二叉樹T,對每個結點調用函數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))
//采用二叉鏈表儲存結構，Visit是對數據元素操作的應用函數。
//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數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))
//采用二叉鏈表儲存結構，Visit是對數據元素操作的應用函數。
//中序遍歷二叉樹T的非遞歸算法，對每個數據元素調用函數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表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//後序遍歷二叉樹T,對每個結點調用函數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表示這個樹的根節點的指針
//采用二叉鏈表儲存結構，Visit是對結點操作的對應函數
//層序遍歷二叉樹T,對每個結點調用函數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;
}
主函數：
// 二叉鏈表.cpp : 定義控制台應用程序的入口點。
//
#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
BiTree T;
cout << "中序輸入二叉樹，如果某個節點的左右子樹為空，則輸入兩個空格：" << 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;
}
結果��（在vs2013中實現，注意要在stadfx.h中包含相應的頭文件）
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
