（1） 假设二叉树采用链接存储方式存储，分别编写一个二叉树先序遍历的递归算法和非递归算法。
代码：
#include<iostream> using namespace std; const int StackSize=100; template<class T> struct BiNode { T data; BiNode<T> *lchild,*rchild; }; template<class T> class BiTree { public: BiTree() { root=Creat(root); } ~BiTree() { Release(root); } void PreOrderWithRecursion() { PreOrderWithRecursion(root); } void PreOrderWithoutRecursion() { PreOrderWithoutRecursion(root); } private: BiNode<T> *root; BiNode<T> *Creat(BiNode<T> *bt); void Release(BiNode<T> *bt); void PreOrderWithRecursion(BiNode<T> *bt); void PreOrderWithoutRecursion(BiNode<T> *bt); }; template<class T> BiNode<T> *BiTree<T>::Creat(BiNode<T> *bt) { static int i=0; char node[] = {'A','B','#','D','#','#','C','#','#'}; T ch; ch=node[i]; i++; if(ch=='#') { bt=NULL; } else { bt=new BiNode<T>; bt->data=ch; bt->lchild=Creat(bt->lchild); bt->rchild=Creat(bt->rchild); } return bt; } template<class T> void BiTree<T>::Release(BiNode<T> *bt) { if(bt!= NULL) { Release(bt->lchild); Release(bt->rchild); delete bt; } } template<class T> void BiTree<T>::PreOrderWithRecursion(BiNode<T> *bt) { if(bt==NULL) return; else { cout<<bt->data<<" "; PreOrderWithRecursion(bt->lchild); PreOrderWithRecursion(bt->rchild); } } template<class T> void BiTree<T>::PreOrderWithoutRecursion(BiNode<T> *bt) { BiNode<T> *s[100]; int top=-1; while(bt!=NULL || top!=-1) { while(bt!=NULL) { cout<<bt->data<<" "; s[++top]=bt; bt=bt->lchild; } if(top!=-1) { bt=s[top--]; bt=bt->rchild; } } } int main() { BiTree<char> BT; cout<<"先序递归遍历为："; BT.PreOrderWithRecursion(); cout<<endl; cout<<"先序非递归遍历为："; BT.PreOrderWithoutRecursion(); return 0; }