树3-二叉树非递归遍历(栈)

拷贝根结点, 初始值FALSE, 入栈

弹出, 如果是FALSE,

将根节点将更新为TRUE, 其子结点(初始值FALSE)一并入栈

[A,B,C] (前序遍历, 入栈顺序:C,B,A 输出顺序: A,B,C)

再弹出, 如果是TRUE则输出

引入链式栈头文件

#include "linkedStack.h"

链式栈头文件

#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H
#include <stdlib.h>

//链式栈的结点
typedef struct LinkNode{
    struct LinkNode *next;
} LinkNode;

//链式栈
typedef struct LinkStack{
    LinkNode head; //链式栈的头结点
    int size; //栈的元素数量
} LinkStack;

//初始化
LinkStack* Init_LinkStack(){
    LinkStack *stack = (LinkStack*)malloc(sizeof(LinkStack));
    stack->head.next = NULL;
    stack->size=0;
    return stack;
};

//入栈(头插法)
void Push_LinkStack(LinkStack* stack, LinkNode *data){
    if(stack==NULL) return;
    if(data==NULL) return;
    //插入结点的后继指向第一个结点
    data->next = stack->head.next;
    //头结点的后继指向插入结点
    stack->head.next = data;
    //链式栈长度++
    stack->size++;
};

//返回栈顶元素
LinkNode* Top_LinkStack(LinkStack* stack){
    if(stack==NULL) return NULL;
    if(stack->size==0) return NULL;
    return stack->head.next;
};

//出栈
void Pop_LinkStack(LinkStack* stack){
    if(stack==NULL) return;
    if(stack->size==0) return;    
    //第一个有效结点
    LinkNode *pNext = stack->head.next;
    //删除第一个有效结点(跳过)
    stack->head.next =  pNext->next;
    //链式栈长度--
    stack->size--;
};

//返回栈元素个数
int Size_LinkStack(LinkStack* stack){
    if(stack==NULL) return -1;
    return stack->size;
};

//清空
void Clear_LinkStack(LinkStack* stack){
    if(stack==NULL) return;
    stack->head.next = NULL;
    stack->size = 0;
};

//销毁
void FreeSpace_LinkStack(LinkStack*

二叉树结点

//二叉树结点
typedef struct BinaryNode{
    char ch;
    struct BinaryNode *lChild;
    struct BinaryNode *rChild;
} BinaryNode;

链式栈结点

//栈结点
typedef struct BiTreeStackNode{
    LinkNode node; //支持链式栈的必要部分  (为什么不是指针?)
    BinaryNode* root; //二叉树结点
    int flag; 
} BiTreeStackNode;

创建栈中的结点

//创建栈中的结点
BiTreeStackNode* CreateBiTreeStackNode(BinaryNode *node, int flag){
    //将二叉树结点作为元素压入栈中
    BiTreeStackNode *newNode = (BiTreeStackNode*)malloc(sizeof(BiTreeStackNode));
    newNode->root = node;
    newNode->flag = flag;
    return newNode;
}

非递归遍历

//非递归遍历
void NonRecursion(BinaryNode* root){
    //创建栈 
    LinkStack *stack = Init_LinkStack();
    //把根节点扔进栈中(初始化为FALSE)
    Push_LinkStack(stack, (LinkNode*)CreateBiTreeStackNode(root, MY_FALSE));
    //栈非空时, 遍历
    while(Size_LinkStack(stack)>0){
        //取出栈顶元素
        BiTreeStackNode *node = (BiTreeStackNode*)Top_LinkStack(stack);
        //弹出栈顶元素
        Pop_LinkStack(stack);
        //是否弹出的结点是否为空, 为空则跳过这次循环
        if(node->root==NULL){
            continue;
        }
        //判断结点的flag, 如果true, 输出
        if(node->flag==MY_TRUE){
            cout << node->root->ch << " ";
        }else{// false, 更新根节点flag+左右子树压栈
            //当前结点的右结点入栈
            Push_LinkStack(stack, (LinkNode*)CreateBiTreeStackNode(node->root->rChild, MY_FALSE));
            //当前结点的左结点入栈
            Push_LinkStack(stack, (LinkNode*)CreateBiTreeStackNode(node->root->lChild, MY_FALSE));
            //根节点更新为TRUE
            node->flag = MY_TRUE;
            Push_LinkStack(stack, (LinkNode*)node);
        }
    }
    cout << endl;
}

释放二叉树

//释放二叉树
void FreeSpaceBinaryTree(BinaryNode* root){
    if(root==NULL) return;
    //释放左子树
    FreeSpaceBinaryTree(root->lChild);
    //释放右子树 
    FreeSpaceBinaryTree(root->rChild);
    //释放当前结点
    free(root);
}

创建二叉树

void CreateBinaryTree(){
    //创建结点
    BinaryNode node1 = {'A',NULL,NULL};
    BinaryNode node2 = {'B',NULL,NULL};
    BinaryNode node3 = {'C',NULL,NULL};
    BinaryNode node4 = {'D',NULL,NULL};
    BinaryNode node5 = {'E',NULL,NULL};
    BinaryNode node6 = {'F',NULL,NULL};
    BinaryNode node7 = {'G',NULL,NULL};
    BinaryNode node8 = {'H',NULL,NULL};
    //建立结点关系
    node1.lChild = &node2;
    node2.rChild = &node3;
    node3.lChild = &node4;
    node3.rChild = &node5;
    node1.rChild = &node6;
    node6.rChild = &node7;
    node7.rChild = &node8;

    //二叉树非递归输出 
    NonRecursion(&node1);

    FreeSpaceBinaryTree(&node1);
}

测试

int main(){
    CreateBinaryTree();
    cout << endl;

    system("pause");
    return 0;
}