//树的建立及三种遍历（递归实现）

主题：//树的建立及三种遍历（递归实现）

原上草根 [专家分：0] 发布于 2007-05-27 15:04:00

//树的建立及三种遍历；；（原上原创版）
#include  <iostream.h>
typedef  struct  tree{
                    int data;
        struct tree *lchild,*rchild;
                           }TREE;
TREE *createtree();
void  preorder(TREE *p);
void  inorder(TREE *p);
void  postorder(TREE *p);
void  main()
{

    TREE *node;
    node=new TREE;
    cout<<"按前序顺序开始建树 "<<endl<<"依次输入新建树的相关节点值:"<<endl;
    node=createtree();
    cout<<"前序遍历结果为:  "<<endl;
    preorder(node);
    cout<<"中序遍历结果为:  "<<endl;
    inorder(node);
    cout<<"后序遍历结果为:  "<<endl;
    postorder(node);
return;
}
//////////////建树
TREE *createtree()
{
int x;
TREE *p;
cin>>x;
if(x==0)  p=NULL;
else
{
  p=new TREE;
  p->data=x;
  p->lchild=createtree();
  p->rchild=createtree();
}
return  p;
}
///////////先序遍历
void preorder (TREE *p)
{
if(p!=NULL)
{
  cout<<p->data<<"  ";
  preorder(p->lchild);
  preorder(p->rchild);
}
return;
}
//////////中序遍历
void inorder (TREE *p)
{
if(p!=NULL)
{
  inorder(p->lchild);
        cout<<p->data<<"  ";
  inorder(p->rchild);
}
return;
}
/////////////后序遍历
void postorder (TREE *p)
{
if(p!=NULL)
{
  postorder(p->lchild);
  postorder(p->rchild);
        cout<<p->data<<"  ";
}
return;
}

此帖转自:[url]http://www.programfan.com/team/team.asp?team_id=1346[/url]

#include <stdlib.h>
#include <stdio.h>

#define MAX_STACK_SIZE  ( 500 )

struct bintree;
typedef struct bintree* BinTree;
struct bintree
{
        char data;
        BinTree left;
        BinTree right;
};

void Preorder( Bintree T )  //先序遍历
{
        typedef BinTree StackElem;
        StackElem  stack[MAX_STACK_SIZE];
        StackElem* top = stack;

        while ( stack != top || NULL != T )
        {
                while ( NULL != T )
                {
                        *top = T->right;
                        ++top;
                        printf( "%c", T->data );
                        T = T->left;
                }
                --top;
                T = *top;
        }
        return;
}

void Inorder( Bintree T )  //中序遍历
{
        typedef BinTree StackElem;
        StackElem  stack[MAX_STACK_SIZE];
        StackElem* top = stack;

        while ( stack != top || NULL != T )
        {
                while ( NULL != T )
                {
                        *top = T;
                        ++top;
                        T = T->left;
                }
                --top;
                T = *top;
                printf( "%c", T->data );
                T = T->right;
        }
        return;
}

void Post( BinTree T )  //后序遍历
{
        BinTree p = NULL;
        typedef BinTree StackElem;
        StackElem  stack[MAX_STACK_SIZE];
        StackElem* top = stack;

        while ( ( stack != top ) || ( T != NULL ) )
        {
                while ( T != NULL )
                {
                        *++top = T;
                        T = T->left;
                }
                T = *top;
                if ( p == T->right || NULL == T->right )
                {
                        printf( "%c", T->data );
                        p = T;
                        --top;
                        T = NULL; /* get T from the top of stack by next while */
                }
                else
                {
                        T = T->right;
                }
        }
        return;
}

主题：//树的建立及三种遍历（递归实现）

回复列表（共1个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：//树的建立及三种遍历（递归实现）

回复列表 （共1个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共1个回复）