二叉树遍历c语言,c语言二叉树的建立与遍历，，程序总停留在输入环节，下不去！！急

二叉树遍历c语言,c语言二叉树的建立与遍历，，程序总停留在输入环节，下不去！！急详细介绍

本文目录一览： C语言二叉树的创建和遍历

void creat(tree *t1)
{
char ch;
struct node *th; //看到这个th了吗？不需要的
ch=getchar();
if(ch=='.') t1=NULL;
else
{
th=(tree *)malloc(sizeof(tree)); //改成t1=(tree *)malloc(sizeof(tree));
t1->c=ch;
printf("%c",t1->c);
creat(t1->lchild);
creat(t1->rchild);
}
我写了一个二叉树 你给看看 一定能行的 我自己用了
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //结点的最大个数
typedef struct BinTNode{
char data;
struct BinTNode *lchild,*rchild;
}BinTNode,*BinTree; //自定义二叉树的结点类型
//定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========以广义表显示二叉树==============
void DisTree(BinTree T)
{
if(T)
{
printf("%c",T->data);
if((T->lchild)||(T->rchild))
{
if(T->lchild)
{
printf("%c",'(');
DisTree(T->lchild);
}
if(T->rchild)
{
printf("%c",',');
DisTree(T->rchild);
printf("%c",')');
}
}
}
}
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(BinTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))
printf("Error!");
T->data=ch;
T->lchild=CreatBinTree(T->lchild);
T->rchild=CreatBinTree(T->rchild);
}
return T;
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
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)
leaf=leaf+1; //若左右深度为0，即为叶子。
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; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree T,root;
int i,depth;
printf("\n");
printf("输入完全二叉树的先序序列:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(T); //创建二叉树，返回根结点
DisTree(root);
printf("\n");
do //从菜单中选择遍历方式，输入序号。
{
printf("\t********** 菜单 ************\n");
printf("\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: {printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
}break;
case 2: {printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
}break;
case 3: {printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
}break;
case 4: {depth=TreeDepth(root); //求树的深度及叶子数
printf("树深=%d 树总结点数=%d",depth,NodeNum);
printf(" 树叶子数=%d",leaf);
}break;
case 5: {printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
}break;
default: exit(1);
}
}while(i>=0&&i<6);
}
兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦！！

二叉树先序遍历算法流程图怎么画，学的是数据结构c语言。

在计算机软件专业中，数据结构、以及 C 语言这两门课程是非常重要的两门课程。最为重要的是：如果将来想做计算机软件开发工作的话，那么对 C 语言中的指针编程、以及递归的概念是必须要熟练精通掌握的，因为它和数据结构课程中的链表、二叉树等内容的关系实在是太紧密了。但是这个编程技能必须要依靠自己多上机实践才能够真正彻底掌握的。
首先要搞明白二叉树的几种遍历方法：（1）、先序遍历法：根左右；（2）、中序遍历法：左根右；（3）、后序遍历法：左右根。其中根：表示根节点；左：表示左子树；右：表示右子树。
至于谈到如何画先序遍历的流程图，可以这样考虑：按照递归的算法进行遍历一棵二叉树。
程序首先访问根节点，如果根节点的值为空（NULL），则停止访问；如果根节点的值非空，则递归访问二叉树的左子树（left），然后是依然判断二叉树下面的左子树下面的根节点是否为空（NULL），如果根节点的值为空（NULL），则返回上一层，再访问二叉树的右子树（right）。依此类推。

c语言二叉树的建立与遍历，，程序总停留在输入环节，下不去！！急

#include

#include

#define M 10typedef struct bnode{ char data; struct bnode *lchild; struct bnode *rchild;}Bnode, *BTree;/*建立二叉树*/ void creat_BTree(BTree* T){ char n; n=getchar(); if(n=='#') *T=NULL; else if(n=='\n') return; else { (*T)=(BTree)malloc(sizeof(Bnode)); (*T)->data=n; creat_BTree(&(*T)->lchild); creat_BTree(&(*T)->rchild); }}/*前序遍历*/ void r_preorder(BTree T){ if(T) { printf("%c",T->data); r_preorder(T->lchild); r_preorder(T->rchild); }}/*后序遍历*/ void r_posorder(BTree T){ if(T) { r_posorder(T->lchild); r_posorder(T->rchild); printf("%c",T->data); }}/*层次遍历*/void r_levelorder(BTree T){ BTree q[1024]; BTree p; int front=0,rear=0; if(T) { q[rear]=T; rear=(rear+1)%M; } while(front!=rear) { p=q[front]; printf("%c ",p->data); if(p->lchild) { q[rear]=p->lchild; rear=(rear+1)%M; } if(p->rchild) { q[rear]=p->rchild; rear=(rear+1)%M; } front = (front+1)%M; }}int main(){ BTree T; T=NULL; int select; while(1) { printf("\n请选择要进行的操作：\n"); printf(" 1 创建二叉树\n"); printf(" 2 前序遍历\n"); printf(" 3 后序遍历\n"); printf(" 4 层次遍历\n"); printf(" 5 结束程序\n"); printf("=========================\n"); scanf("%d",&select); getchar(); switch (select) { case 1: { printf("请按前序次序输入各结点的值，以#表示空树（输入时可连续输入）\n"); creat_BTree(&T); break; } case 2: { if(!T) printf("未建树，请先执行1操作建树！\n"); else r_preorder(T); break; } case 3: { if(!T) printf("未建树，请先执行1操作建树！\n"); else r_posorder(T); break; } case 4: { if(!T) printf("未建树，请先执行1操作建树！\n"); else r_levelorder(T); break; } default:; } }}

求编一个c代码，输入满二叉树的先序遍历，输出中序遍历和后序遍历

lhj
在淘宝搜快客利，认准店主sinohzxu，官方自助话费充值
#include

#include

#include

#define NULL 0

typedef struct btree

{

char data;

struct btree *pLeft;

struct btree *pRight;

}quickli;

quickli* constuctTree(char input[], int beginIndex, int endIndex)

{

if (beginIndex > endIndex) return NULL;

quickli* root=(quickli *)malloc(sizeof(quickli));

root->data=input[beginIndex];

root->pLeft=constuctTree(input , beginIndex+1,(endIndex+beginIndex)/2);

root->pRight=constuctTree(input , (endIndex+beginIndex)/2+1,endIndex);

return root;

}

void inorderTree(quickli* tree)

{

if (tree == NULL) return ;

inorderTree(tree->pLeft);

printf("%c",tree->data);

inorderTree(tree->pRight);

}

void postorderTree(quickli* tree)

{

if (tree == NULL) return ;

postorderTree(tree->pLeft);

postorderTree(tree->pRight);

printf("%c",tree->data);

}

int main()

{

printf("请输入一个满二叉树先序遍历（如ABCDEFG）：\n");

char input[100];

scanf("%s",input);

double check = log(strlen(input)+1)/log(2);

if(check != (int)check)

{

printf("错误：满二叉树的序列长度必须等于2^n-1（^是幂的意思）\n");

return -1;

}

quickli* tree=constuctTree(input,0,strlen(input)-1);

printf("中序遍历如下：\n");

inorderTree(tree);

printf("\n");

printf("后序遍历如下：\n");

postorderTree(tree);

printf("\n");

return 0;

}

在淘宝搜快客利，认准店主sinohzxu，官方自助话费充值

C语言数据结构，急求在线二叉树先序中序后序递归遍历

#include

#include

#include

#define

MaxNode

100

typedef

char

DataType;

typedef

struct

node

{

DataType

data;

struct

node

*lchild;

struct

node

*rchild;

}BiTNode,BiTree;

void

CreateBiTree(BiTree

*bt)//建立一个二叉树

