如何进行搜索二叉树分析

如何进行搜索二叉树分析，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

一、搜索二叉树

1、定义：它是一棵排序二叉树，可为空树。

2、性质：

• 每个节点都有一个作为搜索依据的关键码（key），所有节点的关键码互不相同；

• 左子树上所有节点的关键码（key）都小于根节点的关键码（key）；

• 右子树上所有节点的关键码（key）都大于根节点的关键码（key）；

• 左、右子树都是二叉搜索树。

二、源代码

1、定义节点

templatestruct BSTreeNode{        BSTreeNode *_left;//左节点        BSTreeNode *_right;//右节点        K _key;//节点权值        V _value;        BSTreeNode(const K& key,const V& value)                :_key(key)                ,_value(value)                ,_left(NULL)                ,_right(NULL)        {}};

2、搜索二叉树及其相关实现

templateclass BSTree{        typedef BSTreeNode 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<_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<_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）该节点左右皆不为空。

删除该节点，即需 找到 右子树的最左节点 或 左子树的最右节点，作为替换结点。

看完上述内容，你们掌握如何进行搜索二叉树分析的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注行业资讯频道，感谢各位的阅读！