用栈和递归写的就不用贴过来了，那个我已经知道了，现在我只要不用栈实现的的！
类似于这样的：
void preorder(BiTree T)//先序遍历
{
BiTree s[100];
int top=0;
while(T||top)
{
while(T)
{
s[++top]=T;
putchar(s[top]->data);
T=T->lchild;
}
if(top)
{
T=s[top--]->rchild;
}
}
}
斯蒂芬大帝浏览 205回答 2
2回答
-
SMILET
以下是我写的二叉树的头文件,有你想要的(不失一般性,我用的是模板).里面有非递归后序遍历 .栈和队列的头文件也在.用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 << "请输入数据(-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 分别将各个头文件的内容拷到相应的地方. 新建C++ Source file 将main函数的内容拷入cpp文件. 运行时如输入1,2,4,-1,-1,5,-1,-1,3,-1,-1 相应的遍历结果会出现. -
智慧大石
非递归实现后续遍历二叉树，此程序已调试成功：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/*若第二次出栈，则输出该节点*/{printf("%c",sq.node->data);p=NULL;}}}}
随时随地看视频慕课网APP
相关分类
C++
数据结构