二叉查找树

  在处理数据的时候,二叉查找树是排好序的树,可以很快的实现数据的查找。其定义为:二叉查找树或者是空树,或者是满足如下性质的二叉树:

  1. 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
  2. 若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
  3. 左、右子树本身又各是一棵二叉查找树。

上述性质简称二叉查找树性质(BST性质),故二叉查找树实际上是满足BST性质的二叉树。
对二叉查找树的遍历可以分为三种:中序遍历,前序遍历,后序遍历。其中中序遍历可以得到一个递增的序列。

  二叉查找树的实现需要节点Node类,包含了一个int类型的数据(一般情况定义为object类型)和两个分别指向两个分支的Node变量以及一个输出Node中数据的方法,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node
{
public int element;
public Node left;
public Node right;
public Node() { }
public Node(int value)
{
element = value;
left = null;
right = null;
}
public void DisplayNode()
{
Console.Write(element+" ");
}
}

有了节点我们就可以构建二叉查找树了,可以用一个insert方法挨个插入节点构建二叉查找树。在插入时需要先判断是否已存在包含相同数据的节点,若已存在,提示不可插入。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public void insert(int val )
{
if (SearchNode(val ))
Console.WriteLine("sorry ,bst included the node ,please change it");
else
{
Node newnode = new Node(val);
if (root == null)
{
root = newnode;
}
else
{
Node currentNode = root;
while (true)
{
parent = currentNode;
if (newnode.element < currentNode.element)
{
currentNode = currentNode.left;
if (currentNode == null)
{
parent.left = newnode;
break;
}
}
else if (newnode.element > currentNode.element)
{
currentNode = currentNode.right;
if (currentNode == null)
{
parent.right = newnode;
break;
}
}
}
}
}
}

构建好二叉树就可以使用它了,二叉查找树最大的优点是数据是排好序的,查找很快。我们可以定义一个search方法来实现指定数据的查找,若找到,返回true;否者返回false。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public bool SearchNode( int val )
{
if (root != null)
{
Node currentNode = root;
Node value = new Node(val);
if (currentNode == value)
{
return true;
}
while (true)
{
if (value.element < currentNode.element)
{
if (currentNode.left == null)
{
break;
}
currentNode = currentNode.left;
}
else if (value.element > currentNode.element)
{
if (currentNode.right == null)
{
break;
}
currentNode = currentNode.right;
}
else
break;
}
if (currentNode.element != value.element)
{
return false;
}
else
return true;
}
else
return false;
}

在二叉查找树中,最大值与最小值的查找是最简单的,查找最大值只需要找到二叉查找树沿右子树到最远的那个节点,查找最小值只需要找到最左节点。
在二叉查找树中,删除操作要稍微麻烦一点,需要考虑四种情况。
1.要删除的节点是二叉查找树的叶子(即没有子树)。
2.要删除的节点有左子树,没有右子树。
3.要删除的节点有右子树,没有左子树。
4.要删除的节点有左右子树。
以上情况还要考虑待删除的节点属于左子树还是右子树。
最简单的是第一种情况,只需要将父节点的左子树或者右子树置空,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (currentNode.left==null&&currentNode.right==null)
{
if (currentNode==root)
{
root = null;
}
else if (currentNode.element < parent.element)
{
parent.left = null;
}
else if (currentNode.element > parent.element)
{
parent.right = null;
}
}

第二种情况和第三种情况属于一类,将待删除的节点存在的那一个子节点代替待删除的节点即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//this Node only have left sub
else if (currentNode.left!=null&&currentNode.right==null)
{
if (currentNode.element < parent.element)
{
parent.left = currentNode.left;
}
else
parent.right = currentNode.left;
}
//this Node only have right sub
else if (currentNode.left==null&&currentNode.right!=null)
{
if (currentNode.element < parent.element)
{
parent.left = currentNode.right;
}
else
parent.right = currentNode.right;
}

第四种情况要复杂一点。当我们删除掉一个具有左右子树的节点时,需要调整二叉查找树以使它保持二叉查找树的特性。删除的节点位置我们可以用两种方式来填充。中序遍历的前驱节点或中序遍历的后继节点。

中序遍历的前驱节点:该节点的左子树的最右子节点。

中序遍历的后继节点:该节点的右子树的最左子节点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//this Node have two subs
else if (currentNode.left!=null&&currentNode.right!=null)
{
Node insteadNodeParent ; //the parent of the node that will instead currentNode
Node insteadNode ;//the node that will instead currentNode
insteadNodeParent=currentNode;
insteadNode = currentNode.left;
while(insteadNode.right!=null)//find the insteadNodeParent and the insteadNode
{
insteadNodeParent = insteadNode;
insteadNode = insteadNode.right;
}
if (currentNode.element
{
if (insteadNodeParent != currentNode)
{
insteadNode.right = currentNode.right;
insteadNode.left = currentNode.left;
parent.left = insteadNode;
insteadNodeParent.right = null;
}
else
{
insteadNode.right = currentNode.right;
parent.left = insteadNode;
insteadNodeParent.left = null;
}
}
else if (currentNode.element>parent.element)//when currentNode in the right sub
{
if (insteadNodeParent != currentNode)
{
insteadNode.right = currentNode.right;
insteadNode.left = currentNode.left;
parent.right = insteadNode;
insteadNodeParent.right = null;
}
else
{
insteadNode.right = currentNode.right;
parent.right = insteadNode;
insteadNodeParent.left = null;
}
}

完成了节点的删除,再实现对二叉查找树的三种方式的遍历。由于二叉查找树自身的特性,递归实现遍历是很方便的操作。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
///
/// preorder traverse
///
///
public void PreOrder(Node n)
{
if (n!=null)
{
n.DisplayNode();
PreOrder(n.left);
PreOrder(n.right);
}
}
///
/// inorder traverse
///
///
public void InOrder(Node n)
{
if (n!=null)
{
InOrder(n.left);
n.DisplayNode();
InOrder(n.right);
}
}
///
/// postorder traverse
///
///
public void PostOrder(Node n)
{
if (n!=null)
{
PostOrder(n.left);
PostOrder(n.right);
n.DisplayNode();
}
}

对二叉查找树的基本操作也就这些了,要记住的是它和散列表的比较。

散列表的优点是查询更快,利用散列函数,查询时间为常数1,这是最快的查询速度。
二叉树的查询速度也很快,为log(n),慢于散列表。

但是二叉树相对于散列表的优点是,其中元素是排序的,而散列表不是排序的。
在空间不受限制时,且不需要高频率的排序操作时,二叉查找树不如散列表。反之二叉查找树优于散列表。

-------------本文结束 感谢您的阅读-------------

本文标题:二叉查找树

文章作者:nero

发布时间:2013年04月24日 - 19:04

最后更新:2017年11月20日 - 14:11

原始链接:http://erdao123.oschina.io/nero/2013/04/24/NET/二叉查找树/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。