# Data structure -- non recursive implementation of tree traversal

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.

Keywords: C++

Added by gdure on Tue, 31 Mar 2020 12:28:34 +0300