#pragma once #include <iostream> using namespace std; template<class K, class V> struct BsTreeNode{//二叉樹 節(jié)點 K _key; V _value; BsTreeNode* _left; BsTreeNode* _right; BsTreeNode(const K& key,const V& value) :_key(key) , _value(value) , _left(NULL) , _right(NULL) {} }; template<class K, class V> class BsTree{ public: typedef BsTreeNode<K, V> Node; BsTree() : _root(NULL) { } ~BsTree(){} bool Insert(const K& key, const V& value)//插入 非遞歸 { if (_root == NULL){ _root = new Node(key, value); return true; } Node* cur = _root; while (1){ if (cur->_key > key) { if (cur->_left) cur = cur->_left; else{ cur->_left = new Node(key, value); return true; } } else if (cur->_key < key) { if (cur->_right) cur = cur->_right; else{ cur->_right = new Node(key, value); return true; } }//以上為找 插入位置 并插入 else if (cur->_key == key)//存在 插入失敗 return false; } } bool InsertR(const K& key,const V& value)//插入 遞歸 { return _InsertR(_root,key,value); } 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; } bool RemoveR(const K& key)//刪除 遞歸 { if (_root == NULL) return false; return _RemoveR(_root,key); } bool Remove(K key){//刪除 非遞歸 Node* cur=_root, *prev=NULL; while (cur){ if (cur->_key > key) { prev = cur; cur = cur->_left; } else if (cur->_key < key) { prev = cur; cur = cur->_right; }// 以上為 找到要刪除的 節(jié)點 else { if (cur->_left == NULL)//如果節(jié)點左或右為空,直接刪除該節(jié)//點將之后的節(jié)點 連接在其父節(jié)點 { if (prev == NULL) { _root = cur->_right; } else if (prev->_left == cur) { prev->_left = cur->_right; } else prev->_right = cur->_right; } else if (cur->_right == NULL)//同上 右為空 { if (prev == NULL) { _root = cur->_left; delete cur; } else if (prev->_right == cur) { prev->_right = cur->_left; } else prev->_left = cur->_left; } else//如果左右都不為空 找右孩子最左 或 左孩子最右 節(jié)點替 //代刪除 { prev = cur; cur = cur->_right; while (cur->_left){ cur = cur->_left; } prev->_key = cur->_key; prev->_value = cur->_value; prev->_right =cur->_right; } delete cur; return true; } } return false; } bool modification(K key,V value){//修改 Node* ret = Find(key); if (ret == NULL) return false; ret->_value = value; return true; } private: bool _InsertR(Node* & root,const K& key,const V& value)//插入 遞歸函數(shù) { if (root == NULL) { root = new Node(key,value); return true; } if (root->_key == key) return false; else if (root->_key > key) return _InsertR(root->_left,key,value); else return _InsertR(root->_right,key,value); } bool _RemoveR(Node* & root,const K& key)//刪除 遞歸函數(shù) { if (root->_key < key) return _RemoveR(root->_right, key); if (root->_key>key) return _RemoveR(root->_left, key); if (root->_left == NULL) { Node* dev = root; root = root->_right; delete dev; return true; } else if (root->_right == NULL) { Node* dev = root; root = root->_left; delete dev; return true; } else { root->_key = root->_right->_key; root->_value = root->_right->_value; return _RemoveR(root->_right,root->_key); } } Node* _root; };
網(wǎng)站欄目:c++搜索二叉樹/排序二叉樹
標(biāo)題網(wǎng)址:http://bm7419.com/article28/jjchcp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供小程序開發(fā)、全網(wǎng)營銷推廣、靜態(tài)網(wǎng)站、域名注冊、做網(wǎng)站、虛擬主機
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)