{

char

ch;

//ch=getchar();

scanf("%c",&ch);

if

(ch=='

')

bt=NULL;

else{

bt=(BiTree*)malloc(sizeof(BiTNode));

bt->data=ch;

CreateBiTree(bt->lchild);

CreateBiTree(bt->rchild);

}

}

void

PreOrder(BiTree

*root)//前序遍历

{

if(root!=NULL)

{

Visit(root->data);

PreOrder(root->lchild);

PreOrder(root->rchild);

}

}

void

InOrder(BiTree

*root)//中序遍历

{

if(root!=NULL)

{

InOrder(root->lchild);

Visit(root->data);

InOrder(root->rchild);

}

}

void

LaOrder(BiTree

*root)//后序遍历

{

if(root!=NULL)

{

PreOrder(root->lchild);

PreOrder(root->rchild);

Visit(root->data);

}

}

void

main()

{

BiTree

*bt;

printf("请输入数据:\n");

bt=

NULL;

CreateBiTree(bt);

//and

here

printf("\n

结果如下：\n");

printf("先序遍历的结果为：\n");

PreOrder(bt);

printf("\n");

printf("中序遍历的结果为：\n");

InOrder(bt);

printf("\n");

printf("后序遍历的结果为：\n");

LaOrder(bt);

}

有个Visit（）函数

你没写！！

我只是改了语法错误！！

只剩那一个函数没定义

你定义下就没语法错误了！

！

用C语言建立一棵二叉树,使用二杈链表存储,对其进行后续遍历,输出后序遍历序列

#include

#include

#include

#define Maxsize 100

typedef int datatype;

typedef struct node

{

datatype data;

struct node* lchild;

struct node* rchild;

}BTNode;

void CreatBTNode(BTNode *&b,char * str)

{

BTNode *p,*st[Maxsize];

int top=-1;

p=NULL;

b=NULL;

int j=0,k;

char ch=str[j];

while(ch!='\0')

{

switch(ch)

{

case '(':top++;st[top]=p;k=1;break;

case ')':top--;break;

case ',':k=2;break;

default:p=(BTNode *)malloc(sizeof(BTNode));

p->data=ch;p->lchild=p->rchild=NULL;

if(b==NULL)

{

b=p;

}

else

{

switch(k)

{

case 1:st[top]->lchild=p;break;

case 2:st[top]->rchild=p;break;

}

}

}

j++;ch=str[j];

}

}

void DispBTNode(BTNode *b)

{

if(b!=NULL)

{

printf("%c",b->data);

if(b->lchild!=NULL||b->rchild!=NULL)

{

printf("(");

DispBTNode(b->lchild);

if(b->rchild!=NULL)

printf(",");

DispBTNode(b->rchild);

printf(")");

}

}

}

BTNode *FindNode(BTNode *b,char x)

{

BTNode *p=NULL;

if(b==NULL)

{

return NULL;

}

else if(b->data==x)

{

return b;

}

else

{

p=FindNode(b->lchild,x);

if(p!=NULL)

{

return p;

}

else

{

return FindNode(b->rchild,x);

}

}

}

void main()

{

BTNode *b,*q;

char str[100];

printf("您输入的二叉树为\n");

scanf("%s",&str);

CreatBTNode(b,str);

DispBTNode(b);

q=FindNode(b,'A');

printf("\n");

printf("*********************************\n");

printf("%c\n",q->data);

}

急急急！求C语言的数据结构二叉树递归遍历程序！

#include"stdio.h"//二叉树
#include"stdlib.h"
typedef
struct
node
{
char
data;
struct
node
*lchild,*rchild;
}BinTNode;
typedef
BinTNode*
BinTree;
void
GreateBinTree(BinTree
*T)//以先序遍历为依据构造二叉树,T为指向根指针的指针.
{
//空结点以空格代替.
char
ch;
if((ch=getchar())=='
')
*T=NULL;
else
{
*T=(BinTree)malloc(sizeof(BinTNode));
(*T)->data=ch;
GreateBinTree(&((*T)->lchild));
GreateBinTree(&((*T)->rchild));
}
}
void
Lorder(BinTree
T)//先序遍历二叉树.
{
if(T)
{
printf("%c
",T->data);
Lorder(T->lchild);
Lorder(T->rchild);
}
}
void
Morder(BinTree
T)//中序遍历二叉树.
{
if(T)
{
Morder(T->lchild);
printf("%c
",T->data);
Morder(T->rchild);
}
}
void
Rorder(BinTree
T)//后序遍历二叉树.
{
if(T)
{
Rorder(T->lchild);
Rorder(T->rchild);
printf("%c
",T->data);
}
}
/******************************************************/
/*
二叉树的建立深度优先遍历求叶子个数求深度
*/
/******************************************************/
#include
"stdio.h"
#include
"string.h"
#include
"stdlib.h"
#define
NULL
0
typedef
struct
bitnode{
int
data;
struct
bitnode
*lchild,*rchild;
}bitnode,*bitree;
/*创建一个二杈树以#号结束*/
bitree
create(bitree
t){
char
ch;
ch=getchar();
if(ch=='#')
t=NULL;
else{
t=(bitree)malloc(sizeof(bitnode));
t->data=ch;
t->lchild=create(t->lchild);
t->rchild=create(t->rchild);
}
return
t;
}
/*递归遍历*/
void
preorder(bitree
t){
if(t){
printf("%c",t->data);
/*先序*/
preorder(t->lchild);
/*printf("%c",t->data);
中序*/
preorder(t->rchild);
/*printf("%c",t->data);
后序*/
}
}
/*求深度*/
int
depth(bitree
t){
int
depthval,depl,depr;
if(!t)
depthval=0;
else{
depl=depth(t->lchild);
depr=depth(t->rchild);
depthval=1+(depl>depr?depl:depr);
}
return
depthval;
}
/*求叶子数*/
int
countleaf(bitree
t){
int
count=0;
if(!t)
count=0;
else
if((!t->lchild)&&(!t->rchild))
count++;
else
count=countleaf(t->lchild)+countleaf(t->rchild);
return
count;
}
/*主函数*/
main(){
bitree
t=NULL;
printf("\nplease
input
a
tree:");
t=create(t);
preorder(t);
printf("\ndepth:%d\nleave:%d\n",depth(t),countleaf(t));
system("pause");
}
程序以调试通过！！！！！

设计一个c语言程序，实现二叉树的前序、中序、后序的递归、非递归遍历运算

#include

// malloc()等

#include

// 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等

#include

// atoi()，exit()

#include

// 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode

{

int data; // 结点的值

BiTNode *lchild,*rchild; // 左右孩子指针

}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空

void visit(int e)

{ printf("%d ",e); // 以整型格式输出

}

void InitBiTree(BiTree &T)

{ // 操作结果：构造空二叉树T

T=NULL;

}

void CreateBiTree(BiTree &T)

{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，

// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改

int number;

scanf("%d",&number); // 输入结点的值

if(number==Nil) // 结点的值为空

T=NULL;

else // 结点的值不为空

{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点

if(!T)

exit(OVERFLOW);

T->data=number; // 将值赋给T所指结点

CreateBiTree(T->lchild); // 递归构造左子树

CreateBiTree(T->rchild); // 递归构造右子树

}

}

void DestroyBiTree(BiTree &T)

{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T

if(T) // 非空树

{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作

DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作

free(T); // 释放根结点

T=NULL; // 空指针赋0

}

}

void PreOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1

// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ Visit(T->data); // 先访问根结点

PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树

PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树

}

}

void InOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数

// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T)

{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树

Visit(T->data); // 再访问根结点

InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树

}

}

void PostOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数

// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树

PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树

Visit(T->data); // 最后访问根结点

}

}

void main()

{

BiTree T;

InitBiTree(T); // 初始化二叉树T

printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");

CreateBiTree(T); // 建立二叉树T

printf("先序递归遍历二叉树： ");

PreOrderTraverse(T,visit); // 先序递归遍历二叉树T

printf("\n中序递归遍历二叉树： ");

InOrderTraverse(T,visit); // 中序递归遍历二叉树T

printf(" \n后序递归遍历二叉树：");

PostOrderTraverse(T,visit); // 后序递归遍历二叉树T

printf("\n");

}

急求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

＃i nclude

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

TreeNodeStack;

};

#endif

BinaryTree.cpp:

/********************************************************************

created: 2006/07/04

filename: BinaryTree.cpp

author: 李创

http://www.cppblog.com/converse/

purpose: 演示二叉树的算法

*********************************************************************/

＃i nclude

＃i nclude

＃i nclude

＃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

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

＃i nclude

＃i nclude

＃i nclude

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

#include

#include

#define NULL 0

typedef struct BiTNode

{ char data;

struct BiTNode *lchild,*rchild;

}tree;

typedef struct Sqtack

{ int *top;

int *base;

}S;

int m=0;

tree *CreateBitree(tree *t,int i)

{

char ch;

tree lchild,rchild;

switch(i)

{ case 0 : printf("input tree's gen ");break;

case 1 : printf("input tree's lchild ");break;

case 2 : printf("input tree's rchild ");break;

}

printf("input a zi fu\n");

ch=getch();

if(ch==' ') { t=NULL;return(t);}

else

{ t=(tree *)malloc(sizeof(tree));

t->data=ch;

t->lchild=CreateBitree(&lchild,1);

t->rchild=CreateBitree(&rchild,2);

return(t);

}

}

void Initsqtack(S *L)

{ L->base=(int *)malloc(100*sizeof(S));

L->top=L->base;

}

void push(S *L,int e)

{ *(L->top++)=e;

}

int pop(S *L)

{ int e;

e=*(--L->top);

return(e);

}

void printbitree(tree *t,char ch,int n,S *L)

{ int i;

if(t)

{ n++;

switch(ch)

{ case 0 : printf("%3c",t->data);break;

case 1 : printf("%3c",t->data);break;

case 2 : {printf("\n");for(i=1;i

data);}break;

}

printbitree(t->lchild,1,n,L);

printbitree(t->rchild,2,n,L);

}

else push(L,n);

}

void count(tree *t,S *l,int e,tree *parent)

{

if(t)

{ e=t->data;

count(t->lchild,l,e,t);

count(t->rchild,l,e,t);

}

else if(!parent->lchild&&!parent->rchild&&parent)

{ push(l,e);

m++;

}

}

void Inordertravel(tree *t)

{ if(t)

{

Inordertravel(t->lchild);

printf("%3c",t->data);

Inordertravel(t->rchild);

}

}

void Postordertravel(tree *t)

{ if(t)

{ Postordertravel(t->lchild);

Postordertravel(t->rchild);

printf("%3c",t->data);

}

}

int max(int a,int b)

{ if(a>b) return(a);

else return(b);

}

void main()

{ tree T,*tree,*parent=NULL;

int i;

char c;

S L,L1;

tree=CreateBitree(&T,0);

Initsqtack(&L);

Initsqtack(&L1);

clrscr();

printf("xian xu bian li de shu is:\n");

printbitree(tree,0,0,&L);

i=pop(&L);

while(L.top!=L.base)

i=max(i,pop(&L));

printf("\n");

printf("the tree length is %d\n",i);

printf("zhong xu bian li de shu is:\n");

Inordertravel(tree);

printf("\nhou xu bian li de shu is:\n");

Postordertravel(tree);

printf("\n");

count(tree,&L1,0,parent);

printf("the ye zi is :\n");

while(L1.top!=L1.base)

{ c=pop(&L1);

printf("%3c",c);

pop(&L1);

}

printf("\nye zi geng you %d ge\n",m/2);

}