二叉樹層序遍歷c語言

『壹』 層次遍歷二叉樹的c語言代碼中 if(bt==NULL) return; front=-1;rear=0;這是什麼意思

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct bitnode
{
datatype data;
struct bitnode *lchild,*rchild;
}tree;
tree *init()
{
tree *bt;
bt=NULL;
bt=(tree*)malloc(sizeof(tree));
bt->lchild=NULL;
bt->rchild=NULL;
return bt;
}
tree *create(tree *bt)
{
char ch;
scanf("%c",&ch);
if(ch=='0')
{
bt=NULL;
return bt;
}
else
{
bt=(tree *)malloc(sizeof(tree));
bt->data=ch;
bt->lchild=create(bt->lchild);
bt->rchild=create(bt->rchild);
}
return bt;
}
tree *Linsert(datatype x,tree *parent)
{
tree *p;
if(parent==NULL)
{
printf("insert error\n");
return NULL;
}
if((p=(tree*)malloc(sizeof(tree)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->rchild=NULL;
if(parent->lchild==NULL)
parent->lchild=p;
else
{
p->lchild=parent->lchild;
parent->lchild=p;
}
return parent;
}
tree *Rinsert(datatype x,tree *parent)
{
tree *p;
if(parent==NULL)
{
printf("insert error\n");
return NULL;
}
if((p=(tree*)malloc(sizeof(tree)))==NULL)
return NULL;
p->data=x;
p->lchild=NULL;
p->彎宴rchild=NULL;
if(parent->rchild==NULL)
parent->rchild=p;
else
{
p->rchild=parent->rchild;
parent->rchild=p;
}
return parent;
}
tree *Ldel(tree *parent)
{
tree *p;
if(parent==NULL||parent->lchild==NULL)
{
printf("delete error\州鬧明n");
return NULL;
}
p=parent->lchild;
parent->lchild=NULL;
free(p);
return parent;
}
tree *Rdel(tree *parent)
{
tree *p;
if(parent==NULL||parent->rchild==NULL)
{
printf("delete error\n");
return NULL;
}
p=parent->rchild;
parent->rchild=NULL;
free(p);
return parent;
}
void visit(tree *bt)
{
printf("%c ",bt->data);
}
void preorder(tree *bt)
{
if(bt==NULL)
return ;
visit(bt);
preorder(bt->lchild);
preorder(bt->rchild);
}
void inorder(tree *bt)
{
if(bt==NULL)
return ;
inorder(bt->lchild);
visit(bt);
inorder(bt->rchild);
}
void postorder(tree *bt)
{
if(bt==NULL)
return ;
postorder(bt->lchild);
postorder(bt->冊告rchild);
visit(bt);
}

tree *search(tree *bt,datatype x)
{
tree *p;
p=NULL;
if(bt)
{
if(bt->data==x)
return bt;
if(bt->lchild)
p=search(bt->lchild,x);
if(p!=NULL)
return p;
if(bt->rchild)
p=search(bt->rchild,x);
if(p!=NULL)
return p;
}
return p;
}

void nrpreorder(tree *bt)
{
tree *stack[1000],*p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&&top==-1))
{
while(p!=NULL)
{
visit(p);
top++;
stack[top]=p;
p=p->lchild;
}
if(top<0)
return ;
else
{
p=stack[top];
top--;
p=p->rchild;
}
}

}

void nrinorder(tree *bt)
{
tree *stack[1000],*p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&&top==-1))
{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top<0)
return ;
else
{
p=stack[top];
top--;
visit(p);
p=p->rchild;
}
}

}

void nrpostorder(tree *bt)
{
int top;
tree *d[1000],*dd;
tree *stack[1000],*p;
if(bt==NULL)
return ;
top=-1;
p=bt;
while(!(p==NULL&&top==-1))
{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p->lchild;
}
dd=stack[top];
if(top>-1)
if(dd)
{
p=stack[top]->rchild;
d[top]=stack[top];
stack[top]=NULL;
dd=NULL;
}
else
{
p=d[top];
top--;
visit(p);
p=NULL;
}
}
}
void levelorder(tree *bt)
{
tree *queue[1000];
int front,rear;
if(bt==NULL)
return ;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{
front++;
visit(queue[front]);
if(queue[front]->lchild!=NULL)
{
rear++;
queue[rear]=queue[front]->lchild;
}
if(queue[front]->rchild!=NULL)
{
rear++;
queue[rear]=queue[front]->rchild;
}
}
}

