回 帖 发 新 帖 刷新版面

主题:[讨论]二叉树的遍历


请高手帮忙,我只做出了二叉树的遍历算法,谁能帮我给出非递归的程序,还有层次遍历的程序...对于这几个我老是出错,调试了N久。。

/*======================================================================================================================*/

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
#define INFEASIBLE -1
struct tree   
{struct tree *left;
 int data;
 struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;

/*---------------------------------------------------------------------------------------------------------------------*/
/*                                         插入二叉树的节点                                                            */
/*---------------------------------------------------------------------------------------------------------------------*/
b_tree insert_node(b_tree root,int node)
{
    b_tree newnode;
    b_tree currentnode;
    b_tree parentnode;

    /*建立新节点的内存空间*/
    newnode=(b_tree) malloc (sizeof(treenode));

    newnode->data=node;
    newnode->right=NULL;
    newnode->left=NULL;

    if(root==NULL)
        return newnode;
    else
    {
        currentnode=root;
        while(currentnode!=NULL)
        {parentnode=currentnode;
        if (currentnode->data>node)
            currentnode=currentnode->left;
        else
            currentnode=currentnode->right;
        }
        if(parentnode->data>node)
            parentnode->left=newnode;
        else
            parentnode->right=newnode;
    }
    return root;
}
/*----------------------------------------------------------------------------------------------------------------------*/
/*                                             建立二叉树                                                               */
/*----------------------------------------------------------------------------------------------------------------------*/
b_tree create_btree(int *data,int len)
{
    b_tree root=NULL;
    int i;

    for(i=0;i<len;i++)
        root=insert_node(root,data[i]);
    return root;
}
/*---------------------------------------------------------------------------------------------------------------------*/
/*                                       二叉树前序的递归遍历                                                          */
/*---------------------------------------------------------------------------------------------------------------------*/
void preorder(b_tree point)
{
    if(point!=NULL)
    {
        printf("%d",point->data);
        preorder(point->left);
        preorder(point->right);
    }
}
/*-----------------------------------------中序递归遍历---------------------------------------------------------------*/
void inorder(b_tree point)
{
    if(point!=NULL)
    {
        inorder(point->left);
        printf("%d",point->data);
        inorder(point->right);
    }
}

/*-----------------------------------------后序递归遍历---------------------------------------------------------------*/
void postorder(b_tree point)
{
    if(point!=NULL)
    {
        postorder(point->left);
        postorder(point->right);
        printf("%d",point->data);
    }
}



/*=====================================================================================================================*/
/*                                   主程序                                                                            */
/*=====================================================================================================================*/
void main ()
{
    b_tree root=NULL;
    int i,index;
    int value;
    int nodelist[20];

    printf("\n Please input the elements of the bibary tree(Exit for 0):\n");
    index=0;
    /*---------------读取数值存到数组中--------------*/
    scanf("%d",&value);
    while(value!=0)
    {    nodelist[index]=value;
        index=index+1;
        scanf("%d",&value);
    }

    /*---------------建立二叉树-------------------------------------------------------------*/
    root=create_btree(nodelist,index);
    system("cls");
    
    int choice;
    
    for(;;)
    {    
    
                 printf("二叉树的遍历!");
                 printf("请你选择遍历的方式 :");
                 printf(" * 1 二叉树前序的递归遍");
                 printf("* 2 中序递归遍历");
                 printf(" * 3 后序递归遍历");
                
                
    scanf("%d",&choice);
    switch(choice)
    {
    case 1:
    {
        /*--------------递归前序遍历二叉树-------------------------------------------*/
     printf("\n the preorder traversal result is[ ");
     preorder(root);
     printf("]\n");
     break;
    };
    case 2:
    {    /*--------------递归中序遍历二叉树-------------------------------------------*/
        printf("\n the preorder traversal result is[ ");
        inorder(root);
        printf("]\n");
        
        break;
    }
    case 3:
    { /*--------------递归后序遍历二叉树-------------------------------------------*/
        printf("\n the preorder traversal result is[ ");
        postorder(root);
        printf("]\n");
        
    
        break;
    }
    case 4:
{     
        break;
    }
    case 5:
        break;
    }
    case 6:
    {         
    
        break;
    }
    case 0:
    {exit(0)
        break;
    }
    
    

    }
  }
}

回复列表 (共3个回复)

沙发

哥门,有没有JAVA版本的啊?

板凳

void broadFisrt(node*p)//层次
{
    if(p)
    {
        queue<node*> qu;
        node*q=0;
        qu.enqueue(p);
        while(!qu.empty())
        {
            q=qu.pop();
            cout<<q->data;
            if(q->left) qu.dequeue(q->left);
            if(q->right) qu.dequeue(q->right);
            
        }
    }
}



void preOrder(node*p)//先序
{
    if(p)
    {
        stack<node*> st;
        st.push(p);
        node*q=0;
        while(!st.empty())
        {
            q=st.pop();
            cout<<q->data;
            if(q->right) st.push(p->right);
            if(q->left) st.push(p->left);
        }
        
    }
}



void inOrder(node*p)//中序
{
    if(p)
    {
        stack<node*> st;
        node*q=p;
        while(q||!st.empty())
        {
            if(p) {st.push(q); q=q->left;}
            else
            {
                q=st.pop();
                cout<<q->data;
                q=q->right;
            }
        }
    }
}


template <class T>//后序
void postOrder(node *t)
 {
    Stack<node*>  s;
    node *p=t,*q =t;
    while(p!=0)
    {
        for(;p->left!=0;p=p->left)
        s.Add(p);
        while(p!=0&&(p->RightChild==0||p->RightChild==q)
        {
            visit(p);
            q =p;
            if(s.empty())
            return;
            s.Delete(p);
         }
        s.Add(p);
        p = p->RightChild;
    }
}

3 楼

写层次时,可以用一个队列
掌握好进对列和出队列的时机

我来回复

您尚未登录,请登录后再回复。点此登录或注册