非递归形式实现二叉树 前序 中序 后序遍历
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
