二叉搜索树的达成
发布时间：2021-11-18 18:50:45 所属栏目：教程 来源：互联网
导读：这次贴上二叉搜索树的实现，搜索插入删除我都实现了递归和非递归两种版本（递归函数后面有_R标识） #pragma once #includeiostream using namespace std; templateclass K,class V struct BSTNode { K _key; V _value; BSTNode *_left; BSTNode *_right; BST
|
这次贴上二叉搜索树的实现，搜索插入删除我都实现了递归和非递归两种版本（递归函数后面有_R标识） #pragma once #include<iostream> using namespace std; template<class K,class V> struct BSTNode { K _key; V _value; BSTNode *_left; BSTNode *_right; BSTNode(const K& key, const V& value) :_key(key) ,_value(value) ,_left(NULL) ,_right(NULL) { } }; template<class K,class V> class BSTree { typedef BSTNode<K, V> Node; public: BSTree() :_root(NULL) { } ~BSTree() {} bool Insert(const K& key,const V& value) { if (_root == NULL) { _root = new Node(key, value); } Node *cur = _root; Node *parent = _root; while (cur) { parent = cur; if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return false; } } if (parent->_key > key) { parent->_left = new Node(key, value); } else { parent->_right = new Node(key, value); } return true; } bool Insert_R(const K& key, const V& value) { return _Insert_R(_root,key,value); } bool Remove(const K& key) { if (_root == NULL) { return false; } if (_root->_left == NULL && _root->_right == NULL) { delete _root; _root = NULL; return true; } Node *del = _root; Node *parent = _root; while (del && del->_key != key) { parent = del; if (del->_key > key) { del = del->_left; } else if (del->_key < key) { del = del->_right; } } if (del) { if (del->_left == NULL || del->_right == NULL) { if (del->_left == NULL) { if (parent->_left == del) { parent->_left = del->_right; } else { parent->_right = del->_right; } } else { if (parent->_left == del) { parent->_left = del->_left; } else { parent->_right = del->_left; } } delete del; return true; } else { Node *InOrderfirst = del->_right; Node *parent = del; while (InOrderfirst->_left != NULL) { parent = InOrderfirst; InOrderfirst = InOrderfirst->_left; } swap(del->_key, InOrderfirst->_key); swap(del->_value, InOrderfirst->_value); if (InOrderfirst->_left == NULL) { if (parent->_left == InOrderfirst) { parent->_left = InOrderfirst->_right; } else { parent->_right = InOrderfirst->_right; } } else { if (parent->_left == InOrderfirst) { parent->_left = InOrderfirst->_left; } else { parent->_right = InOrderfirst->_left; } } delete InOrderfirst; return true; } } return false; } bool Remove_R(const K& key) { return _Remove_R(_root, key); } Node *Find(const K& key) { Node *cur = _root; while (cur) { if (cur->_key > key) { cur = cur->_left; } else if (cur->_key < key) { cur = cur->_right; } else { return cur; } } return NULL; } Node *Find_R(const K& key) { return _Find_R(_root,key); } void InOrder() { return _InOrder(_root); } protected: bool _Remove_R(Node *&root,const K& key) { if (root == NULL) { return false; } if (root->_key > key) { return _Remove_R(root->_left, key); } else if (root->_key < key) { return _Remove_R(root->_right, key); } else { if (root->_left == NULL || root->_right == NULL) { if (root->_left == NULL) { Node *del = root; root = root->_right; delete del; return true; } else { Node *del = root; root = root->_left; delete del; return true; } } else { Node *InOrderfirst = root->_right; while (InOrderfirst->_left != NULL) { InOrderfirst = InOrderfirst->_left; } swap(InOrderfirst->_key, root->_key); swap(InOrderfirst->_value, root->_value); return _Remove_R(root->_right, key); } } } void _InOrder(Node *root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node *_Find_R(Node *root, const K& key) { if (root == NULL) { return NULL; } if (root->_key < key) { return _Find_R(root->_right, key); } else if (root->_key > key) { return _Find_R(root->_left, key); } else { return root; } } bool _Insert_R(Node *&root, const K& key, const V& value) { if (root == NULL) { root = new Node(key, value); return true; } if (root->_key > key) { return _Insert_R(root->_left, key, value); } else if (root->_key < key) { return _Insert_R(root->_right, key, value); } else { return false; } } protected: Node *_root; }; void TestBinarySearchTree() { BSTree<int, int> bst1; int a[10] = { 5,4,3,1,7,8,2,6,0,9 }; for (int i = 0; i < 10; ++i) { bst1.Insert(a[i],a[i]); } // bst1.InOrder(); //cout << endl; //cout << bst1.Find(1)->_key << " "; //cout << bst1.Find(5)->_key << " "; //cout << bst1.Find(9)->_key << " "; //cout << bst1.Find_R(1)->_key << " "; //cout << bst1.Find_R(5)->_key << " "; //cout << bst1.Find_R(9)->_key << " "; //cout << endl; bst1.Remove_R(5); bst1.Remove_R(2); bst1.Remove_R(8); for (int i = 0; i < 10; ++i) { bst1.Remove_R(a[i]); } bst1.InOrder(); bst1.Remove(5); bst1.Remove(2); bst1.Remove(8); for (int i = 0; i < 10; ++i) { bst1.Remove(a[i]); } bst1.InOrder(); } 二叉搜索树的性质： 每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同。 左子树上所有节点的关键码（key）都小于根节点的关键码（key）。 右子树上所有节点的关键码（key）都大于根节点的关键码（key）。 左右子树都是二叉搜索树。 插入步骤很简单，就是从根节点开始，进行比较，然后我那个左（右）子树走，走到叶子节点之后，链接上就可以了 寻找也是类似插入的，很简单 删除就要略微繁琐一点有三种情况（其实直接就可以归类为两种） 被删除的节点是叶子节点（左右孩子都是空） 直接删除就可以了 被删除的节点只有一个孩子（左孩子或者右孩子是空） 删除之前需要将父亲节点指针指向被删除节点的孩子 被删除的节点左右孩子都健在（左右孩子都不为空） 删除之前需要和一个特定位置的节点交换  （编辑：常州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
