TA貢獻1796條經(jīng)驗 獲得超4個贊
以下是我寫的二叉樹的頭文件,有你想要的(不失一般性,我用的是模板).里面有非遞歸后序遍歷 .棧和隊列的頭文件也在.用main()舉了一個例子,自己看吧.
//****************BiTree.h
#ifndef B_I_T_R_E_E
#define B_I_T_R_E_E
#include <iostream>
//#include <conio.h>
#include "stack.h"
#include "Lqueue.h"
using namespace std;
template <class TElemType>
struct BiTNode{
TElemType data;
BiTNode<TElemType> *lchild,*rchild;
};
template <class TElemType>
class BiTree
{
public:
void CreateBiTree(BiTNode<TElemType> *&T);
void PreOrderTraverse(BiTNode<TElemType> *T);
void InOrderTraverse(BiTNode<TElemType> *T);
void PostOrderTraverse(BiTNode<TElemType> *T);
void LevelOrderTraverse(BiTNode<TElemType> *T);
};
template <class TElemType>
void BiTree<TElemType>::CreateBiTree(BiTNode<TElemType> *&T)
{
TElemType ch;
cout << "請輸入數(shù)據(jù)(-1表示空(非字符型)):" << endl;
cin >> ch;
if(ch == -1) T = NULL;
else
{
if(!(T = (BiTNode<TElemType> *)malloc(sizeof(BiTNode<TElemType>)))) exit(0);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
template <class TElemType>
//遞歸先序遍歷
void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
cout << T->data << endl;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
} //PreOrderTraverse
/*非遞歸先序遍歷
void BiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType> *T)
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
cout << p->data << endl;
p = p->lchild;
}
else
{
S.Pop(p);
p = p->rchild;
}
}
S.DestroyStack();
} */
//遞歸中序遍歷
template <class TElemType>
void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout << T->data << endl;
InOrderTraverse(T->rchild);
}
}
//非遞歸中序遍歷
/*void BiTree<TElemType>::InOrderTraverse(BiTNode<TElemType> *T)
{
BiTNode<TElemType> * p = T;
stack<BiTNode<TElemType> *> S;
S.InitStack();
while(p || !S.StackEmpty())
{
if(p)
{
S.Push(p);
p = p->lchild;
}
else
{
S.Pop(p);
cout << p->data << endl;
p = p->rchild;
}
}
S.DestroyStack();
} */
//遞歸后序遍歷
template <class TElemType>
void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout << T->data << endl;
}
}
//非遞歸后序遍歷
/*void BiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType> *T)
{
BiTNode<TElemType> * p = T;
BiTNode<TElemType> * q = NULL;
stack<BiTNode<TElemType> *> S;
S.InitStack();
S.Push(p);
p = p->lchild;
while(!S.StackEmpty())
{
if(p)
{S.Push(p);p = p->lchild;}
else
{
S.GetTop(p);
p = p->rchild;
if(!p)
{
S.Pop(p);
cout << p->data << endl;
S.GetTop(q);
while(q && p == q->rchild)
{
S.Pop(p);
cout << p->data << endl;
S.GetTop(q);
//if(q == NULL) break;
}
if(q)
{
S.GetTop(q);
p = q->rchild;
}
}
}
}
S.DestroyStack();
} */
//非遞歸層次遍歷
template <class TElemType>
void BiTree<TElemType>::LevelOrderTraverse(BiTNode<TElemType> *T)
{
Lqueue<BiTNode<TElemType> *> que;
que.InitQueue();
if(T) que.EnQueue(T);
while(!que.QueueEmpty())
{
que.GetHead(T);
if(T->lchild) que.EnQueue(T->lchild);
if(T->rchild) que.EnQueue(T->rchild);
que.DeQueue(T);
cout << T->data << endl;
}
que.DestroyQueue();
}
#endif
//**************BiTree.h
//****Lqueue.h
#ifndef _LQUEUE_H
#define _LQUEUE_H
#define MAXQSIZE 100
typedef int Status;
template <class QElemType>
class Lqueue
{
public:
void InitQueue();
void DestroyQueue();
void ClearQueue();
Status QueueEmpty();
Status QueueLength();
void GetHead(QElemType & e);
void EnQueue(QElemType e);
void DeQueue(QElemType & e);
private:
struct SqQueue
{
QElemType * base;
int front;
int rear;
};
SqQueue Q;
};
//********Lqueue.cpp********
template <class QElemType>
void Lqueue<QElemType>::InitQueue()
{
Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
if(!Q.base) exit(0);
Q.front = Q.rear = 0;
}
template <class QElemType>
void Lqueue<QElemType>::DestroyQueue()
{
free(Q.base);
}
template <class QElemType>
void Lqueue<QElemType>::ClearQueue()
{
Q.front = Q.rear = 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueEmpty()
{
if(Q.front == Q.rear) return 1;
return 0;
}
template <class QElemType>
Status Lqueue<QElemType>::QueueLength()
{
return (Q.rear - Q.front + MAXQSIZE)%MAXQSIZE;
}
template <class QElemType>
void Lqueue<QElemType>::GetHead(QElemType & e)
{
if(Q.front == Q.rear) e = NULL;
else
{
e = Q.base[Q.front];
}
}
template <class QElemType>
void Lqueue<QElemType>::EnQueue(QElemType e)
{
if((Q.rear + 1)%MAXQSIZE == Q.front) cout << "ERROR" << endl;
else
{
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1)%MAXQSIZE;
}
}
template <class QElemType>
void Lqueue<QElemType>::DeQueue(QElemType & e)
{
if(Q.front == Q.rear) cout << "ERROR" << endl;
else
{
e = Q.base[Q.front];
Q.front = (Q.front + 1)%MAXQSIZE;
}
}
//******************Lqueue.cpp***************
#endif //*****Lqueue.h********
//*****stack.h
#ifndef _STACK_H
#define _STACK_H
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
template<class QElemType>
class stack
{
public:
void InitStack();
void DestroyStack();
void ClearStack();
Status StackEmpty();
Status StackLength();
void GetTop(QElemType & e);
void Push(QElemType e);
void Pop(QElemType & e);
private:
struct SqStack{
QElemType *base;
QElemType *top;
int stacksize;
}S;
};
//******stack.cpp------
template<class QElemType>
void stack<QElemType>::InitStack()
{
S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
template <class QElemType>
void stack<QElemType>::DestroyStack()
{
free(S.base);
}
template <class QElemType>
void stack<QElemType>::ClearStack()
{
S.top = S.base;
}
template <class QElemType>
Status stack<QElemType>::StackEmpty()
{
if(S.top == S.base) return 1;
else return 0;
}
template <class QElemType>
Status stack<QElemType>::StackLength()
{
return (S.top - S.base);
}
template <class QElemType>
void stack<QElemType>::GetTop(QElemType & e)
{
if(S.top != S.base)
e = *(S.top - 1);
else e = NULL;
}
template <class QElemType>
void stack<QElemType>::Push(QElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
template <class QElemType>
void stack<QElemType>::Pop(QElemType & e)
{
if(S.top == S.base) e = NULL;
else
e = * --S.top;
}
//**********stack.cpp
#endif //stack.h ****
//#include <iostream>
#include "BiTree.h"
//#include "stack.h"
//#include "Lqueue.h"
//using namespace std;
int main()
{
BiTree<int> tree;
BiTNode<int> *T = NULL;
tree.CreateBiTree(T);
tree.InOrderTraverse(T);
tree.PreOrderTraverse(T);
tree.PostOrderTraverse(T);
tree.LevelOrderTraverse(T);
return 0;
}
新建3個頭文件stack.h,Lqueue.h,BiTree.h
分別將各個頭文件的內(nèi)容拷到相應的地方.
新建C++ Source file
將main函數(shù)的內(nèi)容拷入cpp文件.
運行時如輸入1,2,4,-1,-1,5,-1,-1,3,-1,-1
相應的遍歷結(jié)果會出現(xiàn).
TA貢獻1946條經(jīng)驗 獲得超3個贊
非遞歸實現(xiàn)后續(xù)遍歷二叉樹，此程序已調(diào)試成功：
void postorder(BTree T)
{
DataType s[100],sq;
BTree p=T;
int top=-1;
while(p||top!=-1)
{
while(p)
{
top++;
sq.flag=0;
sq.node=p;
s[top]=sq;
p=p->lchild;
}
if(top!=-1)
{
sq=s[top];
p=sq.node;
top--;
if(sq.flag==0)
{
sq.flag=1;
top++;
s[top]=sq;
p=p->rchild;
}
else/*若第二次出棧，則輸出該節(jié)點*/
{
printf("%c",sq.node->data);
p=NULL;
}
}
}
}
舉報