二叉树的非递归遍历c语言

Ⅰ c语言二叉树的遍历。

二叉树的前中后遍历（递归与非递归）
#include<stdio.h>
#include<stdlib.h>

typedef struct NODE
{
char value;
struct NODE *LChild;
struct NODE *RChild;
}BiTNode,*BiTree; //二叉树数据结构
BiTree root;
typedef struct node
{
BiTNode *pointer;
struct node *link;
}LinkStackNode,*LinkStack; //链栈数据结构
LinkStack S;
int count = 0;
//BiTNode * InitTree(BiTree Tree);
BiTNode *CreateTree(BiTree Tree); //创建二叉树
void PreOrder(BiTree Tree); //递归前序遍历二叉树
void MidOrder(BiTree Tree); //递归中序遍历二叉树
void PostOrder(BiTree Tree); //递归后序遍历二叉树
void NPreOrder(BiTree Tree); //非递归前序遍历二叉树
void NMidOrder(BiTree Tree); //非递归中序遍历二叉树
void NPostOrder(BiTree Tree); //非递归后序遍历二叉树
//---------------------------------------------------
LinkStackNode *InitLinkStack(LinkStack top); //初始化链栈
void Push(LinkStack top,BiTNode *p); //进栈操作
BiTNode * Pop(LinkStack top); //出栈操作
//int IsEmpty(LinkStack S); //判断栈是否为空
void main()
{
//BiTree tree;
//root = InitTree(tree);
root = CreateTree(root);
PreOrder(root);
printf("\n");
MidOrder(root);
printf("\n");
PostOrder(root);
printf("\n");
NPreOrder(root);
printf("\n");
NMidOrder(root);
printf("\n");
NPostOrder(root);
printf("\n");
}

/*BiTNode * InitTree(BiTree Tree)
{
//BiTNode *root;
//root = Tree;
Tree = (BiTNode *)malloc(sizeof(BiTNode));
Tree = NULL;
//Tree->LChild = NULL;
//Tree->RChild = NULL;
return Tree;
}*/

//二叉树的扩展先序遍历的创建
BiTNode * CreateTree(BiTree Tree)
{
char ch;
ch = getchar();
if(ch == '.')
Tree = NULL;
else
{
Tree = (BiTNode *)malloc(sizeof(BiTNode));
if(Tree)
{
Tree->value = ch;
Tree->LChild = CreateTree(Tree->LChild);
Tree->RChild = CreateTree(Tree->RChild);
}
}
return Tree;
}

//递归前序遍历二叉树
void PreOrder(BiTree Tree)
{
if(Tree)
{
printf("%c",Tree->value);
PreOrder(Tree->LChild);
PreOrder(Tree->RChild);
}
}

//递归中序遍历二叉树
void MidOrder(BiTree Tree)
{
if(Tree)
{
MidOrder(Tree->LChild);
printf("%c",Tree->value);
MidOrder(Tree->RChild);
}
}

//递归后序遍历二叉树
void PostOrder(BiTree Tree)
{
if(Tree)
{
PostOrder(Tree->LChild);
PostOrder(Tree->RChild);
printf("%c",Tree->value);
}
}

//非递归前序遍历二叉树
void NPreOrder(BiTree Tree)
{
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
if(p->RChild)
Push(S,p->RChild);
printf("%c",p->value);
p = p->LChild;
}
else
p = Pop(S);
}
}

//非递归中序遍历二叉树
void NMidOrder(BiTree Tree)
{
//char ch;
BiTNode *p;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = Pop(S);
printf("%c",p->value);
p = p->RChild;
}
}
}

//非递归后序遍历二叉树
void NPostOrder(BiTree Tree)
{
BiTNode *p,*q = NULL;
S = InitLinkStack(S);
p = Tree;
while(p || count != 0)
{
if(p)
{
Push(S,p);
p = p->LChild;
}
else
{
p = S->link->pointer;
if(p->RChild == NULL || p->RChild == q)
{
p = Pop(S);
printf("%c",p->value);
q = p;
p = NULL;
}
else
{
//p = Pop(S);
p = p->RChild;
}
}
}
}
//初始化链栈
LinkStackNode *InitLinkStack(LinkStack top)
{
top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
return top;
}

