二叉查找树C++实现

#pragma once #include <iostream> using namespace std; template <class T> class BSTNode { public: T key; BSTNode *parent; BSTNode *left; BSTNode *right; BSTNode(T value, BSTNode *p, BSTNode *l, BSTNode *r):key(value),parent(p),left(l),right(r) { } }; template <class T> class BSTree { private: BSTNode<T> *mRoot; public: BSTree():mRoot(NULL){} ~BSTree(){} // 前序排序 void preOrder() { preOrder(mRoot); } void inOrder() { inOrder(mRoot); } void postOrder() { postOrder(mRoot); } // 查找二叉树中键值为key的节点 BSTNode<T>* SearchKey(const T key) { return SearchKey(mRoot, key); } BSTNode<T>* minKey() { return minKey(mRoot); } BSTNode<T>* maxKey() { return maxKey(mRoot); } // 插入节点 void insert( T key) { BSTNode<T> *z = new BSTNode<T>(key, NULL, NULL, NULL); if (z == NULL) { return; } insert(mRoot, z); } private: // 前序排序 void preOrder(BSTNode<T> *tree) const { if (tree != NULL) { cout << tree->key << " "; preOrder(tree->left); preOrder(tree->right); } } // 中序排序 void inOrder(BSTNode<T> *tree) const { if (tree != NULL) { preOrder(tree->left); cout << tree->key << " "; preOrder(tree->right); } } // 后序排序 void postOrder(BSTNode<T> *tree) const { if (tree != NULL) { preOrder(tree->left); preOrder(tree->right); cout << tree->key << " "; } } BSTNode<T>* SearchKey(BSTNode<T>* pNode, const T key) const { // 递归查找 /*if (pNode = NULL || key == pNode->key) { return pNode; } else if (key > pNode->key) { return SearchKey(pNode->right); } else { return SearchKey(pNode->left); }*/ // 非递归查找 BSTNode<T>* x = pNode; while (x != NULL) { if (key > x->key) { x = x->right; } else if (key < x->key) { x = x->left; } else { return x; } } return NULL; } // 将节点插入到二叉树中 void insert(BSTNode<T>* &tree, BSTNode<T> *Node) { BSTNode<T> *y = NULL; BSTNode<T> *x = tree; while (NULL != x) { y = x; if (Node->key > x->key) { x = x->right; } else { x = x->left; } } Node->parent = y; // 这到后面两句为关键代码 if (NULL == y) { tree = Node; } else if (Node->key > y->key) { y->right = Node; } else { y->left = Node; } } // 查找最小节点 BSTNode<T>* minKey(BSTNode<T>* pNode) const { while (pNode != NULL) { pNode = pNode->left; } return pNode; } BSTNode<T>* maxKey(BSTNode<T>* pNode) const { while (pNode != NULL) { pNode = pNode->right; } return pNode; } // 找节点（x）的后继节点。即查找二叉树中数值大于该节点的最小值 BSTNode<T>* Successor(BSTNode<T>* x) { // 分三种情况 // 1. x有右孩子，找到以右孩子为根的子树的最小节点 // 2. x没有右孩子，当x为左孩子，则x的父节点为后继节点 // 2. x没有右孩子，当x为右孩子，则找x的最低父节点，并且该父节点具有左孩子 if (x->right != NULL) { return minKey(x->right); } BSTNode<T>* y = x->parent; while ((NULL != y) &&(x == y->right)) { x= y; y = y->parent; } return y; } // 找结点(x)的前驱结点。即查找"二叉树中数据值小于该结点"的"最大结点" BSTNode<T>* BSTree<T>::predecessor(BSTNode<T> *x) { // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x->left != NULL) return maxKey(x->left); // 如果x没有左孩子。则x有以下两种可能： // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 BSTNode<T>* y = x->parent; while ((y!=NULL) && (x==y->left)) { x = y; y = y->parent; } return y; } // 删除二叉树中的节点，并返回被删除的节点 //BSTNode<T>* RemoveNode(BSTNode<T>* &tree, BSTNode<T>* pNode) //{ // BSTNode<T>* x = tree; // while (NULL != x && pNode->key != x->key) // { // if (pNode->key > x->key) // { // x = x->right; // } // else if (pNode->key < x->key) // { // x = x->left; // } // } // // 找到或x为空 //} };