/*二叉树的各种遍历，，先，中，后，层次，递归与非递归。*/#include <iostream>#include <stack>#include <queue>using namespace std;typedef struct Bi_Node{char data;struct Bi_Node *lchild,*rchild;}Bit_Node,*Bit_Tree;/*因为你的BiTree类型本身就是指向结构体的指针类型 所以在传递参数的过程中不会发生深拷贝 如果你传递一个对象参数 而且这个对象里面还有指针如果不加引用就会发生浅拷贝 但是这样发生析构的时候就会使两个指针指向同一块内存 所以必须自己写拷贝构造函数实现深拷贝 但是如果加上引用他就不会去调用拷贝构造函数去构造临时对象 而是直接引用了你的实参对象 所以类里面有指针也不会崩掉*/void creat_node(Bit_Tree &T) //不加&，确实没有对指针赋值，从而成为野指针{char data;cin>>data;if (data == '#'){T = NULL;}else{T = (Bit_Tree)malloc(sizeof(Bi_Node));T->data = data;creat_node(T->lchild);creat_node(T->rchild);}}void print_node(Bit_Tree T){if (T->data != '#'){cout<<T->data<<" ";}}void pref_order(Bit_Tree T) //先序遍历 递归 根-左-右{if (T != NULL){print_node(T);pref_order(T->lchild);pref_order(T->rchild);}}void _pref_order(Bit_Tree T) //先序遍历 非递归 {stack<Bit_Tree> s;Bit_Tree p = T;while(p || !s.empty()){if (p != NULL){s.push(p);cout<<p->data<<" ";p = p->lchild;}else{p=s.top();s.pop();p = p->rchild;}}}void in_order(Bit_Tree T) //中序遍历 递归 左-根-右{if (T != NULL){in_order(T->lchild);print_node(T);in_order(T->rchild);}}void _in_order(Bit_Tree T) //中序遍历 非递归 {stack<Bit_Tree> s;Bit_Tree p = T;while(p || !s.empty()){if (p != NULL){s.push(p);//cout<<p->data<<" ";p = p->lchild;}else{p=s.top();cout<<p->data<<" ";s.pop();p = p->rchild;}}}void post_order(Bit_Tree T) //后序遍历 递归 左-右-根{if (T != NULL){post_order(T->lchild);post_order(T->rchild);print_node(T);}}typedef struct Bit_Node_Post{char tag;Bit_Tree bit_tree;}*_Bit_Node_Post;void _post_order(Bit_Tree T) //后序遍历 非递归 {stack<_Bit_Node_Post> s;Bit_Tree p = T;_Bit_Node_Post bt;while(p || !s.empty()){while (p != NULL){bt = (_Bit_Node_Post)malloc(sizeof(Bit_Node_Post));bt->tag = 'L';bt->bit_tree = p;s.push(bt);p = p->lchild;}while(!s.empty() && ((s.top())->tag == 'R')){bt = s.top();s.pop();cout<<bt->bit_tree->data<<" ";}if (!s.empty()){bt = s.top();bt->tag = 'R';p = bt->bit_tree;p = p->rchild;}}}void level_order(Bit_Tree T) //层次遍历 (good) 一层一层，从左到右{queue<Bit_Tree> q;Bit_Tree p = T;q.push(p);while (!q.empty()){p = q.front();cout<<p->data<<" ";q.pop();if (p->lchild != NULL){q.push(p->lchild);}if (p->rchild != NULL){q.push(p->rchild);}}}int main(){Bit_Tree T; //这里指向根节点的指针被初始化，后面的T就不用&再引用了。creat_node(T);cout<<"先序遍历(递归)"<<endl;pref_order(T);cout<<endl;cout<<"先序遍历(非递归)"<<endl;_pref_order(T);cout<<endl;cout<<"中序遍历(递归)"<<endl;in_order(T);cout<<endl;cout<<"中序遍历(非递归)"<<endl;_in_order(T);cout<<endl;cout<<"后序遍历(递归)"<<endl;post_order(T);cout<<endl;cout<<"后序遍历(非递归)"<<endl;_post_order(T);cout<<endl;cout<<"层次遍历"<<endl;level_order(T);cout<<endl;return 0;}
Bitree T -> 定义Bitree一个实例对象:T;Bitree &T -> 定义Bitree的实例对象的引用,就是一个已经定义的对象的别名,需要初始化;/*摘自<<高质量C++/C编程指南>>引用是C++中的概念，初学者容易把引用和指针混淆一起。一下程序中，n是m的一个引用（reference），m是被引用物（referent）。int m;int &n = m;n相当于m的别名（绰号），对n的任何操作就是对m的操作。例如有人名叫王小毛，他的绰号是“三毛”。说“三毛”怎么怎么的，其实就是对王小毛说三道四。所以n既不是m的拷贝，也不是指向m的指针，其实n就是m它自己。*/Bitree *T -> 定义Bitree的实例对象指针,指向一个实例对象;代码参考:Bitree T;Bitree &T = T;Bitree *T = &T; //&是取地址.
擒龙要下海，打虎要上山。
