二叉樹遍歷演算法實現

『壹』 二叉樹的層次遍歷演算法

二叉樹的層次遍歷演算法有如下三種方法：

給定一棵二叉樹，要求進行分層遍歷，每層的節點值單獨列印一行，下圖給出事例結構：

之後大家就可以自己畫圖了，下面給出程序代碼：

[cpp] view plain

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

最後給出完成代碼的測試用例：124##57##8##3#6##

[cpp] view plain

#include<iostream>

#include<vector>

#include<deque>

using namespace std;

typedef struct tree_node_s {

char data;

struct tree_node_s *lchild;

struct tree_node_s *rchild;

}tree_node_t, *Tree;

void create_tree(Tree *T) {

char c = getchar();

if (c == '#') {

*T = NULL;

} else {

*T = (tree_node_t*)malloc(sizeof(tree_node_t));

(*T)->data = c;

create_tree(&(*T)->lchild);

create_tree(&(*T)->rchild);

}

}

void print_tree(Tree T) {

if (T) {

cout << T->data << " ";

print_tree(T->lchild);

print_tree(T->rchild);

}

}

int print_at_level(Tree T, int level) {

if (!T || level < 0)

return 0;

if (0 == level) {

cout << T->data << " ";

return 1;

}

return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);

}

void print_by_level_1(Tree T) {

int i = 0;

for (i = 0; ; i++) {

if (!print_at_level(T, i))

break;

}

cout << endl;

}

void print_by_level_2(Tree T) {

deque<tree_node_t*> q_first, q_second;

q_first.push_back(T);

while(!q_first.empty()) {

while (!q_first.empty()) {

tree_node_t *temp = q_first.front();

q_first.pop_front();

cout << temp->data << " ";

if (temp->lchild)

q_second.push_back(temp->lchild);

if (temp->rchild)

q_second.push_back(temp->rchild);

}

cout << endl;

q_first.swap(q_second);

}

}

void print_by_level_3(Tree T) {

vector<tree_node_t*> vec;

vec.push_back(T);

int cur = 0;

int end = 1;

while (cur < vec.size()) {

end = vec.size();

while (cur < end) {

cout << vec[cur]->data << " ";

if (vec[cur]->lchild)

vec.push_back(vec[cur]->lchild);

if (vec[cur]->rchild)

vec.push_back(vec[cur]->rchild);

cur++;

}

cout << endl;

}

}

int main(int argc, char *argv[]) {

Tree T = NULL;

create_tree(&T);

print_tree(T);

cout << endl;

print_by_level_3(T);

cin.get();

cin.get();

return 0;

}

『貳』 求二叉樹遍歷演算法C語言實現的

Status
PreOrderTraverse
(
BiTree
T,
Status
(
*Visit
)
(
TElemType
e
)
)
{
//
採用二叉鏈表存儲結構，Visit
是對數據元素操作的應用函數，先序遍歷二叉樹
T
的遞歸演算法。
if
(
T
)
{
//
若
T
不為空
if
(
Visit
(
T->data
)
)
//
調用函數
Visit
if
(
PreOrderTraverse
(
T->lchild,
Visit
)
)
//
遞歸調用左子樹
if
(
PreOrderTraverse
(
T->rchild,
Visit
)
)
return
OK;
//
遞歸調用右子樹
return
ERROR;
}
else
return
OK;
}
//
PreOrderTraverse

『叄』 求用C語言實現二叉樹層次遍歷的遞歸演算法，謝謝！！！

演算法思想：層次遍歷目前最普遍用的就是隊列的那種方式，不是遞歸，但是用到while循環，既然題目要求用遞歸，可以用遞歸實現該while循環功能。演算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}
//測試程序，創建樹輸入例如ABD##E##C##,根左右創建的方式。
如下代碼是測試通過的。
#include "stdlib.h"

#define MAX 100

typedef int Element;

typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;

typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;

Queue Qu;

void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();

void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);