int countleaf(tree *bt)
{
if(bt==NULL)
return 0;
if(bt->lchild==NULL&&bt->rchild==NULL)
return 1;
return(countleaf(bt->lchild)+countleaf(bt->rchild));
}
int main()
{
tree *bt,*p;
int n=1,m,t;
char x;
printf("-----------------------程序說明---------------------------\n");
printf("1．本程序涉及二叉樹的所有操作。\n");
printf("2．創建操作為先序輸入，輸入0代表空。\n");
printf("3．刪除操作和插入操作之前必須使用查找操作找到其雙親。\n");
printf("4．輸入回車鍵開始本程序。\n");
printf("----------------------------------------------------------\n");
getchar();
while(n!=0)
{
printf("choose:\n1、Create a bitree 2、Search\n3、Preorder 4、Inorder 5、Postorder\n6、Levelorder 7、The number of leaves \n0、End\n");
printf("Do: ");
scanf("%d",&n);
getchar();
switch(n)
{
case 1:
bt=init();
printf("Create a bitree :");
bt=create(bt);
break;
case 2:
printf("Input a char :");
scanf("%c",&x);
getchar();
p=search(bt,x);
if(p!=NULL)
{
printf("1、do nothing \n2、Insret L-tree 3、Insert R-tree \n4、Delete L-tree 5、Delete R-tree \n");
printf("Do: ");
scanf("%d",&m);
getchar();
switch(m)
{
case 1: break;
case 2:
printf("Input a char :");
scanf("%c",&x);
Linsert(x,p);
break;
case 3:
printf("Input a char :");
scanf("%c",&x);
Rinsert(x,p);
break;
case 4:
if(Ldel(p)!=NULL)
printf("Complish delete !\n");
break;
case 5:
if(Rdel(p)!=NULL)
printf("Complish delete !\n");
break;
default : printf("Input error\n");
}
}
else printf("The char dose not exist\n");
break;
case 3:
printf("1、Recursive 2、Nonrecursive\n");
printf("Do: ");
scanf("%d",&t);
if(t==1)
preorder(bt);
else
nrpreorder(bt);
printf("\n");
break;
case 4:
printf("1、Recursive 2、Nonrecursive\n");
printf("Do: ");
scanf("%d",&t);
if(t==1)
inorder(bt);
else
nrinorder(bt);
printf("\n");
break;
case 5:
printf("1、Recursive 2、Nonrecursive\n");
printf("Do: ");
scanf("%d",&t);
if(t==1)
postorder(bt);
else
nrpostorder(bt);
printf("\n");
break;
case 6:
levelorder(bt);
break;
case 7:
printf("%d\n",countleaf(bt));
break;
case 0:break;
default : printf("Input error\n");
}
printf("\n");
}
return 0;
}

『貳』 求用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);
}

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

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

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

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

[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語言編一個演算法 按層次遍歷二叉樹的結點

#include<stdio.h>
#include<malloc.h>
// 定義隊列的最大長差乎判度
#define QUEUE_LENGTH 100
//
// 二叉樹與雙向鏈表數據結構定義，
//
typedef struct struNode
{
int data;
struct struNode *lchild; //二叉樹中的左子樹或雙向鏈表中的前向指針
struct struNode*rchild; //二叉樹中的右子樹或雙向鏈表中的後向指針
}BitNode , *BitNodePtr , DuLNode , *DuLNodePtr;
//
// 生成二叉樹
//
BitNodePtr Create_bitree()
{
int m;
BitNodePtr T;
T = NULL;
scanf("%d", &m);
if(m)
{
T = (BitNodePtr)malloc(sizeof(BitNode));
T->data = m;
T->lchild = Create_bitree();
T->rchild = Create_bitree();
}
return T;
}
//
// 層次遍歷二叉樹
//
void ReadBitTree(BitNodePtr pRoot)
{
BitNodePtr pQueue[QUEUE_LENGTH];
int head = 0 , tail = 1;
pQueue[0] = pRoot;
//結束的條件是head向後移動一個位置後，與tail重合
while (head != tail)
{
printf("%d " , pQueue[head]->data);
//左孩子入隊列
if (pQueue[head]->lchild)
{
pQueue[tail] = pQueue[head]->lchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//隊列長度太小，退出
printf("虛改Queue overflow!");
return;
}
}
//右孩子入隊列
if (pQueue[head]->rchild)
{
pQueue[tail] = pQueue[head]->rchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//隊列長度頃清太小，退出
printf("Queue overflow!");
return;
}
}
//隊首出隊列
head = (head + 1) % QUEUE_LENGTH;
}
printf("\n");
return;
}
void main()
{
BitNodePtr Root;
Root = Create_bitree();
ReadBitTree(Root);
return;
}

