头文件：
#includeusing namespace std;template class Bintree;//结点类template class BintreeNode{ friend class Bintree ;public: BintreeNode() :data(Type()), leftchild(NULL), rightchild(NULL) {} BintreeNode(Type d, BintreeNode *l = NULL, BintreeNode *r = NULL) : data(d), leftchild(l), rightchild(r) {}private: BintreeNode *leftchild; BintreeNode *rightchild; Type data;};//二叉树类template class Bintree{public: Bintree() :Ref(Type()), root(NULL) {} Bintree(Type re, BintreeNode *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 *Search(Type key) { return Search(root, key); } BintreeNode *PreOrder_Find(Type key) { return PreOrder_Find(root, key); } BintreeNode *InOrder_Find(Type key) { return InOrder_Find(root, key); } BintreeNode *PostOrder_Find(Type key) { return PostOrder_Find(root, key); } BintreeNode *Parent(BintreeNode *q) { return Parent(root, q); } BintreeNode *Leftchild(Type key) { return Leftchild(root, key); } BintreeNode *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 *&t) { Type input; cin >> input; if (input == Ref) { t = NULL; } else { t = new BintreeNode (input); Creat(t->leftchild); Creat(t->rightchild); } } // 前序遍历 void PreOrder(const BintreeNode *t) { if (t == NULL) { return; } else { cout << t->data << " "; PreOrder(t->leftchild); PreOrder(t->rightchild); } } // 中序遍历 void InOrder(const BintreeNode *t) { if (t == NULL) { return; } else { InOrder(t->leftchild); cout << t->data << " "; InOrder(t->rightchild); } } // 后序遍历 void PostOrder(const BintreeNode *t) { if (t == NULL) { return; } else { PostOrder(t->leftchild); PostOrder(t->rightchild); cout << t->data << " "; } } // 求高度 int Height(const BintreeNode *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, const Type key) { BintreeNode<Type> *p = Search(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 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;} 求高度：
中序遍历：
中序遍历查找：
推断是否为空树：
求其父节点：
后序遍历：
前序遍历：
退出系统：
求其右孩子：
求根：
查找：
求节点个数：
