树的几种遍历

[Bob]

From：http://nongcunya.blog.hexun.com/6158707_d.html

//================================
#include "stdafx.h"

//
//#include <stdio.h>
//#include <iostream>

typedef int DataType;
typedef struct MyBinTree
{
DataType data;
MyBinTree* lchild,* rchild;
}MYBINTREE;

//liststack
typedef struct MyListStack
{
MyBinTree *TNode;
MyListStack *top;
}MYLISTSTACK, *LPMYLISTSTACK;

MYLISTSTACK* MyListStackInit()
{
MYLISTSTACK *Head;

Head = (MYLISTSTACK*) malloc (sizeof(MYLISTSTACK));
if(!Head)
{
printf(" the liststack malloc failed!\n");
return NULL;
}
Head->TNode = NULL;
Head->top = NULL;

return Head;
}

//push
void MyListStackPush(MYLISTSTACK *& Head,MyBinTree *Tnode)
{
if(!Head) {
printf("the liststack is null!\n");
return;
}
MYLISTSTACK * s,*p = Head;
s = (MYLISTSTACK*) malloc (sizeof(MYLISTSTACK));
if(!s)
{
printf(" the liststack malloc failed!\n");
return ;
}
s->TNode = Tnode;
s->top = Head;
Head = s;
}

//pop
void MyListStackPop(MYLISTSTACK *& Head,MyBinTree *& Tnode)
{
MYLISTSTACK* p = Head;
Tnode = Head->TNode;
Head = Head->top;
free(p);
}
int MyListStackIsempty(MYLISTSTACK * Head)
{
if(Head->TNode == NULL)
return -1;
else return 0;
}

void MyBinTreeInsert(MYBINTREE*& T, MYBINTREE* b)
{
if( T == NULL) T = b;
else if(T->data == b->data)
return;
else if(T->data < b->data)
MyBinTreeInsert(T->rchild,b);
else if (T->data > b->data)
MyBinTreeInsert(T->lchild,b);

}
void MyBinTreeCreate( MYBINTREE *& T)
{
MYBINTREE *s ;
DataType x;
do{
printf("pls input the node value\n");
scanf("%d",&x);

s = (MYBINTREE*) malloc (sizeof(MYBINTREE));
if(!s) return;

s->data = x;
s->lchild = NULL;
s->rchild = NULL;

MyBinTreeInsert(T,s);
}while(x != -1);
//strong advise inputting like this :7 5 9 6 4 10 8 -1
}

void MyBinTreeVisit( MYBINTREE * T)
{
if(T)
printf("%d ",T->data);
}
void MyBinTreePrint( MYBINTREE * T)
{
if( T != NULL)
{
printf("%d ",T->data);
if(T->lchild != NULL || T->rchild != NULL)
{
MyBinTreePrint(T->lchild);
MyBinTreePrint(T->rchild);
}
}
}

//preorder
void MyBinTreePreOrder(MYBINTREE * T)
{
if(T)
{
printf("%d ",T->data);
MyBinTreePreOrder(T->lchild);
MyBinTreePreOrder(T->rchild);
}
}

//preorder no recursion
void MyBinTreePreOrderNorec(MYBINTREE * T)
{
if(T)
{
MYLISTSTACK *Head;
Head = MyListStackInit();
if(!Head) return;

while( T != NULL || 0 == MyListStackIsempty(Head))
{
if( T != NULL)
{
printf("%d ",T->data);
MyListStackPush(Head,T);
T = T->lchild;
}
else
{
MyListStackPop(Head,T);
T = T->rchild;
}
}
free(Head);
}
}

// inorder
void MyBinTreeInOrder(MYBINTREE * T)
{
if(T)
{
MyBinTreeInOrder(T->lchild);
printf("%d ",T->data);
MyBinTreeInOrder(T->rchild);
}
}

//inorder no recursion
void MyBinTreeInOrderNorec(MYBINTREE * T)
{
if(T)
{
MYLISTSTACK *Head;
Head = MyListStackInit();
if(!Head) return;

while( T != NULL || 0 == MyListStackIsempty(Head))
{
int mm = MyListStackIsempty(Head);
if( T != NULL)
{

MyListStackPush(Head,T);
T = T->lchild;
}
else
{
MyListStackPop(Head,T);
printf("%d ",T->data);
T = T->rchild;
}
}
free(Head);
}
}

//postorder
void MyBinTreePostOrder(MYBINTREE * T)
{
if(T)
{
MyBinTreePostOrder(T->lchild);
MyBinTreePostOrder(T->rchild);
printf("%d ",T->data);
}
}

//postorder no recursion
void MyBinTreePostOrderNorec(MYBINTREE * T)
{//zzzzzzzzzzzz

/*
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;

typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;

void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;

do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}

while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}

if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec

*/
}

int _tmain(int argc, _TCHAR* argv[])
{
MYBINTREE *T = NULL;
MyBinTreeCreate(T);

MyBinTreePreOrder(T);
printf("\n");
MyBinTreePreOrderNorec(T);
printf("\n");
MyBinTreeInOrder(T);
printf("\n");
MyBinTreeInOrderNorec(T);
printf("\n");
MyBinTreePostOrder(T);
printf("\n");
MyBinTreePostOrderNorec(T);

return 0;
}

//==================================