‘二叉树’是数据结构中比较重要的一部分,这里主要讨论一下‘搜索二叉树’,针对‘搜索二叉树的插入、删除和查找节点进行分情况讨论,希望能够帮助读者更加的理解搜索二叉树的原理。
◆搜索二叉树的性质:
1.每个节点都有一个一个作为搜索依据的关键码,所有节点的关键码都不相同。
2.左子树所有的关键码(key)都小于根节点的关键码(key)。
3.右子树所有的关键码(key)都大于根节点的关键码(key)。
4.左、右子树都是二叉搜索树。
实现‘搜索二叉树’的节点结构可以实现为K形式,和K、V形式,若实现K形式,则K表示节点的值,同时可以使用K来确定节点的位置,若实现K、V形式,则K表示节点的一个标记,用来判断节点在二叉树中具体的存储位置,V表示节点的具体存储的值。这里实现的是K、V形式,K形式读者可以下去自己进行尝试。
◆下面为实现‘搜索二叉树’的具体节点结构:
template <class K, class V> struct BSTNode { BSTNode<K, V>* _left; //指向左节点的指针 BSTNode<K, V>* _right; //指向右节点的指针 K _key; //节点标记,确定节点位置 V _value; //节点的值 BSTNode(const K& key, const V& value) //构造节点 :_key(key) , _value(value) , _left(NULL) , _right(NULL) { } };
◆讨论相关操作情况
(1)节点插入
(2)节点删除
(3)节点查找
根据搜索二叉树的性质来进行查找,当key>root->key;向右孩子节点再次进行查找,当key<root->key,从左边的孩子节点进行查找,否则,就证明查找到了。
◆下面是详细的代码(实现的递归和非递归两种方式)
template <class K, class V> class BSTree { typedef BSTNode<K, V> Node; public: BSTree() //构造 :_root(NULL) {} bool Insert(const K& key, const V& value) //非递归插入 { if (_root == NULL) //根节点为空 { _root = new Node(key, value); return true; } Node* cur = _root; if (cur->_left == NULL && cur->_right == NULL) //父节点的左右节点为空 { if (cur->_key < key) { cur->_right = new Node(key, value); } else if (cur->_key > key) { cur->_left = new Node(key, value); } else { return false; } } else { Node* parent = cur; while (cur) { parent = cur; if (cur->_key < key) { if (parent->_right == NULL) //右节点为空 { parent->_right = new Node(key, value); } cur = cur->_right; } else if (cur->_key > key) { if (parent->_left == NULL) //左节点为空 { parent->_left = new Node(key, value); } cur = cur->_left; } else //数据在树中已经存在,防止数据冗余 { return false; } } } return true; } bool Remove(const K& key) //非递归删除 { if (_root == NULL) //根节点为空 { return false; } if (_root->_left == NULL && _root->_right == NULL) //根节点的左右节点为空 { if (_root->_key == key) { delete _root; _root = NULL; return true; } else { return false; } } Node* parent = NULL; Node* cur = _root; while (cur) { if (cur->_key > key) //寻找要删除的节点 { parent = cur; cur = cur->_left; } else if (cur->_key < key) { parent = cur; cur = cur->_right; } else //找到要删除的节点 { Node* del = cur; if (cur->_left == NULL) //左为空 { if (parent == NULL) //cur节点没有父节点 { _root = cur->_right; } else //cur有父节点 { if (parent->_left == cur) { parent->_left = cur->_right; } else { parent->_right = cur->_right; } } } else if (cur->_right == NULL) //右为空 { if (parent == NULL) { _root = cur->_left; } else { if (parent->_left == cur) { parent->_left = cur->_left; } else { parent->_right = cur->_left; } } } else //左、右为空 { //找右树的最左节点 //找到的节点与cur交换再删除 parent = cur; Node* firstLeft = cur->_right; while (firstLeft->_left) { parent = firstLeft; parent = firstLeft->_left; } swap(cur->_key, firstLeft->_key); swap(cur->_value, firstLeft->_value); del = firstLeft; if (parent->_left == firstLeft) { parent->_left = firstLeft->_right; } else { parent->_right = firstLeft->_right; } } delete del; return true; } } return false; } Node* Find(const K& key) //非递归查找 { if (_root == NULL) { return NULL; } Node* cur = _root; while (cur) { if (cur->_key < key) { cur = cur->_right; } else if (cur->_key > key) { cur = cur->_left; } else { return cur; } } return NULL; } bool Insert_R(const K& key, const V& value) //递归实现插入 { return _Insert_R(_root, key, value); } bool Remove_R(const K& key) //递归实现删除 { return _Remove_R(_root, key); } Node* Find_R(const K& key) //递归实现查找 { return _Find_R(_root, key); } void Inorder() //递归实现中序遍历 { _Inorder(_root); } protected: bool _Insert_R(Node*& root, const K& key, const V& value) //递归实现插入节点 { if (root == NULL) { root = new Node(key, value); //添加引用会更改_root return true; } if (root->_key < key) { return _Insert_R(root->_right, key, value); } else if (root->_key > key) { return _Insert_R(root->_left, key, value); } else { return false; } } 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 _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 { Node* del = root; if (root->_left == NULL) { root = root->_right; delete del; return true; } else if (root->_right == NULL) { root = root->_left; delete del; return true; } else { Node* firstLeft = root->_right; while (firstLeft->_left) { firstLeft = firstLeft->_left; } swap(firstLeft->_key, root->_key); swap(firstLeft->_value, root->_value); _Remove_R(root->_right, key); delete del; return true; } } return false; } void _Inorder(Node* root) //中序遍历 { if (root == NULL) { return; } _Inorder(root->_left); cout << root->_key << " "; _Inorder(root->_right); } protected: Node* _root; };
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。