int main()
{
Tree *r=NULL;
CreateTree(&r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}

void Init()
{
int i=0;
for (i=0; i<MAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}

void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)->ch = ch;
CreateTree(&((*r)->left));
CreateTree(&((*r)->right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
PrintTree(r->left);
PrintTree(r->right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r->ch);
if (r->left != NULL)
{
InsertQueue(r->left);
}
if (r->right != NULL)
{
InsertQueue(r->right);
}

Tree *t = DeleteQueue();
TransLevele(t);
}

『肆』 二叉樹的遍歷演算法

遞歸演算法的實現是依據棧來做的，建議你看一下關於這方面的內容。
preorder()函數功能為：若當前結點不為空，則列印當前值，並遞歸調用列印左右結點。
preorder()函數在每次遞歸調用前，先將下一條指令地址和參數壓棧，即在執行preorder(root->Lchild)前，preorder(root->Rchild)地址及參數壓棧。
以後每次遞歸調用均是如此。
遞歸函數返回時，也即root=NULL時，當前preoder(root->Rchild)指令出棧，繼續向下執行，直到整個遞歸完成。
對於上述的樹，執行過程如下：
1、列印1
2、調用列印2，列印3調用壓棧
3、列印2
4、調用列印4，列印5調用壓棧
5、列印4
6、調用列印4的左結點，列印4的右結點調用壓棧
7、4無左結點，即當前結點=NULL，調用返回
8、棧中彈出列印4右結點調用
9、4無右結點，調用返回
10、棧中彈出列印5的調用
.....
一直這樣執行下去，所以列印結果為：1-2-4-5-3-6

『伍』 中序遍歷二叉樹的演算法

中序遍歷的遞歸演算法定義：
若二叉樹非空，則依次執行如下操作：
(1)遍歷左子樹；
(2)訪問根結點；
(3)遍歷右子樹。
中序遍歷的演算法實現
用二叉鏈表做為存儲結構，中序遍歷演算法可描述為：
void
inorder(bintree
t)
{
//演算法里①~⑥是為了說明執行過程加入的標號
①
if(t)
{
//
如果二叉樹非空
②
inorder(t->lchild)；
③
printf("％c"，t->data)；
//
訪問結點
④
inorder(t->rchild);
⑤
}
⑥
}
//
inorder

『陸』 實現二叉樹的各種遍歷方法

#include <stdlib.h>

struct tree /* 樹的結構宣告 */
{
int data; /* 節點數據 */
struct tree *left; /* 指向左子樹的指標 */
struct tree *right; /* 指向右子樹的指標 */
};
typedef struct tree treenode; /* 樹的結構新型態 */
typedef treenode *btree; /* 宣告樹節點指標型態 */

/* ---------------------------------------- */
/* 插入二叉樹的節點 */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

btree newnode; /* 樹根指標 */
btree current; /* 目前樹節點指標 */
btree back; /* 父節點指標 */

/* 建立新節點記憶體 */
newnode = ( btree ) malloc(sizeof(treenode));
newnode->data = value; /* 建立節點內容 */
newnode->left = NULL; /* 設定指標初值 */
newnode->right = NULL; /* 設定指標初值 */
if ( root == NULL ) /* 是否是根節點 */
{
return newnode; /* 傳回新節點位置 */
}
else
{
current = root; /* 保留目前樹指標 */
while ( current != NULL )
{
back = current; /* 保留父節點指標 */
if ( current->data > value ) /* 比較節點值 */
current = current->left; /* 左子樹 */
else
current = current->right; /* 右子樹 */
}
if ( back->data > value ) /* 接起父子的鏈結 */
back->left = newnode; /* 左子樹 */
else
back->right = newnode; /* 右子樹 */
}
return root; /* 傳回樹根指標 */
}

/* ---------------------------------------- */
/* 建立二叉樹 */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
btree root = NULL; /* 樹根指標 */
int i;

for ( i = 0; i < len; i++ ) /* 用迴路建立樹狀結構 */
root = insertnode(root,data[i]);
return root;
}

/* ---------------------------------------- */
/* 二叉樹中序遍歷 */
/* ---------------------------------------- */
void inorder(btree ptr)
{
if ( ptr != NULL ) /* 終止條件 */
{
inorder(ptr->left); /* 左子樹 */
printf("[%2d]\n",ptr->data); /* 列印節點內容 */
inorder(ptr->right); /* 右子樹 */
}
}