//进栈操作
void Push(LinkStack top,BiTNode *p)
{
LinkStackNode *temp;
temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
if(temp)
{
temp->pointer = p;
temp->link = top->link;
top->link = temp;
count++;
}
}

//出栈操作
BiTNode * Pop(LinkStack top)
{
//char ch;
BiTNode *p;
LinkStackNode *temp;
p = (BiTNode *)malloc(sizeof(BiTNode));
temp = top->link;
if(temp)
{
top->link = temp->link;
p = temp->pointer;
free(temp);
count--;
}
return p;
}

Ⅱ 用c语言写二叉树，源代码。

二叉树是采用递归定义的，实现起来代码简洁（也许并不简单）。并且它在具体的计算机科学中有很重要的运用，是一种很重要的数据结构，二叉树有三种遍历和建立的方式。今天先学习一下它的建立和打印。
以下代码在Win-Tc1.9.1下编译通过。

#include <stdio.h>
#define ElemType char
//节点声明，数据域、左孩子指针、右孩子指针
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序建立二叉树
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#')T=NULL;
else{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = ch;
T->lchild = CreateBiTree();
T->rchild = CreateBiTree();
}
return T;//返回根节点
}
//先序遍历二叉树
void PreOrderTraverse(BiTree T){
if(T){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

//中序遍历
void InOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
printf("%c",T->data);
PreOrderTraverse(T->rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T){
if(T){
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
printf("%c",T->data);
}
}
void main(){
BiTree T;
T = CreateBiTree();//建立
PreOrderTraverse(T);//输出
getch();
}

Ⅲ 二叉树先序非递归遍历C语言算法

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度

typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义

typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定则宽义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s->base) exit(1); //抛出异常
s->top=s->base; //栈顶=栈尾 表示栈空
s->stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果栈满 追加开辟空间
{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1); //抛出异常
s->top=s->纯盯枯base+s->stacksize; //感觉这一句没用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //栈空 返回0
--s->top;*e=*(s->top); //做洞栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!='#'&&ch!='\n') /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根结点
CreateBiTree(&(*T)->lchild); //构造左子树
CreateBiTree(&(*T)->rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/

/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar('\n');
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar('\n');
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉树\n");
}

Ⅳ 求二叉树的非递归后序遍历的c语言代码

#include<iostream>
#include<stdio.h>
#define N 10
using namespace std;

char *a;

typedef struct NODE{
char data;
struct NODE *lch, *rch,*parent;
} *BINTREE,Node;

void visit(char data){

printf("%5c",data);
}

void preorder(BINTREE T){ // 先根序周游
BINTREE stack[50];
BINTREE p;
p=T;
int s=0;
if(p==NULL)return;
while(1)
{ visit(p->data);
while(p->lch!=NULL) {
stack[++s]=p;
p=p->lch;
visit(p->data); }
// cout<<" "扮正<<s;
while(1)
{ if((p=p->rch)!=NULL)
break;
if(s==0)
return;
p=stack[s--];
}
}
}

void inorder(BINTREE T)//中根序周游
{
Node *stack[100];
int top=0;
stack[0]=T;
while(top>0 ||stack[top]!=NULL)
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
}
if(top>0)
{
printf("%5c",stack[--top]->data );
stack[top]=stack[top]->rch ;
}
}

}

void posorder1(BINTREE T)//后根序周游
{
Node *stack[100];
int top=0;
int tag[100];
tag[0]=0;
stack[0]=T;
do
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
tag[top]=0;
}
while(tag[top-1]==1)
printf("%5c",stack[--top]->data );
if(top>0)
{
stack[top]=stack[top-1]->rch ;
tag[top-1]=1;
tag[top]=0;
}
} while(top!=0);

}

BINTREE Create(){//先根序树的建立
BINTREE T;
char ch;
cin>>ch;
cout<<" ch="<<ch<<endl;
if(ch=='#')
T=NULL;
else{
if(!(T=(BINTREE )malloc(sizeof(Node))))
printf("Error!");
T->data=ch;
T->缺缺裤lch=Create();
T->rch=Create();
}
return T;
}

