数据结构和算法分析

二叉树非递归遍历 - 先序 中序 后序

2018-08-16  本文已影响2人  Co_zy

(数字建立二叉树)

#include <stdio.h>
#include <stdlib.h>
#define maxsize 100

typedef struct BTNode
{
    int data;
    struct BTNode *left;
    struct BTNode *right;
}BTNode;

//逐个输入先序遍历建立二叉树
void CreateBiTree(BTNode *&T)
{
    int c;
    scanf("%d",&c);
    if(c == -1)
        T = NULL;
    else
    {
        T = (BTNode *)malloc(sizeof(BTNode));
        CreateBiTree(T->left);
        T->data = c;
        CreateBiTree(T->right);
    }
}

int visit(int c)
{
    printf("%d ",c);
    return 1;
}
//非递归先序遍历
void preorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *stack[maxsize];
        int top = -1;
        BTNode *p;
        stack[++top] = bt;
        while(top!=-1)
        {
            p = stack[top--];
            visit(p->data);
            if(p->right!=NULL)
                stack[++top] = p->right;
            if(p->left != NULL)
                stack[++top] = p->left;
        }
    }
}
//非递归中序遍历
void inorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *stack[maxsize];
        int top = -1;
        BTNode *p;
        p = bt;
        while(top!=-1 || p!=NULL)
        {
            while(p!=NULL)
            {
                stack[++top] = p;
                p = p->left;
            }
            if(top!=-1)
            {
                p = stack[top--];
                visit(p->data);
                p = p->right;
            }
        }
    }
}

//非递归后序遍历
void postorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *stack1[maxsize];
        BTNode *stack2[maxsize];
        int top1 = -1;
        int top2 = -1;
        BTNode *p = NULL;
        stack1[++top1] = bt;
        while(top1 != -1)
        {
            p = stack1[top1--];
            stack2[++top2] = p;
            if(p->left != NULL)
                stack1[++top1] = p->left;
            if(p->right != NULL)
                stack1[++top1] = p->right;
        }

        while(top2 != -1)
        {
            p = stack2[top2--];
            visit(p->data);
        }

    }
}

int main()
{
    BTNode *T;
    CreateBiTree(T);
    preorderNonrecursion(T);
    printf("\n");
    inorderNonrecursion(T);
    printf("\n");
    postorderNonrecursion(T);
    printf("\n");
    return 0;
}

输入
1 2 3 -1 -1 5 -1 -1 4 -1 -1

输出 (分别是先序,中序,后序)
1 2 3 5 4
3 2 5 1 4
3 5 2 4 1

上一篇下一篇

猜你喜欢

热点阅读