简介
二叉树是递归定义的，这里的三叉树同样也是。
三叉树分为左子树，中子树，右子树。
三叉树的遍历顺序方式，我把它则分为四种：
（1）先序：根->左->中->右
（1）中1序：左->根->中->右
（1）中2序：左->中>根->右
（1）后序：左->中->右->根
例如以下一棵三叉树：
将其以如下方式进行存储在test.txt文件中（便于程序先序读取创建一颗树，空用#表示）
ABC###D####E#F####G#H###IJ###K###M###
对于上面这棵树，从之后的编程实现对其遍历有如下结果。
编程实现
1.首先建立一个TTNode.h
#ifndef TTNODE_H#define TTNODE_Htemplate <typename T>struct TTNode{T data;TTNode<T> *lchild,*mchild,*rchild;};#endif
2.建立TTree.h
#ifndef TTREE_H#define TTREE_Henum Tags{Left,Mid,Right};enum style{Pre,In01,In02,Post};template <typename T>struct StackElem{TTNode<T> *p;Tags flag;};template <typename T>class TTree{protected:TTNode<T> *root;private:void DestroyTTree(TTNode<T>* &t){if(t!=NULL){DestroyTTree(t->lchild);DestroyTTree(t->mchild);DestroyTTree(t->rchild);delete t;t=NULL; }} public:TTree(){root=NULL;}~TTree(){DestroyTTree(root);}void CreateTTreeFromFile(ifstream &f){T e;InputFromFile(f,e);if(e==Nil) return ;root =new TTNode<T>;assert(root!=NULL);root->data=e;TTree<T> left,mid,right;left.CreateTTreeFromFile(f);mid.CreateTTreeFromFile(f);right.CreateTTreeFromFile(f);root->lchild=left.root;left.root=NULL;root->mchild=mid.root;mid.root=NULL;root->rchild=right.root;right.root=NULL;}bool TTreeEmpty()const{return root==NULL;}int TTreeDepth(TTNode<T>* t){int i,j,k,bri;if(t==NULL) return 0;else{i=TTreeDepth(t->rchild);k=TTreeDepth(t->mchild);j=TTreeDepth(t->lchild);bri=i>j?i:j;return bri>k?bri+1:k+1;}}TTNode<T>* Root(){return root;}T Value(TTNode<T>* p)const{return p->data;}void Assign(TTNode<T>* p,T value){p->data=value;}void PreOrderTraverse(void(*visit)(TTNode<T>*))const{stack<TTNode<T>*> s;TTNode<T> *t=root;s.push(NULL);while(t!=NULL){visit(t);if(t->rchild!=NULL)s.push(t->rchild);if(t->mchild!=NULL)s.push(t->mchild);if(t->lchild!=NULL)t=t->lchild;else{t=s.top();s.pop();}}}void In01OrderTraverse(void(*visit)(TTNode<T>*))const{StackElem<T> se;stack<StackElem<T> > s;TTNode<T> *t=root;if(t==NULL) return ;while(!s.empty()||t!=NULL){while(t!=NULL){se.p=t;se.flag=Left;s.push(se);t=t->lchild;}se=s.top();s.pop();t=se.p;if(se.flag==Left){visit(t);se.flag=Mid;s.push(se);t=t->mchild;}else{if(se.flag==Mid){se.flag=Right;s.push(se);t=t->rchild;}else{t=NULL;}}}}void In02OrderTraverse(void(*visit)(TTNode<T>*))const{StackElem<T> se;stack<StackElem<T> > s;TTNode<T> *t=root;if(t==NULL) return ;while(!s.empty()||t!=NULL){while(t!=NULL){se.p=t;se.flag=Left;s.push(se);t=t->lchild;}se=s.top();s.pop();t=se.p;if(se.flag==Left){se.flag=Mid;s.push(se);t=t->mchild;}else{if(se.flag==Mid){visit(t);se.flag=Right;s.push(se);t=t->rchild;}else{t=NULL;}}}}void PostOrderTraverse(void(*visit)(TTNode<T>*))const{StackElem<T> se;stack<StackElem<T> > s;TTNode<T> *t=root;if(t==NULL) return ;while(!s.empty()||t!=NULL){while(t!=NULL){se.p=t;se.flag=Left;s.push(se);t=t->lchild;}se=s.top();s.pop();t=se.p;if(se.flag==Left){se.flag=Mid;s.push(se);t=t->mchild;}else{if(se.flag==Mid){se.flag=Right;s.push(se);t=t->rchild;}else{visit(t);t=NULL;}}}}void LevelOrderTraverse(void(*visit)(TTNode<T>*))const{queue<TTNode<T>*> q;TTNode<T> *a,*t=root;if(t!=NULL){q.push(t);while(!q.empty()){a=q.front();q.pop();visit(a);if(a->lchild!=NULL)q.push(a->lchild);if(a->mchild!=NULL)q.push(a->mchild);if(a->rchild!=NULL)q.push(a->rchild);}}cout<<endl;}void OrderTraverse(TTNode<T>* t,style mode,void(*visit)(TTNode<T>*))const{if(t!=NULL){if(mode==Pre)visit(t);OrderTraverse(t->lchild,mode,visit);if(mode==In01)visit(t);OrderTraverse(t->mchild,mode,visit);if(mode==In02)visit(t);OrderTraverse(t->rchild,mode,visit);if(mode==Post)visit(t);}}};#endif
3.此外习惯将头文件组合在一起也弄个头文件C.h（多可少不行）
#ifndef C_H#define C_H#include <iostream>#include <fstream>#include <iomanip>#include <cmath>#include <string>#include <vector>#include <list>#include <stack>#include <queue>#include <algorithm>#include <assert.h>using namespace std;#endif
4.最后是测试代码
#include "C.h"#include "TTNode.h"typedef char T;void Visit(TTNode<T> *c){cout<<c->data<<" ";}void InputFromFile(ifstream &f,T &c){f>>c;}void Input(T &c){cin>>c;}T Nil='#';#include "TTree.h"int main(){TTree<T> t,c;TTNode<T> *p, *q;T e;ifstream fin("test.txt");t.CreateTTreeFromFile(fin);fin.close();cout<<"由文件test.txt创建三叉树t后，树t空否？"<<boolalpha<<t.TTreeEmpty();cout<<"。树t的深度="<<t.TTreeDepth(t.Root())<<endl;cout<<endl<<"层序遍历删除后的三叉树t：";t.LevelOrderTraverse(Visit);p=t.Root();cout<<endl<<"t的根结点="<<t.Value(p)<<"。给根结点赋新值，请输入新值：";Input(e);t.Assign(p, e);cout<<endl<<"层序遍历删除后的三叉树t：";t.LevelOrderTraverse(Visit);cout<<endl<<"先序遍历删除后的三叉树t：";t.PreOrderTraverse(Visit);cout<<endl<<"先序递归遍历删除后的三叉树t：";t.OrderTraverse(t.Root(), Pre, Visit);cout<<endl;cout<<endl<<"中1序遍历删除后的三叉树t：";t.In01OrderTraverse(Visit);cout<<endl<<"中1序递归遍历删除后的三叉树t：";t.OrderTraverse(t.Root(), In01, Visit);cout<<endl;cout<<endl<<"中2序遍历删除后的三叉树t：";t.In02OrderTraverse(Visit);cout<<endl<<"中2序递归遍历删除后的三叉树t：";t.OrderTraverse(t.Root(), In02, Visit);cout<<endl;cout<<endl<<"后序遍历删除后的三叉树t：";t.PostOrderTraverse(Visit);cout<<endl<<"后序递归遍历删除后的三叉树t：";t.OrderTraverse(t.Root(), Post, Visit);return 0;}
