# 二叉搜索树 (BST) 的创建以及遍历

1、BST 的总体结构：

BST 类代码如下：

``` 1     public class BST<Tkey, Tval> where Tkey : IComparable
2     {
3         private Node root;
4
5         public class Node
6         {
7             private Tkey key;
8             private Tval val;
9             private int n;
10
11             public Node(Tkey key, Tval val, int n)
12             {
13                 this.key = key;
14                 this.val = val;
15             }
16             public Tkey Key { get => key; }
17             public Tval Val { get => val; set => val = value; }
18             public Node left { set; get; }
19             public Node right { set; get; }
20             public int N { set => n = value; get => n; }
21         }
22
23        public int Size()
24        public void Insert(Tkey, Tval)
25        public void Delete(Node x)
26        public void InorderTraversal()
27     }```

2、插入新节点

``` 1 public void Insert(Tkey key, Tval val)
2 {
3     // 创建私有方法，便于传入参数 root
4     root = Insert(root, key, val);
5 }
6
7 private Node Insert(Node x, Tkey key, Tval val)
8 {
9     // 若节点为空（无根节点），则创建新的节点
10     if (x == null)
11     {
12         return new Node(key, val, 1);
13     }
14
15     // 比较键的大小，小于返回 -1 ， 大于返回 1， 等于返回 0
16     int t = key.CompareTo(x.Key);
17
18     if (t > 0) { x.right = Insert(x.right, key, val); }
19     else if (t < 0) { x.left = Insert(x.left, key, val); }
20     else { x.Val = val; }
21
22     x.N = Size(x.left) + Size(x.right) + 1;
23
24     return x;
25 }```

3、计算以该节点为根的节点总节点数

```1     public int Size(Node x)
2     {
3         if (x == null) { return 0; }
4         return Size(x.left) + Size(x.right) + 1;
5     }```

4、遍历

```1     public void InorderTraversal_recursive(Node x)
2     {
3         if (x == null) { return; }
4
5         InorderTraversal(x.left);
6         Console.Write(x.Key + "   ");
7         InorderTraversal(x.right);
8     }```

``` 1     public void  InorderTraversal_stack()   // 利用堆栈先进后出的特性， 先将全部左节点压入，然后输出左节点，每输出一个左节点后切换到右节点， 继续输出
2     {
3         Stack<Node> nodeStack = new Stack<Node>();
4         Node currentNode = root;
5
6         while (nodeStack != null || currentNode != null)  // 此处判断 curretNode 非空，是因为首次循环 nodeStack 为空， 避免了在循环外添加根节点。
7         {
8             while (currentNode != null)  //  将全部左节点压入堆栈
9             {
10                 nodeStack.Push(currentNode);
11                 currentNode = currentNode.left;
12             }
13             if (nodeStack.count != 0)
{
14                 currentNode = nodeStack.Pop();
15                 Console.Write(currentNode.key + "   ");
16                 currentNode = currentNode.right; // 切换到右节点
}
17         }
18     }```

``` 1     // 利用队列先进先出的特性， 层层输出
2     public void LevelTraversal()
3     {
4         Queue<Node> nodeQueue = new Queue<Node>();
5         if (root != null) { nodeQueue.Enqueue(root); }
6
7         while (nodeQueue.Count() != 0)
8         {
9             Node currentNode = nodeQueue.Dequeue();
10             Console.Write(currentNode.Key + "   ");
11             // 将去除节点的子节点添加到队列的尾部
12             if (currentNode.left != null) { nodeQueue.Enqueue(currentNode.left); }
13             if (currentNode.right != null) { nodeQueue.Enqueue(currentNode.right); }
14         }
15     }            ```

5. 证明二叉树为搜索树

``` 1     public bool isBST()
2     {
3         Stack<Node> nodeStack = new Stack<Node>();
4         Node currentNode = root;
5         Node preNode = null;
6
7
8         if (nodeStack.Count() != 0 || currentNode != null)
9         {
10             while (currentNode != null)
11             {
12                 nodeStack.Push(currentNode);
13                 currentNode = currentNode.left;
14             }
15
16             if (nodeStack.Count() != 0)
17             {
18                 currentNode = nodeStack.Pop();
19                 // 此处需要判断 preNode 等于空的情况（当进行首个节点判断时，preNOde 为空， 跳过判断）
20                 if (preNode != null && currentNode.Key.CompareTo(preNode.Key) <= 0) { return false; }
21
22                 preNode = currentNode;
23                 currentNode = currentNode.right;
24             }
25         }
26         return true;
27     }```

61 篇文章16 人订阅

0 条评论

## 相关文章

### 【Java入门提高篇】Day33 Java容器类详解（十五）PriorityQueue详解

今天要介绍的是基础容器类（为了与并发容器类区分开来而命名的名字）中的另一个成员——PriorityQueue，它的大名叫做优先级队列，想必即使没有用过也该有所...

14410

19560

239100

315100

### hihocoder-平衡树·SBT

http://hihocoder.com/problemset/problem/1337 #1337 : 平衡树·SBT 时间限制:10000ms 单点时限:...

27950

### 数字的陷阱

Java中对数字的处理，如四舍五入，如加减乘除，貌似是一个很基础很简单的知识点，但是如果你没有对他进行充分了解，很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

19880

11730

21150