二叉树扩展之三叉树C++类模板的实现

大家好，欢迎来到IT知识分享网。

简介

二叉树是递归定义的，这里的三叉树同样也是。

三叉树分为左子树，中子树，右子树。

三叉树的遍历顺序方式，我把它则分为四种：

（1）先序：根->左->中->右

（1）中1序：左->根->中->右

（1）中2序：左->中>根->右

（1）后序：左->中->右->根

例如以下一棵三叉树：

将其以如下方式进行存储在test.txt文件中（便于程序先序读取创建一颗树，空用#表示）

ABCDE#FG#HIJKM

对于上面这棵树，从之后的编程实现对其遍历有如下结果。

编程实现

1.首先建立一个TTNode.h

#ifndef TTNODE_H #define TTNODE_H template <typename T> struct TTNode{ T data; TTNode<T> *lchild,*mchild,*rchild; }; #endif

2.建立TTree.h

#ifndef TTREE_H #define TTREE_H enum 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; }