二叉树--进阶

非递归形式实现二叉树 前序 中序 后序遍历

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