『伍』 急求C語言寫二叉樹的遍歷

BinaryTree.h:

/********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李創
http://www.cppblog.com/converse/

purpose: 演示二叉樹的演算法
*********************************************************************/

#ifndef BinaryTree_H
#define BinaryTree_H

＃i nclude <stdlib.h>
＃i nclude <stack>

class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;

TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}

}TreeNode, *PTreeNode;

public:
enum TraverseType
{
PREORDER = 0, // 前序
INORDER = 1, // 中序
POSTORDER = 2, // 後序
LEVELORDER = 3 // 層序
};

BinaryTree(Item Array[], int nLength);
~BinaryTree();

PTreeNode GetRoot()
{
return m_pRoot;
}

// 遍歷樹的對外介面
// 指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
void Traverse(TraverseType traversetype, bool bRec = true);

private:
PTreeNode CreateTreeImpl(Item Array[], int nLength);
void DetroyTreeImpl(PTreeNode pTreenode);

void PreTraverseImpl(PTreeNode pTreenode); // 遞歸前序遍歷樹
void InTraverseImpl(PTreeNode pTreenode); // 遞歸中序遍歷樹
void PostTraverseImpl(PTreeNode pTreenode); // 遞歸後序遍歷樹

void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非遞歸前序遍歷樹
void NoRecInTraverseImpl(PTreeNode pTreenode); // 非遞歸中序遍歷樹
void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非遞歸後序遍歷樹

void LevelTraverseImpl(PTreeNode pTreenode);

PTreeNode m_pRoot; // 根結點

// 採用STL裡面的stack作為模擬保存鏈表結點的stack容器
typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
};

#endif

BinaryTree.cpp:

/********************************************************************
created: 2006/07/04
filename: BinaryTree.cpp
author: 李創
http://www.cppblog.com/converse/

purpose: 演示二叉樹的演算法
*********************************************************************/

＃i nclude <iostream>
＃i nclude <assert.h>
＃i nclude <queue>
＃i nclude "BinaryTree.h"

BinaryTree::BinaryTree(Item Array[], int nLength)
: m_pRoot(NULL)
{
assert(NULL != Array);
assert(nLength > 0);

m_pRoot = CreateTreeImpl(Array, nLength);
}

BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}

// 按照中序遞歸創建樹
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
int mid = nLength / 2;
PTreeNode p = new TreeNode(Array[mid]);

if (nLength > 1)
{
p->pLeft = CreateTreeImpl(Array, nLength / 2);
p->pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
}

return p;
}

void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
if (NULL != pTreenode->pLeft)
{
DetroyTreeImpl(pTreenode->pLeft);
}
if (NULL != pTreenode->pRight)
{
DetroyTreeImpl(pTreenode->pRight);
}

delete pTreenode;
pTreenode = NULL;
}

// 遍歷樹的對外介面
// 指定遍歷類型和是否是非遞歸遍歷,默認是遞歸遍歷
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
switch (traversetype)
{
case PREORDER: // 前序
{
if (true == bRec)
{
std::cout << "遞歸前序遍歷樹\n";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸前序遍歷樹\n";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;

case INORDER: // 中序
{
if (true == bRec)
{
std::cout << "遞歸中序遍歷樹\n";
InTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸中序遍歷樹\n";
NoRecInTraverseImpl(m_pRoot);
}
}
break;

case POSTORDER: // 後序
{
if (true == bRec)
{
std::cout << "遞歸後序遍歷樹\n";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout << "非遞歸後序遍歷樹\n";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;

case LEVELORDER: // 層序
{
std::cout << "層序遍歷樹\n";
LevelTraverseImpl(m_pRoot);
}
}

std::cout << std::endl;
}

// 遞歸前序遍歷樹
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

std::cout << "Item = " << pTreenode->Node << std::endl;

PreTraverseImpl(pTreenode->pLeft);

PreTraverseImpl(pTreenode->pRight);
}

// 非遞歸前序遍歷樹
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到盡頭
{
std::cout << "Item = " << pNode->Node << std::endl; // 訪問當前結點
NodeStack.push(pNode->pLeft); // 左子樹根結點入棧
}
NodeStack.pop(); // 左子樹根結點退

棧
if (!NodeStack.empty())
{
pNode = NodeStack.top();
NodeStack.pop(); // 當前結點退棧
NodeStack.push(pNode->pRight); // 當前結點的右子樹根結點入棧
}
}
}

// 中序遍歷樹
// 中序遍歷輸出的結果應該和用來初始化樹的數組的排列順序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
InTraverseImpl(pTreenode->pLeft);
}