/* ---------------------------------------- */
/* 主程式: 建立二叉樹且用中序遍歷列印出來. */
/* ---------------------------------------- */
void main()
{
btree root = NULL; /* 樹根指標 */

/* 二叉樹節點數據 */
int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
root = createbtree(data,9); /* 建立二叉樹 */
printf("樹的節點內容 \n");
inorder(root); /* 中序遍歷二叉樹 */
}

/* ======================================== */
/* 二叉樹的前序遍歷 */
/* ======================================== */
#include <stdlib.h>

struct tree /* 樹的結構宣告 */
{
int data; /* 節點數據 */
struct tree *left; /* 指向左子樹的指標 */
struct tree *right; /* 指向右子樹的指標 */
};
typedef struct tree treenode; /* 樹的結構新型態 */
typedef treenode *btree; /* 宣告樹節點指標型態 */

/* ---------------------------------------- */
/* 插入二叉樹的節點 */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

btree newnode; /* 樹根指標 */
btree current; /* 目前樹節點指標 */
btree back; /* 父節點指標 */

/* 建立新節點記憶體 */
newnode = ( btree ) malloc(sizeof(treenode));
newnode->data = value; /* 建立節點內容 */
newnode->left = NULL; /* 設定指標初值 */
newnode->right = NULL; /* 設定指標初值 */
if ( root == NULL ) /* 是否是根節點 */
{
return newnode; /* 傳回新節點位置 */
}
else
{
current = root; /* 保留目前樹指標 */
while ( current != NULL )
{
back = current; /* 保留父節點指標 */
if ( current->data > value ) /* 比較節點值 */
current = current->left; /* 左子樹 */
else
current = current->right; /* 右子樹 */
}
if ( back->data > value ) /* 接起父子的鏈結 */
back->left = newnode; /* 左子樹 */
else
back->right = newnode; /* 右子樹 */
}
return root; /* 傳回樹根指標 */
}

/* ---------------------------------------- */
/* 建立二叉樹 */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
btree root = NULL; /* 樹根指標 */
int i;

for ( i = 0; i < len; i++ ) /* 用迴路建立樹狀結構 */
root = insertnode(root,data[i]);
return root;
}

/* ---------------------------------------- */
/* 二叉樹前序遍歷 */
/* ---------------------------------------- */
void preorder(btree ptr)
{
if ( ptr != NULL ) /* 終止條件 */
{
printf("[%2d]\n",ptr->data); /* 列印節點內容 */
preorder(ptr->left); /* 左子樹 */
preorder(ptr->right); /* 右子樹 */
}
}

/* ---------------------------------------- */
/* 主程式: 建立二叉樹且用前序遍歷列印出來. */
/* ---------------------------------------- */
void main()
{
btree root = NULL; /* 樹根指標 */

/* 二叉樹節點數據 */
int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
root = createbtree(data,9); /* 建立二叉樹 */
printf("樹的節點內容 \n");
preorder(root); /* 前序遍歷二叉樹 */
}

/* ======================================== */
/* 二叉樹的後序遍歷 */
/* ======================================== */
#include <stdlib.h>

struct tree /* 樹的結構宣告 */
{
int data; /* 節點數據 */
struct tree *left; /* 指向左子樹的指標 */
struct tree *right; /* 指向右子樹的指標 */
};
typedef struct tree treenode; /* 樹的結構新型態 */
typedef treenode *btree; /* 宣告樹節點指標型態 */

/* ---------------------------------------- */
/* 插入二叉樹的節點 */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

btree newnode; /* 樹根指標 */
btree current; /* 目前樹節點指標 */
btree back; /* 父節點指標 */

