二叉树的链表实现
直接上代码:
/* 二叉树的链表实现: 以及三种遍历方式: author:天下无双 Date:2014-5-28 Version:2.0 */ #include <iostream> #include <string> typedef int T;//树内节点的数据类型 using namespace std; class BiTree { private: struct BiNode{ T data; BiNode *lchild,*rchild; BiNode(T d){ data=d; lchild=nullptr; rchild=nullptr; } }; BiNode *root; public: BiTree(){ //root=root->rchild=root->rchild=nullptr; root=nullptr; } ~BiTree(){ } //使用递归创建二叉树 //以二叉排序树的规则建立 /*二级指针写法 bool addBiNode(BiNode **nodeRoot,T d){ if(*nodeRoot==nullptr){ BiNode *p=new BiNode(d); *nodeRoot=p; cout<<p->data<<" insert success!"<<endl; return true; }else if(*nodeRoot!=nullptr&&d<(*nodeRoot)->data){ //往左子树递归 addBiNode(&((*nodeRoot)->lchild),d); }else if(*nodeRoot!=nullptr&&d>(*nodeRoot)->data){ //往右子树递归 addBiNode(&((*nodeRoot)->rchild),d); }else{ cout<<"树中已有该数据"<<endl; return false; } } */ //指针的引用写法(推荐使用) bool addBiNode(BiNode *&nodeRoot,T d){ if(nodeRoot==nullptr){ BiNode *p=new BiNode(d); nodeRoot=p; cout<<p->data<<" insert success!"<<endl; return true; }else if(nodeRoot!=nullptr&&d<nodeRoot->data){ //往左子树递归 addBiNode(nodeRoot->lchild,d); }else if(nodeRoot!=nullptr&&d>(nodeRoot)->data){ //往右子树递归 addBiNode(nodeRoot->rchild,d); }else{ cout<<"树中已有该数据"<<endl; return false; } } BiNode *&getRoot(){//返回根指针的引用 return root; } BiNode *getPtrToRoot()const{ return root; } bool Traverse(const BiNode *b,string type)const{ if(type=="PreOrderTraverse"){ cout<<"\n先序遍历的结果为:"<<endl; PreOrderTraverse(b); return true; }else if(type=="InOrderTraverse"){ cout<<"\n中序遍历的结果为:"<<endl; InOrderTraverse(b); return true; }else if(type=="PostOrderTraverse"){ cout<<"\n后序遍历的结果为:"<<endl; PostOrderTraverse(b); return true; }else{ cout<<"遍历类型无效!"<<endl; return false; } } protected: //T如果是结构或者类类型,需重载<<运算符 void Visit(const BiNode *r)const{ cout<<r->data<<" "; } //利用递归遍历,三种遍历原理都是一样的 //前序遍历,先根遍历 void PreOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot!=nullptr) Visit(nodeRoot); if(nodeRoot->lchild!=nullptr) PreOrderTraverse(nodeRoot->lchild); if(nodeRoot->rchild!=nullptr) PreOrderTraverse(nodeRoot->rchild); } //中根遍历 void InOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot->lchild!=nullptr) InOrderTraverse(nodeRoot->lchild); if(nodeRoot!=nullptr)//当该点左子树空时 Visit(nodeRoot); if(nodeRoot->rchild!=nullptr) InOrderTraverse(nodeRoot->rchild); } //后序遍历 void PostOrderTraverse(const BiNode *nodeRoot)const{ if(nodeRoot->lchild!=nullptr) PostOrderTraverse(nodeRoot->lchild); if(nodeRoot->rchild!=nullptr) PostOrderTraverse(nodeRoot->rchild); if(nodeRoot!=nullptr) Visit(nodeRoot); } };
测试代码:
int main() { BiTree b; //b.addBiNode(&b.root,50);//设立根节点值//二级指针写法 b.addBiNode(b.getRoot(),50);//指针的引用写法 int i; int arr[9]={30,40,35,27,100,90,110,95,-999}; bool flag=true; while(flag) { flag=!flag; //cout<<"请输入一个数(输入-999将退出:"; //cin>>i; for(int j=0;j<9;j++) { i=arr[j]; if(i==-999) break; b.addBiNode(b.getRoot(),i); } //b.addBiNode(&b.root,i); } b.Traverse(b.getPtrToRoot(),"PreOrderTraverse"); b.Traverse(b.getPtrToRoot(),"InOrderTraverse"); b.Traverse(b.getPtrToRoot(),"PostOrderTraverse"); cin.get(); system("pause"); return 0; }
测试结果:(注意,输入顺序不同时生成的树不同)