Tree structure is an important nonlinear data structure. Tree is a finite set of n (n > = 0) nodes. In any non empty tree, there are and only

When n > 1, the remaining nodes can be divided into m (M > 0) disjoint finite sets T1,T2,...,Tm, each of which

The collection itself is a tree, and is called the root subtree. Therefore, the data structure of the tree is defined as:

#define ElemType char
typedef struct BinTreeNode
{
    ElemType data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
}BinTreeNode;

typedef struct BinTree
{
    BinTreeNode *root;
}BinTree;

Therefore, the non recursive implementation of traversing the tree structure in the pre order, middle order and post order has the following method statements:

void PreOrder(BinTree *t);
void PreOrder(BinTreeNode *t);
void InOrder(BinTree *t);
void InOrder(BinTreeNode *t);
void PostOrder(BinTree *t);
void PostOrder(BinTreeNode *t);

Then the methods declared above are implemented as follows:

#include<iostream>
#include<assert.h>
#include"Queue.h"
#include"Stack.h"
using namespace std;

#define ElemType char
typedef struct BinTreeNode
{
    ElemType data;
    BinTreeNode *leftChild;
    BinTreeNode *rightChild;
}BinTreeNode;

typedef struct BinTree
{
    BinTreeNode *root;
}BinTree;

void InitBinTree(BinTree *t);
void CreateBinTree(BinTree *t);
void CreateBinTree(BinTreeNode *&t);
void PreOrder(BinTree *t);
void PreOrder(BinTreeNode *t);
void InOrder(BinTree *t);
void InOrder(BinTreeNode *t);
void PostOrder(BinTree *t);
void PostOrder(BinTreeNode *t);

void InitBinTree(BinTree *t)
{
    t->root = NULL;
}

void CreateBinTree(BinTree *t)
{
    CreateBinTree(t->root);
}
void CreateBinTree(BinTreeNode *&t)
{
    ElemType item;
    cin>>item;
    if(item == '#')
        t = NULL;
    else
    {
        t = (BinTreeNode*)malloc(sizeof(BinTreeNode));
        assert(t != NULL);
        t->data = item;
        CreateBinTree(t->leftChild);
        CreateBinTree(t->rightChild);
    }
}

void PreOrder(BinTree *t)
{
    PreOrder(t->root);
}
void PreOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        PushStack(&st, t);
        BinTreeNode *p;
        while(!IsEmpty(&st))
        {
            p = GetTop(&st);
            PopStack(&st);
            cout<<p->data<<" ";
            if(p->rightChild != NULL)
                PushStack(&st,p->rightChild);
            if(p->leftChild != NULL)
                PushStack(&st, p->leftChild);
        }
    }
}

void InOrder(BinTree *t)
{
    InOrder(t->root);
}
void InOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        PushStack(&st, t);
        BinTreeNode *p;
        while(!IsEmpty(&st))
        {
            while(t->leftChild != NULL)
            {
                t = t->leftChild;
                PushStack(&st, t);
            }
            p = GetTop(&st);
            PopStack(&st);
            cout<<p->data<<" ";
        
            if(p->rightChild != NULL)
            {
                t = p->rightChild;
                PushStack(&st, t);
            }
        }
    }
}

void PostOrder(BinTree *t)
{
    PostOrder(t->root);
}
void PostOrder(BinTreeNode *t)
{
    if(t != NULL)
    {
        Stack st;
        InitStack(&st);
        StkNode sn;
        do
        {
            while(t != NULL)
            {
                sn.ptr = t;
                sn.tag = L;
                PushStack(&st, sn);
                t = t->leftChild;
            }
            bool flag = true;
            while(flag && !IsEmpty(&st))
            {
                sn = GetTop(&st);
                PopStack(&st);
                switch(sn.tag)
                {
                case L:
                    sn.tag = R;
                    PushStack(&st,sn);
                    flag = false;
                    t = sn.ptr->rightChild;
                    break;
                case R:
                    cout<<sn.ptr->data<<" ";
                    break;
                }
            }
        }while(!IsEmpty(&st));
    }
}

In the non recursive implementation of tree traversal, the data structure of stack is used, and the implementation of stack is in my previous article

It has also been realized.