/* 建立新節點記憶體 */
newnode = ( btree ) malloc(sizeof(treenode));
newnode->data = value; /* 建立節點內容 */
newnode->left = NULL; /* 設定指標初值 */
newnode->right = NULL; /* 設定指標初值 */
if ( root == NULL ) /* 是否是根節點 */
{
return newnode; /* 傳回新節點位置 */
}
else
{
current = root; /* 保留目前樹指標 */
while ( current != NULL )
{
back = current; /* 保留父節點指標 */
if ( current->data > value ) /* 比較節點值 */
current = current->left; /* 左子樹 */
else
current = current->right; /* 右子樹 */
}
if ( back->data > value ) /* 接起父子的鏈結 */
back->left = newnode; /* 左子樹 */
else
back->right = newnode; /* 右子樹 */
}
return root; /* 傳回樹根指標 */
}

/* ---------------------------------------- */
/* 建立二叉樹 */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
btree root = NULL; /* 樹根指標 */
int i;

for ( i = 0; i < len; i++ ) /* 用迴路建立樹狀結構 */
root = insertnode(root,data[i]);
return root;
}

/* ---------------------------------------- */
/* 二叉樹後序遍歷 */
/* ---------------------------------------- */
void postorder(btree ptr)
{
if ( ptr != NULL ) /* 終止條件 */
{
postorder(ptr->left); /* 左子樹 */
postorder(ptr->right); /* 右子樹 */
printf("[%2d]\n",ptr->data); /* 列印節點內容 */
}
}

/* ---------------------------------------- */
/* 主程式: 建立二叉樹且用後序遍歷列印出來. */
/* ---------------------------------------- */
void main()
{
btree root = NULL; /* 樹根指標 */

/* 二叉樹節點數據 */
int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
root = createbtree(data,9); /* 建立二叉樹 */
printf("樹的節點內容 \n");
postorder(root); /* 後序遍歷二叉樹 */
}

『柒』 二叉樹的遍歷演算法

