数据结构-树-二叉树遍历完整可执行代码(递归/非递归)

r囧r小猫 2022-09-18 03:53 85阅读 0赞

**数据结构-树-二叉树遍历完整可执行代码(递归/非递归)**

**mark：有篇博客写的不错，关于非递归算法描述很详细，先记录了。http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html**

#include <stdio.h>
    #include <stdlib.h>
    
    #define  MAXSIZE 20
    //二叉树结点的结构体表示形式
    typedef struct BitNode
    {
        char    data;
        struct BitNode* left,*right;
    }BitTree;
    
    //栈的结构体表示形式
    typedef struct stackelem
    {
        BitTree* a[MAXSIZE];
        int top;
    }Stack;
    
    //队列的结构体的表示形式
    typedef struct queueelem
    {
        BitTree* b[MAXSIZE];
        int front,rear;
    }Queue;
    
    //创建二叉树，利用递归的方法
    //按前序次序输入。 如 A # #(#表示空树)
    BitTree* Create()
    {
        char ch;
        scanf("%c",&ch);
        getchar();    //吃掉空格符
        if (ch=='#')
        {
            return NULL;
        }
        else
        {
            BitTree* btree=(BitTree*)malloc(sizeof(BitTree));
            if (NULL==btree)
            {
                return NULL;
            }
            btree->data=ch;
            btree->left=Create();
            btree->right=Create();
            return btree;
        }
    }
    
    //前序遍历，递归的方法
    void Preorder(BitTree* bt)
    {
        if (NULL!=bt)
        {
            printf("%c ",bt->data);
            Preorder(bt->left);
            Preorder(bt->right);
        }
    }
    
    //前序遍历的非递归实现
    /*
     思想：利用栈来实现；根结点进栈，之后栈非空，弹出，接着根节点的右结点进栈，之后，左节点进栈；接着，弹出栈顶元素（输出）,
     此结点的右结点进栈，之后左节点进栈，弹出栈顶元素（输出）...一直这样下去，直到栈为空。
     */
    void Preorder2(BitTree* bt)
    {
        BitTree* p;
        Stack st;
        st.top=-1;
        if (NULL==bt)
        {
            return;
        }
        else
        {
            st.top++;
            st.a[st.top]=bt;
            while (st.top!=-1)
            {
                p=st.a[st.top];
                st.top--;
                printf("%c ",p->data);
                if (p->right!=NULL)
                {
                    st.top++;
                    st.a[st.top]=p->right;
                }
                if (p->left!=NULL)
                {
                    st.top++;
                    st.a[st.top]=p->left;
                }
            }
        }
    }
    
    //中序遍历，递归实现
    void Inorder(BitTree* bt)
    {
        if (NULL!=bt)
        {
            Inorder(bt->left);
            printf("%c ",bt->data);
            Inorder(bt->right);
        }
    }
    
    //中序遍历，非递归实现
    /*
     思想：利用栈。从根节点开始，循环，只要有左子节点则进栈，直到左子节点为空。接着弹出栈顶输出，判断该结点是否有右子节点，
     若有则进栈，若没有继续弹栈。有右子节点的情况，判断该节点是否有左子节点，有则进栈，直到左子节点为空；若该右子节点没有
     左子节点，则弹栈；判断弹出的节点，是否有右子节点，若有则进栈，没有继续弹栈；接着又要判断刚进栈的这个节点，是否有左子节点，
     有则进栈，没有则继续弹栈。重复下去....
     栈空，是判定条件。
     */
    void Inorder2(BitTree* bt)
    {
        BitTree* p,*q;
        Stack st;
        st.top=-1;
        if (NULL==bt)
        {
            return;
        }
        else
        {
            while (bt!=NULL)
            {
                st.top++;
                st.a[st.top]=bt;
                bt=bt->left;
            }
            while (st.top!=-1)
            {
                p=st.a[st.top];
                st.top--;
                printf("%c ",p->data);
                while ( p->right!=NULL )
                {
                    st.top++;
                    st.a[st.top]=p->right;
                    q=p->right;
                    while (q->left!=NULL)
                    {
                        st.top++;
                        st.a[st.top]=q->left;
                        q=q->left;
                    }
                    break;
                }
            }
        }
    }
    
    //后序遍历，递归实现
    void Postorder(BitTree* bt)
    {
        if (bt!=NULL)
        {
            Postorder(bt->left);
            Postorder(bt->right);
            printf("%c ",bt->data);
        }
    }
    
    //后序遍历，非递归实现
    /*
     算法思想：利用栈来实现。从根结点开始，只要左子节点非空，则进栈，直到左子节点为空为止。取出栈顶元素（只是取，并非弹栈），判断
     1:取出的栈顶元素是否有右子节点，或者右子节点是否被访问过，若满足条件（无右子节点，或者右子节点被访问过），则输出该结点，
     同时弹栈，并且记录下该访问的节点。
     2:取出的栈顶元素，若有右子节点，且未被访问过，则指针继续移动到右子节点，重复一开始是否又左子节点的判断。
     */
    void Postorder2(BitTree* bt)
    {
        Stack st;
        st.top=-1;
        BitTree* t;
        do
        {
            while (bt!=NULL)
            {
                st.top++;
                st.a[st.top]=bt;
                bt=bt->left;
            }
            t=NULL;
            while (st.top!=-1)
            {
                bt=st.a[st.top];
                if (bt->right==t)  //t:表示为null，或者右子节点被访问过了。
                {
                    printf("%c ",bt->data);
                    st.top--;
                    t=bt;  //t记录下刚刚访问的节点
                }
                else
                {
                    bt=bt->right;
                    break;
                }
            }
        } while (st.top!=-1);
    }
    
    //求二叉树的高度，递归实现
    int Height(BitTree* bt)
    {
        int depth1,depth2;
        if (NULL==bt)
        {
            return 0;
        }
        else
        {
            depth1=Height(bt->left);
            depth2=Height(bt->right);
            if (depth1>depth2)
            {
                return (depth1+1);
            }
            else
            {
                return (depth2+1);
            }
        }
    }
    
    //层次遍历二叉树,用队列来实现
    void TraversalOfLevel(BitTree* bt)
    {
        Queue q;
        q.front=q.rear=0;
        if (bt!=NULL)
        {
            printf("%c ",bt->data);
        }
        q.b[q.front]=bt;
        q.rear=q.rear+1;
        while (q.front<q.rear)
        {
            bt=q.b[q.front];
            q.front=q.front+1;
            if (bt->left!=NULL)
            {
                printf("%c ",bt->left->data);
                q.b[q.rear]=bt->left;
                q.rear=q.rear+1;
            }
            if (bt->right!=NULL)
            {
                printf("%c ",bt->right->data);
                q.b[q.rear]=bt->right;
                q.rear=q.rear+1;
            }
        }
    }
    
    int main()
    {
        BitTree* btr=Create();
        printf("前序遍历：递归和非递归实现：\n");
        Preorder(btr);
        printf("\n");
        Preorder2(btr);
        printf("\n");
        printf("中序遍历：递归和非递归实现：\n");
        Inorder(btr);
        printf("\n");
        Inorder2(btr);
        printf("\n");
        printf("后序遍历：递归和非递归实现：\n");
        Postorder(btr);
        printf("\n");
        Postorder2(btr);
        printf("\n");
        printf("二叉树的高度：\n");
        int Hgt=Height(btr);
        printf("%d \n",Hgt);
        printf("层次遍历二叉树:\n");
        TraversalOfLevel(btr);
        printf("\n");
        return 0;
    }
    
    /*  测试数据：  
     d b a # # c # # f e # # g # #
     前序遍历：递归和非递归实现：
     d b a c f e g
     d b a c f e g
     中序遍历：递归和非递归实现：
     a b c d e f g
     a b c d e f g
     后序遍历：递归和非递归实现：
     a c b e g f d
     a c b e g f d
     二叉树的高度：
     3
     层次遍历二叉树:
     d b f a c e g
    
    */

**学习的路上，与君共勉。**