您好,登录后才能下订单哦!
如何进行搜索二叉树分析,相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
一、搜索二叉树
1、定义:它是一棵排序二叉树,可为空树。
2、性质:
每个节点都有一个作为搜索依据的关键码(key),所有节点的关键码互不相同;
左子树上所有节点的关键码(key)都小于根节点的关键码(key);
右子树上所有节点的关键码(key)都大于根节点的关键码(key);
左、右子树都是二叉搜索树。
二、源代码
1、定义节点
template<class K,class V> struct BSTreeNode { BSTreeNode<K,V> *_left;//左节点 BSTreeNode<K,V> *_right;//右节点 K _key;//节点权值 V _value; BSTreeNode(const K& key,const V& value) :_key(key) ,_value(value) ,_left(NULL) ,_right(NULL) {} };
2、搜索二叉树及其相关实现
template<class K,class V> class BSTree { typedef BSTreeNode<K,V> Node; public: BSTree() :_root(NULL) {} //非递归 Node* Find(const K& key) { return _Find(_root,key); } bool Insert(const K& key,const V& value) { return _Insert(_root,key,value); } bool Remove(const K& key) { return _Remove(_root,key); } //递归 bool InOrder() //中序遍历 --> 有序序列 { return _InOrder(_root); cout<<endl; } Node* FindR(const K& key) { return _FindR(_root,key); } bool InsertR(const K& key,const V& value) { return _InsertR(_root,key,value); } bool RemoveR(const K& key) { return _RemoveR(_root,key); } protected: //非递归 Node* _Find(Node *root,const K& key) { if(root == NULL) return NULL; Node *cur=root; if(cur->_key > key) { cur=cur->_right; } else if(cur->_key < key) { cur=cur->_left; } else { return cur; } return NULL; } bool _Insert(Node *&root,const K& key,const V& value) { if(root == NULL) { root=new Node(key,value); return true; } Node *cur=root; Node *parent=NULL; while(cur) { if(cur->_key < key) { parent=cur; cur=cur->_right; } else if(cur->_key > key) { parent=cur; cur=cur->_left; } else return false; } if(parent->_key < key) { parent->_right=new Node(key,value); parent->_right=parent; } else { parent->_left=new Node(key,value); parent->_left=parent; } return true; } bool _Remove(Node*& root,const K& key ) { if(root == NULL) return false; Node *cur=root; Node *parent=NULL; while(cur) //找节点 { if(cur->_key > key) { parent=cur; cur=cur->_left; } else if(cur->_key < key) { parent=cur; cur=cur->_right; } else //找到节点 { if(cur->_left == NULL)//左为空 { if(parent == NULL) root=cur->_right; else 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 //左右都不为空 { Node *parent=cur; Node *left=cur->_right;//右子树的最左节点 while(left->_left) { left=left->_left; } cur->_key=left->_key;//替换结点 cur->_value=left->_value; if(parent->_left == left) parent->_left=left->_left; else parent->_right=left->_right; delete left; } } return true; } return false; } //递归 bool _InOrder(Node *root) { if(root == NULL) return false; _InOrder(root->_left); cout<<root->_left<<" "; _InOrder(root->_right); return true; } Node* _FindR(Node *root,const K& key) { if(root == NULL) return NULL; if(root->_key == key) return root; else if(root->_key > key) return _FindR(root->_left,key); else return _FindR(root->_right,key); } bool _InsertR(Node *root,const K& key,const V& value) { if(root == NULL) { root=new Node(key,value); return true; } if(root->_key > key) return _InsertR(root->_left,key,value); else if(root->_key < key) return _InsertR(root->_right,key,value); else return false; } bool _RemoveR(Node *root,const K& key) { if(root == NULL) return false; if(root->_key > key) return _RemoveR(root->_left,key); else if(root->_key < key) return _RemoveR(root->_right,key); else //找到节点 { Node *del=NULL; if(root->_left == NULL) root=root->_right; else if(root->_right == NULL) root=root->_left; else { Node *parent=NULL; Node *left=root; while(left->_left) { parent=left; left=left->_left; } root->_key=left->_key; root->_value=left->_value; del=left; if(parent->_left == left) parent->_left=left->_left; else parent->_right=left->_right; delete del; return true; } } return false; } protected: Node *_root; };
3、总结:
搜索二叉树是一棵排序二叉树,可为空树。它的每一个节点都遵从搜索二叉树的性质。
搜索二叉树的中序遍历后为升序序列;其查找根据key值以及性质进行;其插入需先根据其key值找到插入的节点,随后添加节点,另外其key值唯一;
其删除节点时,需分3种情况:
(1)仅左为空;
(2)仅右为空;
(3)该节点左右皆不为空。
删除该节点,即需 找到 右子树的最左节点 或 左子树的最右节点,作为替换结点。
看完上述内容,你们掌握如何进行搜索二叉树分析的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。