二叉树--进阶

作者: 修夏之夏i | 来源:发表于2018-08-27 15:39 被阅读2次
    非递归形式实现二叉树 前序 中序 后序遍历

    Stack.h

    #define _CRT_SECURE_N0_WARNINGS 1
    
    #include <assert.h>
    
    struct BTreeNode;   // 结构体声明
    
    typedef struct BTreeNode * StackDataType;
    
    #define MAX_SIZE    (100)
    
    typedef struct Stack {
        StackDataType   array[MAX_SIZE];
        int             top;    // 表示当前个数
    }   Stack;
    
    void StackInit(Stack *pStack)
    {
        pStack->top = 0;
    }
    
    void StackDestroy(Stack *pStack)
    {
        pStack->top = 0;
    }
    
    void StackPush(Stack *pStack, StackDataType data)
    {
        assert(pStack->top < MAX_SIZE);
    
        pStack->array[pStack->top++] = data;
    }
    
    void StackPop(Stack *pStack)
    {
        assert(pStack->top > 0);
    
        pStack->top--;
    }
    
    StackDataType StackTop(const Stack *pStack)
    {
        assert(pStack->top > 0);
    
        return pStack->array[pStack->top - 1];
    }
    
    int StackSize(const Stack *pStack)
    {
        return pStack->top;
    }
    
    int StackFull(const Stack *pStack)
    {
        return pStack->top >= MAX_SIZE;
    }
    
    int StackEmpty(const Stack *pStack)
    {
        return pStack->top <= 0;
    }
    

    BinaryTree2.0.h

    #define _CRT_SECURE_N0_WARNINGS 1
    
    #pragma once
    
    #include "Stack.h"
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    typedef int TreeDataType;
    
    typedef struct BTreeNode{
        TreeDataType data;
        struct BTreeNode* left;
        struct BTreeNode* right;
    }BTreeNode;
    
    
    
    BTreeNode* CreateNode(int data)
    {
        BTreeNode* node = (BTreeNode *)malloc(sizeof(BTreeNode));
        node->data = data;
        node->left = node->right = NULL;
    
        return node;
    }
    
    //构造二叉树
    //返回值:1 二叉树的根节点 2 创建树过程中,使用的字符个数
    BTreeNode* CreateTree(int preOrder[], int size, int* pUsedSize)
    {
        //空树
        if (size <= 0)
        {
            *pUsedSize = 0;
            return NULL;
        }
    
        int leftUse, rightUse;
        int rootValue = preOrder[0];
    
        //一颗空树
        if (rootValue == -1)
        {
            *pUsedSize = 1;
            return NULL;
        }
    
        BTreeNode* root = CreateNode(rootValue);
    
        root->left = CreateTree(preOrder + 1, size - 1, &leftUse);
        root->right = CreateTree(preOrder + 1 + leftUse, size - 1 - leftUse, &rightUse);
    
        //使用字符个数 = 根节点 + 左子树 + 右子树 = 1 + leftused + rightused;
        *pUsedSize = 1 + leftUse + rightUse;
    
        return root;
    
    }
    
    //非递归实现 前序 中序 后序遍历
    
    //前序
    
    void PreOrder(BTreeNode* root)
    {
        Stack stack;
        StackInit(&stack);
        BTreeNode *cur, *top;
        cur = root;
    
        while (cur != NULL || !StackEmpty(&stack))
        {
            while (cur != NULL)
            {
                printf("%d ", cur->data);
                // 栈里保存的是 右子树没有遍历过的结点
                StackPush(&stack, cur);
                cur=cur->left;
            }
            // top 的左子树 和 根已经遍历过了
            top = StackTop(&stack);
            StackPop(&stack);
    
            // 需要进行 top 是空的判定么?
            cur = top->right;
        }
    }
    
    //中序
    void InOrder(BTreeNode *root)
    {
        Stack stack;
        StackInit(&stack);
        BTreeNode *cur, *top;
        cur = root;
        while (cur != NULL || !StackEmpty(&stack))
        {
            while (cur != NULL)
            {
                StackPush(&stack, cur);
                cur = cur->left;
            } 
            top = StackTop(&stack);
            StackPop(&stack);
            printf("%d ", top->data);
    
            // 需要进行 top 是空的判定么?
            // 利用子问题的思想去遍历 top 右子树
            cur = top->right;
        }
    }
    
    void PostOrder(BTreeNode *root)
    {
        Stack stack;
        StackInit(&stack);
        BTreeNode *cur, *top;
        BTreeNode *last = NULL;
        cur = root;
        while (cur != NULL || !StackEmpty(&stack))
        {
            while (cur != NULL)
            {
                StackPush(&stack, cur);
                cur = cur->left;
            }
            top = StackTop(&stack);
            if (top->right == NULL || top->right == last) {
                // 如果右子树被遍历过了
                StackPop(&stack);
                printf("%d ", top->data);
    
                // 记录这个被遍历的结点
                last = top;
            }
            else {
                // 如果右子树没有被遍历过
                cur = top->right;
            }
        }
    }
    
    
    void Test()
    {
        int preOrder[] = { 1, 2, 3, -1, 4, 5, -1, -1, -1, 6, -1, -1, 7, 8, -1, -1, 9, -1, 10 };
        //int preOrder[] = { 1, 2, 4, -1, -1, -1, 3 };
        int size = sizeof(preOrder) / sizeof(int);
        int usedSize;
    
        BTreeNode *root = CreateTree(preOrder, size, &usedSize);
    
        PreOrder(root); printf("\n");
        InOrder(root); printf("\n");
        PostOrder(root); printf("\n");
    }
    

    Main.c

    #define _CRT_SECURE_N0_WARNINGS 1
    #include "BinaryTree2.0.h"
    
    int main()
    {
        Test();
    }
    
    测试: 二叉树——二叉树.png
    结果: 非递归前中后序遍历.png

    相关文章

      网友评论

        本文标题:二叉树--进阶

        本文链接:https://www.haomeiwen.com/subject/atqtwftx.html