非递归遍历二叉树

//  非递归遍历二叉树


#include <stdio.h>
#include <iostream>


using namespace std;

typedef struct TNode{
    int data;
    struct TNode *lchild, *rchild;
}TNode, *Tree;

typedef struct LinkNode{
    TNode *data;
    struct LinkNode *next;
}LinkNode, *Stack;


// 初始化
void init_data(Stack &S){
    S = (LinkNode *)malloc(sizeof(LinkNode));
    S->data = NULL;
    S->next = NULL;
}

// 入栈
bool set_data(Stack &S, TNode *value){
    LinkNode *p = S;

    if (p == NULL) {
        return false;
    }

    LinkNode *q = (LinkNode *)malloc(sizeof(LinkNode));
    q->data = value;
    q->next = p->next;
    p->next = q;
    
    return true;
}

// 查看栈顶元素
TNode * get_data(Stack S){
    if (S->next==NULL) {
        return NULL;
    }
    return S->next->data;
    
}

// 出栈
bool erase_data(Stack &S, TNode *&value){
    if (S->next==NULL) {
        return false;
    }
    LinkNode *p = S->next;
    S->next = p->next;
    value = p->data;
    free(p);
    return true;
}

// 打印
void print_data(Stack S){
    LinkNode *p = S->next;
    if (p == NULL) {
        return ;
    }
    while (p!=NULL) {
        cout << "element:" << p->data << endl;
        p = p->next;
    }
}

// 先序遍历
void pre_order(Tree &tree){
    Stack S;

    init_data(S);
    
    TNode *p = tree;
    int k = 100; //防止死循环，正式环境去掉
    TNode *q = NULL;//记录最新出栈的结点，用来检查是否已经访问过当前结点的右结点（树的特性）
    while ((p!=NULL||S->next!=NULL)&&k>0) {
        if (p!=NULL) {
            cout << "element:" << p->data << endl;
            set_data(S, p);
            p = p->lchild;
        }else{
            p = get_data(S);
            if (p->rchild!=NULL&&p->rchild!=q) {//不能重复走右边
                p = p->rchild;
            }else{
                erase_data(S, p);
                q = p;
                p = NULL;
                
            }
            
        }
        k--;
    }
}

// 中序遍历
void in_order(Tree &tree){
    Stack S;

    init_data(S);
    
    TNode *p = tree;
    int k = 100; //防止死循环，正式环境去掉
    TNode *q = NULL;//记录最新出栈的结点，用来检查是否已经访问过当前结点的右结点（树的特性）
    while ((p!=NULL||S->next!=NULL)&&k>0) {
        if (p!=NULL) {
            set_data(S, p);
            p = p->lchild;
        }else{
            p = get_data(S);
        
            if (p->rchild!=q||q==NULL) {
                cout << "element:" << p->data << endl;
            }
            if (p->rchild!=NULL&&p->rchild!=q) {//不能重复走右边
               
                p = p->rchild;
            }else{
                erase_data(S, p);
                q = p;
                p = NULL;
            }
            
        }
        k--;
    }
}
// 后序遍历
void post_order(Tree &tree){
    Stack S;

    init_data(S);
    
    TNode *p = tree;
    int k = 100; //防止死循环，正式环境去掉
    TNode *q = NULL;//记录最新出栈的结点，用来检查是否已经访问过当前结点的右结点（树的特性）
    while ((p!=NULL||S->next!=NULL)&&k>0) {
        if (p!=NULL) {
            set_data(S, p);
            p = p->lchild;
        }else{
            p = get_data(S);
            if (p->rchild!=NULL&&p->rchild!=q) {//不能重复走右边
                p = p->rchild;
            }else{
                erase_data(S, p);
                q = p;
                cout << "element:" << p->data << endl;
                p = NULL;
                
            }
        }
        k--;
    }
}

int main(){
    std::cout << "welcome, to my world!" << std::endl;
    Tree tree = NULL;//空指针
    
    cout << "size of:" << sizeof(tree) << endl;
    tree = (TNode *)malloc(sizeof(TNode));//根结点
    tree->data = 1;
    tree->lchild = NULL;
    tree->rchild = NULL;
   
    TNode *p = (TNode *)malloc(sizeof(TNode));//新增结点
    p->lchild = NULL;
    p->rchild = NULL;
    p->data = 2;
    // 如果父亲结点没有左孩子 插入左孩子
    tree->lchild = p;
    
    TNode *q1 = (TNode *)malloc(sizeof(TNode));//新增结点
    q1->lchild = NULL;
    q1->rchild = NULL;
    q1->data = 4;
  
    
    TNode *q = (TNode *)malloc(sizeof(TNode));//新增结点
    q->lchild = NULL;
    q->rchild = q1;
    q->data = 3;
    tree->rchild = q;
    
    cout << "先序遍历 pre_order:" << endl;
    pre_order(tree);
    cout << "中序遍历 in_order:" << endl;
    in_order(tree);
    cout << "后序遍历 post_order:" << endl;
    post_order(tree);
    return 0;
}

输出
welcome, to my world!
size of:8
先序遍历 pre_order:
element:1
element:2
element:3
element:4
中序遍历 in_order:
element:2
element:1
element:3
element:4
后序遍历 post_order:
element:2
element:4
element:3
element:1
Program ended with exit code: 0