《二叉排序树C++实现》由会员分享,可在线阅读,更多相关《二叉排序树C++实现(3页珍藏版)》请在金锄头文库上搜索。
1、#include using namespace std;class BiSortTree;/二叉树结点类的定义class BiNode /结点的数据域/左孩子指针/右孩子指针int data;BiNode *lchild;BiNode *rchild;friend class BiSortTree;public:BiNode() lchild = rchild = NULL; ;/二叉排序树类定义class BiSortTreepublic:BiSortTree() root = NULL; BiNode *Getroot() return root; void CreatBst(int a
2、,int n);void Insert(int item);void Insert(BiNode *&root,BiNode *p); void PreOrder() PreOrder(root); 树void PreOrder(BiNode *current); 根的子树void InOrder() InOrder(root); void InOrder(BiNode *current);void PostOrder() PostOrder(root); 序树/构造函数/返回根结点指针/建立二叉排序树/向二叉排序树中插入一个元素/向二叉排序树中插入一个结点/前序遍历二叉排序/前序遍历以 cu
3、rrent 为/前序遍历二叉排序树/前序遍历二叉排void PostOrder(BiNode *current);void Print();BiNode *Search(int key) return Search(root, key); private:BiNode *root;BiNode *Search(BiNode *root, int key);void BiSortTree:Insert(BiNode *&root, BiNode *p)if (root = NULL)/插入新结点/向左子树中插入结点/向右子树中插入结点root = p;else if (p-data data)I
4、nsert(root-lchild, p);elseInsert(root-rchild, p);void BiSortTree:Insert(int item)BiNode *p = new BiNode;p-data = item;Insert(root, p); void BiSortTree:CreatBst(int a,int n)for (int i = 0; i data = ai;Insert(root,p);void BiSortTree:PreOrder(BiNode *current)if (current != NULL) /即到达叶结点,是递归终止条 件cout da
5、ta lchild);/前序遍历左子树PreOrder(current-rchild);/前序遍历右子树void BiSortTree:InOrder(BiNode *current)if (current != NULL)InOrder(current-lchild);cout data rchild);void BiSortTree:PostOrder(BiNode *current)if (current != NULL)PostOrder(current-lchild);PostOrder(current-rchild); cout data ;void BiSortTree:Prin
6、t()cout 前序遍历的结果:;PreOrder();cout endl;cout 中序遍历的结果:;InOrder();cout endl;cout 后序遍历的结果:;PostOrder();cout data)return root;else if (key data)return Search(root-lchild, key);else return Search(root-rchild, key);void main()BiSortTree bt;/定义二叉树对象int n,*b,i;定义数组指针b,用于存放元素cout n;b = new intn;cout 请输入二叉排序树的元素:;for(i = 0;i bi;bt.CreatBst(b,n);/以数组 b 为元素,建立二叉排序树bt.Print();cout bt.Search(5) endl;