头文件:
- #include <iostream>
- using namespace std;
- template<class Type>
- class Bintree;
- //结点类
- template<class Type>
- class BintreeNode
- {
- friend class Bintree<Type>;
- public:
- BintreeNode() :data(Type()),leftchild(NULL),rightchild(NULL)
- {}
- BintreeNode(Type d,BintreeNode<Type> *l = NULL,BintreeNode<Type> *r = NULL) : data(d),leftchild(l),rightchild(r)
- {}
- private:
- BintreeNode<Type> *leftchild;
- BintreeNode<Type> *rightchild;
- Type data;
- };
- //二叉树类
- template<class Type>
- class Bintree
- {
- public:
- Bintree() :Ref(Type()),root(NULL)
- {}
- Bintree(Type re,BintreeNode<Type> *r = NULL) : Ref(re),root(r)
- {}
- ~Bintree()
- {
- Destory();
- }
- public:
- //提供接口
- void CreatBintree()
- {
- Creat(root);
- }
- void PreOrder()
- {
- PreOrder(root);
- }
- void InOrder()
- {
- InOrder(root);
- }
- void PostOrder()
- {
- PostOrder(root);
- }
- int Height()
- {
- return Height(root);
- }
- int Size()
- {
- return Size(root);
- }
- BintreeNode<Type> *Search(Type key)
- {
- return Search(root,key);
- }
- BintreeNode<Type> *PreOrder_Find(Type key)
- {
- return PreOrder_Find(root,key);
- }
- BintreeNode<Type> *InOrder_Find(Type key)
- {
- return InOrder_Find(root,key);
- }
- BintreeNode<Type> *PostOrder_Find(Type key)
- {
- return PostOrder_Find(root,key);
- }
- BintreeNode<Type> *Parent(BintreeNode<Type> *q)
- {
- return Parent(root,q);
- }
- BintreeNode<Type> *Leftchild(Type key)
- {
- return Leftchild(root,key);
- }
- BintreeNode<Type> *Rightchild(Type key)
- {
- return Rightchild(root,key);
- }
- Type Root()
- {
- return Root(root);
- }
- void Destory()
- {
- return Destory(root);
- }
- bool IsEmpty()
- {
- return IsEmpty(root);
- }
- void quit_system(int &x)
- {
- x = 0;
- }
- protected:
- //创建二叉树
- void Creat(BintreeNode<Type> *&t)
- {
- Type input;
- cin >> input;
- if (input == Ref)
- {
- t = NULL;
- }
- else
- {
- t = new BintreeNode<Type>(input);
- Creat(t->leftchild);
- Creat(t->rightchild);
- }
- }
- // 前序遍历
- void PreOrder(const BintreeNode<Type> *t)
- {
- if (t == NULL)
- {
- return;
- }
- else
- {
- cout << t->data << " ";
- PreOrder(t->leftchild);
- PreOrder(t->rightchild);
- }
- }
- // 中序遍历
- void InOrder(const BintreeNode<Type> *t)
- {
- if (t == NULL)
- {
- return;
- }
- else
- {
- InOrder(t->leftchild);
- cout << t->data << " ";
- InOrder(t->rightchild);
- }
- }
- // 后序遍历
- void PostOrder(const BintreeNode<Type> *t)
- {
- if (t == NULL)
- {
- return;
- }
- else
- {
- PostOrder(t->leftchild);
- PostOrder(t->rightchild);
- cout << t->data << " ";
- }
- }
- // 求高度
- int Height(const BintreeNode<Type> *t)
- {
- if (t == NULL)
- return 0;
- return (Height(t->leftchild) > Height(t->rightchild)) ? (Height(t->leftchild) + 1) : (Height(t->rightchild) + 1);
- }
- int Size(const BintreeNode<Type> *t)
- {
- if (t == NULL)
- return 0;
- return(Size(t->leftchild) + Size(t->rightchild) + 1);
- }
- // 查找一个节点返回其地址
- BintreeNode<Type> *Search( BintreeNode<Type> *t,const Type key)
- {
- if (t == NULL)
- {
- return NULL;
- }
- if (t->data == key)
- return t;
- BintreeNode<Type> *p;
- if ((p = Search(t->leftchild,key)) != NULL)
- return p;
- else
- return Search(t->rightchild,key);
- }
- // 前序查找
- BintreeNode<Type> *PreOrder_Find(BintreeNode<Type> *t,const Type key)
- {
- if (t == NULL)
- {
- return NULL;
- }
- if (t->data == key)
- return t;
- BintreeNode<Type> *p;
- if ((p = PreOrder_Find(t->leftchild,key)) != NULL)
- return p;
- else
- return PreOrder_Find(t->rightchild,key);
- }
- // 中序查找
- BintreeNode<Type> *InOrder_Find(BintreeNode<Type> *t,const Type key)
- {
- if (t == NULL)
- {
- return NULL;
- }
- BintreeNode<Type> *p;
- if ((p = InOrder_Find(t->leftchild,key)) != NULL)
- return p;
- else if (t->data == key)
- return t;
- else
- return InOrder_Find(t->rightchild,key);
- }
- // 后序查找
- BintreeNode<Type> *PostOrder_Find(BintreeNode<Type> *t,const Type key)
- {
- if (t == NULL)
- {
- return NULL;
- }
- BintreeNode<Type> *p;
- BintreeNode<Type> *q;
- if ((p = PostOrder_Find(t->leftchild,key)) != NULL)
- return p;
- else if ((q = PostOrder_Find(t->rightchild,key)) != NULL)
- return q;
- else if (t->data = key)
- return t;
- }
- // 求父节点并返回其父节点地址
- BintreeNode<Type> *Parent(BintreeNode<Type> *&t,BintreeNode<Type> *q)
- {
- if (t == NULL)
- {
- return t;
- }
- if (q == t->leftchild || q == t->rightchild || q == t)
- {
- return t;
- }
- BintreeNode<Type> *p;
- if ((p = Parent(t->leftchild,q)) != NULL)
- {
- return p;
- }
- else
- return Parent(t->rightchild,q);
- }
- // 求左孩子
- BintreeNode<Type> *Leftchild(BintreeNode<Type> *t,const Type key)
- {
- BintreeNode<Type> *p = Search(t,key);
- if (p == NULL)
- {
- cout << "the node is not exist!" << endl;
- return NULL;
- }
- if (p->leftchild == NULL)
- {
- cout << "this node not has leftchild" << endl;
- return NULL;
- }
- else
- return p->leftchild;
- }
- // 求右孩子
- BintreeNode<Type> *Rightchild(BintreeNode<Type> *t,key);
- if (p == NULL)
- {
- cout << "the node is not exist!" << endl;
- return NULL;
- }
- if (p->rightchild == NULL)
- {
- cout << "this node not has rightchild" << endl;
- return NULL;
- }
- else
- return p->rightchild;
- }
- // 求根
- Type Root(const BintreeNode<Type> *t)
- {
- return t->data;
- }
- void Destory(const BintreeNode<Type> *t)
- {
- if (t != NULL)
- {
- Destory(t->leftchild);
- Destory(t->rightchild);
- delete t;
- }
- }
- // 看树是否为空
- bool IsEmpty(const BintreeNode<Type> *t)
- {
- return t == NULL;
- }
- private:
- BintreeNode<Type> *root;
- Type Ref;
- };
页面设计:
- #include "Bintree.h"
- int main()
- {
- Bintree<char> bt('#');
- int select = 1;
- char c;
- while (select)
- {
- cout << "******************************************************************" << endl;
- cout << "* [1] creat [2] PreOrder [3] InOrder *" << endl;
- cout << "* [4] PostOrder [5] Height [6] Size *" << endl;
- cout << "* [7] search [8] PreOrder_Find [9] InOrder_Find *" << endl;
- cout << "* [10] PostOrder_Find [11] parent [12] leftchild *" << endl;
- cout << "* [13] rightchild [14] root [15] destory *" << endl;
- cout << "* [16] Isempty [17] quit_system *" << endl;
- cout << "******************************************************************" << endl;
- cout << "pleae choose:";
- cin >> select;
- switch (select)
- {
- case 1:
- cout << "please enter:";
- bt.CreatBintree();
- break;
- case 2:
- bt.PreOrder();
- cout << endl;
- break;
- case 3:
- bt.InOrder();
- cout << endl;
- break;
- case 4:
- bt.PostOrder();
- cout << endl;
- break;
- case 5:
- cout << bt.Height() << endl;
- break;
- case 6:
- cout << bt.Size() << endl;
- break;
- case 7:
- cout << "please enter what u want to search:";
- cin >> c;
- cout << bt.Search(c) << endl;
- break;
- case 8:
- cout << "please enter what u want to search:";
- cin >> c;
- cout << bt.PreOrder_Find(c) << endl;
- break;
- case 9:
- cout << "please enter what u want to search:";
- cin >> c;
- cout << bt.InOrder_Find(c) << endl;
- break;
- case 10:
- cout << "please enter what u want to search:";
- cin >> c;
- cout << bt.PostOrder_Find(c) << endl;
- break;
- case 11:
- cout << "whose parent u wanna find:";
- cin >> c;
- cout << bt.Parent(bt.Search(c)) << endl;
- break;
- case 12:
- cout << "whose leftchild u wanna find:";
- cin >> c;
- cout << bt.Leftchild(c) << endl;
- break;
- case 13:
- cout << "whose rightchild u wanna find:";
- cin >> c;
- cout << bt.Rightchild(c) << endl;
- break;
- case 14:
- cout << bt.Root() << endl;
- break;
- case 15:
- bt.Destory();
- break;
- case 16:
- if (bt.IsEmpty())
- {
- cout << "it is an empty bintree" << endl;
- }
- else
- {
- cout << "it is not an empty bintree" << endl;
- }
- break;
- case 17:
- bt.quit_system(select);
- break;
- default:
- break;
- }
- }
- return 0;
- }
求高度:
中序遍历:
中序遍历查找:
判断是否为空树:
求其父节点:
后序遍历:
前序遍历:
退出系统:
求其右孩子:
求根:
查找:
求节点个数: