[BinaryTree]二进制搜索树（二进制搜索树，二进制排序树）

二叉搜索树（也称为二叉搜索树）是具有以下属性的空树或二叉树:

（1）如果其左子树不为空，则左子树上所有节点的值均小于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；

（3）它的左右子树也是二叉搜索树.

以下是其一些重要功能:

插入节点:

【思想1】递归

终止条件（1,2）:

1. 如果将其插入到空树中，则新创建的节点将是根节点，并且左，右子级将设置为空二叉排序树查找算法，并返回true

2. 如果等于根节点的值，则返回false

3. 如果当前值小于根节点的值，则左子树是递归的，否则右子树是递归的

 1 template<class T>
 2 bool BinarySearchTree<T>::InsertNode(BinaryTreeNode<T> * &root, T newpointer)
 3 {
 4     if (root == NULL)
 5     {
 6         root = new BinaryTreeNode<T>;
 7         root->element = newpointer;
 8         root->LeftChild = root->RightChild = NULL;
 9         return true;
10     }
11     if (newpointer == root->element)
12         return false;
13     if (newpointer < root->element)
14         return InsertNode(root->LeftChild, newpointer);
15     else
16         return InsertNode(root->RightChild, newpointer);
17 }

【思想2】非递归

1. 如果二叉树为空，则首先单独生成根节点

2. 执行搜索算法以找到插入节点的父节点

3. 确定插入的节点是其父节点的左右子节点，然后将插入的节点作为叶节点插入

注意: 新插入的节点始终是叶节点

 1 template<class T>
 2 bool BinarySearchTree<T>::InsertNode(BinaryTreeNode<T> * &root, T newpointer)
 3 {
 4     if (root == NULL)
 5     {
 6         root = new BinaryTreeNode<T>;
 7         root->element = newpointer;
 8         root->LeftChild = root->RightChild = NULL;
 9         return true;
10     }
11     BinaryTreeNode<T> *pointer = root;
12     while(pointer != NULL)
13     {
14         if (newpointer == pointer->element)
15             return false;
16         else if (newpointer < pointer->element)
17         {
18             if(pointer->LeftChild == NULL)
19             {
20                 BinaryTreeNode<T>* l = new BinaryTreeNode<T>(newpointer);
21                 l->LeftChild = l->RightChild = NULL;
22                 pointer->LeftChild = l;
23                 return true;
24             }
25             pointer = pointer->LeftChild;
26         }
27         else
28         {
29             if(pointer->RightChild == NULL)
30             {
31                 BinaryTreeNode<T>* r = new BinaryTreeNode<T>(newpointer);
32                 r->LeftChild = r->RightChild = NULL;
33                 pointer->RightChild = r;
34                 return true;
35             }
36             pointer = pointer->RightChild;
37         }
38     }
39 }

删除节点:

[想法]根据删除位置删除二叉搜索树中的节点并讨论情况

1. 删除叶节点

操作: 直接删除，并将其父节点的相应指针字段更改为空.

2. 删除的节点只有左儿子或只有右儿子

操作: 直接将节点的子树连接到节点的位置

3. 有两个子节点可用于删除节点

（1）合并和删除

（2）通过复制删除

选择一个替换项（左侧子树中的最大节点或右侧子树中的最小节点）来替换已删除节点的位置

  1 template<class T>
  2 void BinarySearchTree<T>::deleteBinarySearchTree(BinaryTreeNode<T>* root, T x)
  3 {
  4     bool find = false;
  5     int flag = 0;//标志要删除的结点是前驱结点pre的左孩子还是右孩子
  6     BinaryTreeNode<T> *pre = NULL;
  7     while (root && !find)
  8     {
  9         if (x == root->element)
 10         {
 11             find = true;
 12         }
 13         else if (x < root->element)
 14         {
 15             pre = root;
 16             root = root->LeftChild;
 17             flag = -1;
 18         }
 19         else
 20         {
 21             pre = root;
 22             root = root->RightChild;
 23             flag = 1;
 24         }
 25     }
 26     if (root == NULL)
 27     {
 28         cout << "未找到要删除元素" << endl;
 29         return;
 30     }
 31     //此时root为要删除结点
 32     
 33     //要删除结点是叶子结点
 34     if (root->isLeaf())
 35     {
 36         if (flag == 0)
 37         {
 38             delete root;
 39             root = NULL;
 40         }
 41         else if (flag == -1)
 42         {
 43             pre->LeftChild = NULL;
 44             delete root;
 45             root = NULL;
 46         }
 47         else
 48         {
 49             pre->RightChild = NULL;
 50             delete root;
 51             root = NULL;
 52         }
 53     }
 54     
 55     //要删除结点具有左右子结点
 56     else if (root->LeftChild && root->RightChild)
 57     {
 58         //复制删除，选取左子树中最大的结点替换
 59         BinaryTreeNode<T> *t = root;
 60         BinaryTreeNode<T> *s = root->LeftChild;
 61         while (s->RightChild)
 62         {
 63             t = s;
 64             s = s->RightChild;
 65         }
 66         root->element = s->element;
 67         
 68         //此时S只有左孩子，需要连接到它的前驱结点t上
 69         if (root == t)//while循环未执行
 70         {
 71             t->LeftChild = s->LeftChild;
 72         }
 73         else//while循环已执行
 74         {
 75             t->RightChild = s->LeftChild;
 76         }
 77         delete s;
 78         s = NULL;
 79     }
 80     
 81     else//要删除结点为单支子树根结点
 82     {
 83         if (flag == 0)//root为根结点
 84         {
 85             if (root->LeftChild)
 86             {
 87                 pre = root;
 88                 root = root->LeftChild;
 89                 delete pre;
 90                 pre = NULL;
 91             }
 92             else
 93             {
 94                 pre = root;
 95                 root = root->RightChild;
 96                 delete pre;
 97                 pre = NULL;
 98             }
 99         }
100         else if (flag == -1)//root为pre的左子树
101         {
102             if (root->LeftChild)//要删除结点只存在左子树
103             {
104                 pre->LeftChild = root->LeftChild;
105                 delete root;
106                 root = NULL;
107             }
108             else//要删除结点只存在右子树
109             {
110                 pre->LeftChild = root->RightChild;
111                 delete root;
112                 root = NULL;
113             }
114         }
115         else//root为pre的右子树
116         {
117             if (root->LeftChild)//要删除结点只存在左子树
118             {
119                 pre->RightChild = root->LeftChild;
120                 delete root;
121                 root = NULL;
122             }
123             else//要删除结点只存在右子树
124             {
125                 pre->RightChild = root->RightChild;
126                 delete root;
127                 root = NULL;
128             }
129         }
130     }
131 }

查找节点:

[想法]分割搜索方法:

1. 如果根节点的密钥代码等于搜索的密钥代码，则成功.

2. 否则，如果它小于根节点的键控代码，请检查其左子树；否则，请检查其左子树. 如果它大于根节点的键码二叉排序树查找算法，请检查其右子树.

二叉搜索树的高效率是，继续搜索时只需要找到两个子树之一.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167960-1.html