這里有二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。
1.先序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{

Bitree
Elem[maxsize];

int
top;
}SqStack;
void
PreOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
//通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍歷非遞歸演算法
#define
maxsize
100
typedef
struct
{
Bitree
Elem[maxsize];
int
top;
}SqStack;
void
InOrderUnrec(Bitree
t)
{
SqStack
s;
StackInit(s);
p=t;
while
(p!=null
||
!StackEmpty(s))
{
while
(p!=null)
//遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile
if
(!StackEmpty(s))
{
p=pop(s);
visite(p->data);
//訪問根結點
p=p->rchild;
//通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}//InOrderUnrec
3.後序遍歷非遞歸演算法
#define
maxsize
100
typedef
enum{L,R}
tagtype;
typedef
struct
{
Bitree
ptr;
tagtype
tag;
}stacknode;
typedef
struct
{
stacknode
Elem[maxsize];
int
top;
}SqStack;
void
PostOrderUnrec(Bitree
t)
{
SqStack
s;
stacknode
x;
StackInit(s);
p=t;
do
{
while
(p!=null)
//遍歷左子樹
{
x.ptr
=
p;
x.tag
=
L;
//標記為左子樹
push(s,x);
p=p->lchild;
}
while
(!StackEmpty(s)
&&
s.Elem[s.top].tag==R)
{
x
=
pop(s);
p
=
x.ptr;
visite(p->data);
//tag為R，表示右子樹訪問完畢，故訪問根結點
}
if
(!StackEmpty(s))
{
s.Elem[s.top].tag
=R;
//遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while
(!StackEmpty(s));
}//PostOrderUnrec

『捌』 二叉樹的遍歷演算法

void
preorder(BiTree
root)
/*先序遍歷輸出二叉樹結點，root為指向二叉樹根節點的指針*/
{
if（root!=NULL）
{
printf(root->data);
preorder(root->Lchild);
preorder(root->Rchild);
}
}
你看好這個程序,你首先定義了一個preorder函數,然後在函數體中又調用了本函數,這是函數的自調用.執行printf(root->data);語句的時候輸出當前遍歷的數據,preorder(root->Lchild);在執行到4的時候,root->Lchild=NULL,但是執行preorder(root->Rchild);語句,由此轉向下一個結點,即5

『玖』 二叉樹的遍歷操作實現

// S_lbecs.cpp : 定義控制台應用程序的入口點。
//鏈表二叉樹的定義和操作

#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //最大節點個數

typedef struct node{
char data;
struct node *lchild,*rchild; //左邊孩子的指針 和 右邊孩子的指針
}BinTNode;

typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum是結點數 leaf是葉子數

//基於先序遍歷演算法創建二叉樹
//要求輸入先序序列，其中加入虛結點「#」以示空指針的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
scanf("%c",&ch);
if(ch=='#') //讀入# 返回空指針
return(NULL);
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成結點

T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//DLR 先序遍歷
//訪問根節點 先序遍歷左子樹 先序遍歷右子樹
void Preorde(BinTree T){
if(T){
printf("%c",T->data); //訪問結點 D
Preorde(T->lchild); //先序遍歷左子樹 L
Preorde(T->rchild); //先序遍歷右子樹 R
}
}
//LDR 中序遍歷
void Inorder(BinTree T){
if(T){
Inorder(T->lchild); //中序遍歷左子樹 L
printf("%c",T->data); //訪問結點 D
Inorder(T->rchild); //中序遍歷右子樹 R
}
}
//LRD 後序遍歷
void Postorder(BinTree T){
if(T){
Postorder(T->lchild); //後序遍歷左子樹 L
Postorder(T->rchild); //後序遍歷右子樹 R
printf("%c",T->data); //訪問結點 D
}
}
//採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr?hl:hr; //取最大深度
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) //若左右深度都為0 則為葉子
leaf=leaf+1;
return(max+1);
}else{
return(0);
}
}
//利用「先進先出」（FIFO）隊列，按層次遍歷二叉樹
void Levelorder(BinTree T){
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear){
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
BinTree root;
int i,depth; //最大深度
printf("\n創建二叉樹;輸入完全二叉樹先序序列:");
//用#代表虛結點 如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹 返回根結點
printf("\n創建成功!\n");
do{ //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: 先序遍歷\n");
printf("\t2: 中序遍歷\n");
printf("\t3: 後序遍歷\n");
printf("\t4: 求樹的深度及葉子數\n");
printf("\t5: 按層次遍歷\n"); //按層次遍歷之前，先選擇4，求出該樹的結點數。
printf("\t0: 退出\n");
printf("\t*******************************\n請選擇:");
scanf("%d",&i); //輸入菜單選項 0-5
switch(i){
case 1:
//1: 先序遍歷 Preorde
printf("先序遍歷的結果是");
Preorde(root); //
printf("\n");
break;
case 2:
//2: 中序遍歷 Inorder
printf("中序遍歷的結果是");
Inorder(root); //
printf("\n");
break;
case 3:
//3: 後序遍歷 Postorder
printf("後序遍歷的結果是");
Postorder(root); //
printf("\n");
break;
case 4:
//4: 求樹的深度及葉子數 TreeDepth
depth=TreeDepth(root); //
printf("數的深度=%d 結點數=%d",depth,NodeNum);
printf(" 葉子數=%d",leaf);
printf("\n");
break;
case 5:
//5: 按層次遍歷 Preorde
printf("按層次遍歷的結果是");
Levelorder(root); //
printf("\n");
break;
default:
printf("輸入錯誤\n");
break;
}

}while(i!=0);

return 0;
}

是vs做的 有些地方需要改下 是C語言做的

『拾』 怎樣實現二叉樹的前序遍歷的非遞歸演算法

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp]
view
plain

print?
int
(const
BiTree
&T,
int
(*VisitNode)(TElemType
data))
{
if
(T
==
NULL)
{
return
-1;
}
BiTNode
*pBiNode
=
T;
SqStack
S;
InitStack(&S);
Push(&S,
(SElemType)T);
while
(!IsStackEmpty(S))
{
while
(pBiNode)
{
VisitNode(pBiNode->data);
if
(pBiNode
!=
T)
{
Push(&S,
(SElemType)pBiNode);
}
pBiNode
=
pBiNode->lchild;
}
if(pBiNode
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
}
if
(
pBiNode->rchild
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
//如果此時棧已空，就有問題
}
pBiNode
=
pBiNode->rchild;
}
return
0;
}