std::cout << "Item = " << pTreenode->Node << std::endl;

if (NULL != pTreenode->pRight)
{
InTraverseImpl(pTreenode->pRight);
}
}

// 非遞歸中序遍歷樹
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);

while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到盡頭
{
NodeStack.push(pNode->pLeft);
}

NodeStack.pop();

if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
{
std::cout << "Item = " << pNode->Node << std::endl;
NodeStack.pop();
NodeStack.push(pNode->pRight);
}
}
}

// 後序遍歷樹
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

if (NULL != pTreenode->pLeft)
{
PostTraverseImpl(pTreenode->pLeft);
}

if (NULL != pTreenode->pRight)
{
PostTraverseImpl(pTreenode->pRight);
}

std::cout << "Item = " << pTreenode->Node << std::endl;
}

// 非遞歸後序遍歷樹
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

TreeNodeStack NodeStack;
PTreeNode pNode1, pNode2;
NodeStack.push(pTreenode);
pNode1 = pTreenode->pLeft;

bool bVisitRoot = false; // 標志位,是否訪問過根結點
while (!NodeStack.empty())
{
while (NULL != pNode1) // 向左走到盡頭
{
NodeStack.push(pNode1);
pNode1 = pNode1->pLeft;
}

pNode1 = NodeStack.top();
NodeStack.pop();

if (NULL == pNode1->pRight) // 如果沒有右子樹就是葉子結點
{
std::cout << "Item = " << pNode1->Node << std::endl;
pNode2 = pNode1;
pNode1 = NodeStack.top();

if (pNode2 == pNode1->pRight) // 如果這個葉子結點是右子樹
{
std::cout << "Item = " << pNode1->Node << std::endl;
NodeStack.pop();
pNode1 = NULL;
}
else // 否則訪問右子樹
{
pNode1 = pNode1->pRight;
}
}
else // 訪問右子樹
{
if (pNode1 == pTreenode && true == bVisitRoot) // 如果已經訪問過右子樹那麼就退出
{
std::cout << "Item = " << pNode1->Node << std::endl;
return;
}
else
{
if (pNode1 == pTreenode)
{
bVisitRoot = true;
}

NodeStack.push(pNode1);
pNode1 = pNode1->pRight;
}
}
}
}

// 按照樹的層次從左到右訪問樹的結點
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;

// 層序遍歷用於保存結點的容器是隊列
std::queue<PTreeNode> NodeQueue;
PTreeNode pNode;
NodeQueue.push(pTreenode);

while (!NodeQueue.empty())
{
pNode = NodeQueue.front();
NodeQueue.pop();
std::cout << "Item = " << pNode->Node << std::endl;

if (NULL != pNode->pLeft)
{
NodeQueue.push(pNode->pLeft);
}
if (NULL != pNode->pRight)
{
NodeQueue.push(pNode->pRight);
}
}
}

main.cpp

/********************************************************************
created: 2006/07/04
filename: main.cpp
author: 李創
http://www.cppblog.com/converse/

purpose: 測試二叉樹的演算法
*********************************************************************/

＃i nclude "BinaryTree.h"

＃i nclude <stdio.h>
＃i nclude <stdlib.h>
＃i nclude <time.h>
＃i nclude <iostream>

void DisplayArray(int array[], int length)
{
int i;

for (i = 0; i < length; i++)
{
printf("array[%d] = %d\n", i, array[i]);
}
}

void CreateNewArray(int array[], int length)
{
for (int i = 0; i < length; i++)
{
array[i] = rand() % 256 + i;
}
}

int main()
{
int array[10];
srand(time(NULL));

// 創建數組
CreateNewArray(array, 10);
DisplayArray(array, 10);

BinaryTree *pTree = new BinaryTree(array, 10);

// 測試前序遍歷
pTree->Traverse(BinaryTree::PREORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::PREORDER, false);

// 測試中序遍歷
pTree->Traverse(BinaryTree::INORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::INORDER, false);
// 測試後序遍歷
pTree->Traverse(BinaryTree::POSTORDER);
std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
std::cout << "root->left = " << pTree->GetRoot()->pLeft->Node << std::endl;
std::cout << "root->right = " << pTree->GetRoot()->pRight->Node << std::endl;
pTree->Traverse(BinaryTree::POSTORDER, false);
// 測試層序遍歷
pTree->Traverse(BinaryTree::LEVELORDER);

system("pause");

delete pTree;

return 0;
}

『陸』 編寫按層次順序（同一層從左至右）遍歷二叉樹的演算法

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}

void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}
遍歷方法從void cengci(bitree *t) 開始的 用隊列方法遍歷的