要求:给定一个二叉树序列,要求以递归与非递归的形式先序输出。
递归的本质就是系统自动用系统工作栈来将参数入栈与出栈,所以递归化非递归就是程序员自己来控制参数的入栈与出栈,可用循环加自定义栈来控制。
代码如下:
#include<iostream> #include<stack> using namespace std; typedef struct BTNode { char ch; struct BTNode *lchild; struct BTNode *rchild; }BTNode,*pBTNode; void create_Bt(pBTNode &root)//用引用更加直观 { char ch=getchar(); if(ch==' ') root=NULL; else { root=new BTNode; root->ch=ch; create_Bt(root->lchild); create_Bt(root->rchild); } } //递归先序遍历 void pre(pBTNode root) { if(root!=NULL) { cout<<root->ch<<' '; pre(root->lchild); pre(root->rchild); } } //非递归先序遍历 void pre_(pBTNode root) { stack<pBTNode> s; while(root!=NULL||!s.empty())//递归化非递归关键用循环和自定义栈来控制递归的结束 { if(root!=NULL) { s.push(root); cout<<root->ch<<' '; root=root->lchild; } else { root=s.top(); s.pop(); root=root->rchild; } } } void main() { pBTNode root; cout<<"请输入一个二叉树序列"<<endl; create_Bt(root); pre(root); cout<<endl; pre_(root); }程序运行结果如下: