#include <iostream> #include <cstdio> #include <cstring> using namespace std; class BSTNode { public: int key; //结点的值 BSTNode* left; //结点的左孩子 BSTNode* right; //结点的右孩子 BSTNode* parent; //结点的双亲 /*构造函数*/ BSTNode():parent(NULL) {} BSTNode(int key, BSTNode* left, BSTNode* right, BSTNode* parent) :key(key), left(left), right(right), parent(parent) {} }; class BSTree { private: BSTNode* root; //根节点 public: /*构造函数*/ BSTree() :root(NULL) {}; /*获取根节点*/ BSTNode* getRoot(); /*将键值key插入到二叉树中*/ void insert(int key); /*将结点插入到二叉树中*/ void insert(BSTNode*& root, BSTNode* node); /*先序遍历*/ void preOrder(BSTNode* root); /*中序遍历*/ void inOrder(BSTNode* root); /*后序遍历*/ void postOrder(BSTNode* root); /*查找二叉树中键值为key的结点并返回*/ BSTNode* search(BSTNode* node, int key); /*找出二叉树中键值最小的结点并返回*/ BSTNode* minimum(BSTNode* node); /*找出二叉树中键值最大的结点并返回*/ BSTNode* maximum(BSTNode* node); /*找到二叉树结点node的后继结点*/ BSTNode* successor(BSTNode* node); /*找到二叉树结点node的前驱结点*/ BSTNode* predecessor(BSTNode* node); /*移除键值为key的结点*/ BSTNode* remove(BSTNode*& root, int key); /*销毁二叉排序树*/ void destroy(BSTNode* root); }; BSTNode* BSTree::getRoot() { return root; } /*先序遍历*/ void BSTree::preOrder(BSTNode* root) { if (root != NULL) { cout << root->key; preOrder(root->left); preOrder(root->right); } } /*中序遍历*/ void BSTree::inOrder(BSTNode* root) { if (root != NULL) { inOrder(root->left); cout << root->key; inOrder(root->right); } } /*后序遍历*/ void BSTree::postOrder(BSTNode* root) { if (root != NULL) { postOrder(root->left); postOrder(root->right); cout << root->key; } } BSTNode* BSTree::search(BSTNode* node, int key) { if (node == NULL || node->key == key) return node; if (node->key < key) search(node->right, key); else search(node->left, key); } BSTNode* BSTree::minimum(BSTNode* node) { if (node->left == NULL) return node; minimum(node->left); } BSTNode* BSTree::maximum(BSTNode* node) { if (node->right == NULL) return node; maximum(node->right); } /*查找node的后继结点*/ BSTNode* BSTree::successor(BSTNode* node) { /*（1）右子树非空，返回右子树最小值结点*/ if (node->right != NULL) return minimum(node->right); /*（2）*/ BSTNode* pnode = node->parent; while (pnode != NULL&&node == pnode->right) { node = pnode; pnode = pnode->parent; } return pnode; } /*查找结点node的前驱节点*/ BSTNode* BSTree::predecessor(BSTNode* node) { /*（1）左子树非空，返回左子树最大值结点*/ if (node->left != NULL) return maximum(node->left); /*（2）*/ BSTNode* pnode = node->parent; while (pnode != NULL&&node == pnode->left) { node = pnode; pnode = pnode->parent; } return pnode; } /* * 将结点插入到二叉树中 * * 参数说明： * root 二叉树的根结点 * node 要插入的结点 */ void BSTree::insert(BSTNode*& root, BSTNode* node) { BSTNode* y = NULL; BSTNode* x = root; /*找到要插入的位置*/ while (x != NULL) { y = x; if (node->key > x->key) x = x->right; else x = x->left; } /*插入结点*/ node->parent = y; if (y == NULL) root = node; else if(y->key > node->key) y->left = node; else y->right = node; } void BSTree::insert(int key) { BSTNode* node = new BSTNode(key, NULL, NULL, NULL); insert(root, node); } //BSTNode* BSTree::remove(BSTNode*& root, int key) //{ // BSTNode* x = NULL; // BSTNode* y = NULL; // // BSTNode* z = search(root, key); // if (z->left == NULL || z->right == NULL) // y = z; // else y = successor(z); // // if (y->left != NULL) // x = y->left; // else x = y->right; // // if (x != NULL) // x->parent = y->parent; // // if (y->parent == NULL) // root = x; // else if (y->parent->left == y) // y->parent->left = x; // else if (y->parent->right == y) // y->parent->right = x; // // if (y != z) // z->key = y->key; // // return y; //} /*获取要删除的结点并返回*/ BSTNode* BSTree::remove(BSTNode*& root, int key) { BSTNode* node = search(root, key); printf("%d ", node->key); if (node != NULL) { if (node->left == NULL && node->right == NULL) //node为叶子结点 { if (node->parent == NULL) //要删除的结点为根结点 return node; else if (node->parent->left == node)//判断要删除点在双亲结点的左边还是右边 node->parent->left = NULL; else node->parent->right = NULL; } else if (node->left == NULL) //node左子树为空 { if (node->parent == NULL) //要删除的结点为根结点 { this->root = node->right; node->right->parent = NULL; } else if (node->parent->left == node)//判断要删除点在双亲结点的左边还是右边 node->parent->left = node->right; else node->parent->right = node->right; } else if (node->right == NULL) //node右子树为空 { if (node->parent == NULL) //要删除的结点为根结点 { this->root = node->left; node->left->parent = NULL; } else if (node->parent->left == node)//判断要删除点在双亲结点的左边还是右边 node->parent->left = node->left; else node->parent->right = node->left; } else //node左右子树均不为空 { BSTNode* lnode = node->left; //lnode初始为node左子树的根节点 while (lnode->right) //找到node左子树的最右结点赋值为lnode lnode = lnode->right; lnode->right = node->right; //将node的右子树变成lnode的右子树 node->right->parent = lnode; if (node->parent == NULL) //要删除的结点为根结点 { this->root = node->right; if (node->right->left != NULL) { BSTNode* leftDownNode = minimum(node->right); leftDownNode->left = node->left; node->left->parent = leftDownNode; } else { node->right->left = node->left; node->left->parent = node->right; } } else if (node->parent->left == node) //将node的左子树替换node的位置 { node->parent->left = node->left; node->left->parent = node->parent; } else if (node->parent->right == node) { node->parent->right = node->left; node->left->parent = node->parent; } } } return node; } /*销毁二叉树*/ void BSTree::destroy(BSTNode* root) { if (root == NULL) return; destroy(root->left); destroy(root->right); delete root; }
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/10628.html