二叉樹的非遞歸遍歷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;
}
}
}