二叉树层序遍历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) 开始的 用队列方法遍历的