void main(){

freopen("D:\\input.txt","r",stdin);
BINTREE T;
T=Create();
cout<<伏简"先根序遍历 ";
preorder(T);
cout<<endl;

cout<<"中根序遍历 ";
inorder(T);
cout<<endl;

cout<<"后根序遍历 ";
posorder1(T);
cout<<endl;
cout<<endl;

}
在D盘建立一个input.txt的文件，输入数的内容，输入顺序为先序根遍历的顺序，叶子节点的left和right用#代替即可。

Ⅳ 急求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;
}

Ⅵ 二叉树中序遍历的非递归算法

推荐这篇文章，把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html

Ⅶ 0xC0000005: 写入位置 0x00000000 时发生访问冲突 C语言 二叉树非递归遍历

你在主函数进行非递归调用时用到栈s，但s是一个指针，而你调用之前没有构造s，即s是一个野指针。并且察神栈的结构也定义错误, 正确的主缺没配函数应该如下伏指
void main(){
BiTree T;
struct su{
BiTNode *base;
BiTNode *top;
}*s;
T = CreateBiTree();//建立
s = (su*) malloc (sizeof(su)); //构造一个栈
s->base = s->top = (BiTNode*) malloc (X * sizeof(BiTNode)); //初始化为空栈,容量X自己去定
feidigui(s,T);
PreOrderTraverse(T);//输出
PostOrderTraverse(T);
getchar();
}

Ⅷ 如何用C实现二叉树的前中后序遍历非递归算法最好的是模块集成的

这里二叉树前中后序遍历非递归算法，详看代码，有详细解释，希望能帮助到你！

#include<stdio.h>
#include<malloc.h>
#include"header.h"

/**
*访问
*/
voidVisited(BinTree*BT){
printf("%d",BT->Data);
}

/**
*层序生成二叉树
*/
BinTree*CreateBinTree(){
BinTree_TypeData;
BinTree*BT=NULL,*T=NULL;
Queue*Q=NULL;
Q=InitQueue();/*生成一个队列*/
scanf("%d",&Data);/*建立第一个结点,即根节点*/
if(Data){/*分配结点单元,并将结点地址入队*/
BT=(BinTree*)malloc(sizeof(BinTree));
BT->Data=Data;
EnQueue(Q,BT);
}else{
returnNULL;/*若第一个数据就是0,则返回空树*/
}
while(!IsQueueEmpty(Q)){
T=DeQueue(Q);/*从队列中取出一结点地址*/
scanf("%d",&Data);/*读入T的左孩子*/
if(Data){/*分配新结点,作为出对结点左孩子*/
T->Left=(BinTree*)malloc(sizeof(BinTree));
T->Left->Data=Data;
EnQueue(Q,T->Left);/*新结点入队*/
}else{
T->Left=NULL;
}
scanf("%d",&Data);/*读入T的右孩子*/
if(Data){/*分配新结点,作为出对结点右孩子*/
T->Right=(BinTree*)malloc(sizeof(BinTree));
T->Right->Data=Data;
EnQueue(Q,T->Right);/*新结点入队*/
}else{
键首茄T->Right=NULL;
}
}/*结束while*/
returnBT;
}


/**
*遍历二叉树非递归算法
*/
/**
*前序遍历非递归算法
*/
voidPreOrderTraversal_Iter(BinTree*BT){
BinTree*T;
LinkStack*S=InitStack();/*生成一个堆栈*/
T=BT;
while(T||!IsStackEmpty(S)){
while(T)稿察{/*一直向左并访问沿途结点后压入堆栈S*/
Visited(T);
Push(S,T);
T=T->Left;
}
if(!IsStackEmpty(S)){
T=Pop(S);/*结点弹出堆栈*/
T=T->Right;/*转向右子树*/
}
}
}

/**
*中序遍历非递归算法
*/
voidInOrderTraversal_Iter(BinTree*BT){
BinTree*T;
LinkStack*S=InitStack();/*生成一个堆栈*/
T=BT;
while(T||!IsStackEmpty(S)){
while(T){/*一直向左并将沿途结点后压入堆栈S*/
Push(S,T);
T=T->Left;
}
if(!IsStackEmpty(S)){
T=Pop(S);/*结点弹出堆栈*/
Visited(T);
T=T->Right;/*转向右子树*/
}
}
}

/**
*后序遍历非递归算法一
*此思路来源于数据结构教程(李春葆主编)
*/
voidPostOrderTraversal_Iter1(BinTree*BT){
if(BT==NULL)
return;
BinTree*p,*T;
LinkStack*S=InitStack();
T=BT;
intflag=0;
do{
while(T){/*一直向左并将沿途结点后压入堆栈S*/
Push(S,T);
T=T->Left;
}
/*执行到此处,栈顶元素没有做孩子或左子树均已访问过*/
flag=1;/*表示T的左孩子已访问或为空*/
p=NULL;/*p指向栈顶结点的前一个已访问的结点*/
while芹颂(!IsStackEmpty(S)&&flag){
T=getTop(S);/*获取当前的栈顶元素,不是删除*/
/**
*若p=NULL,表示T的右孩子不存在,而左孩子不存在或已经被访问过,所以访问T;
*若p≠NULL,表示T的右孩子已访问(原因是p指向T的右子树中刚访问过的结点,而p是T的右孩子,
*p一定是T的右子树中后序序列的最后一个结点),所以可以访问T.
*/
if(p==T->Right){
Visited(T);/*访问*/
p=Pop(S);/*弹出刚访问的结点并将p指向刚访问的结点*/
}else{
T=T->Right;/*T指向T的右孩子*/
flag=0;/*表示T的右孩子尚未被访问过*/
}
}
}while(!IsStackEmpty(S));

}

/**
*后序遍历非递归算法二
*思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。
*如果p不存在左孩子和右孩子，则可以直接访问它；
*或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
*若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，
*左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
*(此思路来源于博客园海子!!!)
*/
voidPostOrderTraversal_Iter2(BinTree*BT){
if(!BT)
return;
BinTree*p,*cur;
LinkStack*S=InitStack();
p=NULL;
cur=NULL;
Push(S,BT);
while(!IsStackEmpty(S)){
cur=getTop(S);
if((!cur->Left&&!cur->Right)/*NULL==cur->Left&&NULL==cur->Right*/
||(p&&(p==cur->Left||p==cur->Right))){
Visited(cur);
p=Pop(S);
}else{
if(cur->Right){
Push(S,cur->Right);
}
if(cur->Left){
Push(S,cur->Left);
}
}
}
}

/**
*层序遍历
*/
voidLevelOrderTraversal(BinTree*BT){
BinTree*T;
T=BT;
if(!T){
return;
}
Queue*Q=InitQueue();/*生成一个队列*/
EnQueue(Q,T);/*根节点入队*/
while(!IsQueueEmpty(Q)){/*队列不为空,弹出一个元素*/
T=DeQueue(Q);
Visited(T);/*访问*/
if(T->Left)/*左子树不为空入队*/
EnQueue(Q,T->Left);
if(T->Right)/*右子树不为空入队*/
EnQueue(Q,T->Right);
}
}

/**
*访问叶子结点的递归算法
*/
voidgetOrderPrintLeaves(BinTree*BT){
if(BT){
if(!BT->Left&&!BT->Right){
Visited(BT);
}
getOrderPrintLeaves(BT->Left);
getOrderPrintLeaves(BT->Right);
}
}

/**
*访问叶子结点的非递归算法
*/
voidgetOrderPrintLeaves_Iter(BinTree*BT){
BinTree*T;
LinkStack*S=InitStack();
T=BT;
while(T||!IsStackEmpty(S)){
while(T){
Push(S,T);
T=T->Left;
}
if(!IsStackEmpty(S)){
T=Pop(S);
if(!T->Left&&!T->Right){/*当该结点的左子树和右子树都为空,访问*/
Visited(T);
}
T=T->Right;
}
}
}