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

二叉搜索树(Binary Search Tree) : 属于二叉树,其中每个节点都含有一个可以比较的键(如需要可以在键上关联值), 且每个节点的键都大于其左子树中的任意节点而小于右子树的任意节点的键。

1、BST 的总体结构:

主要的几种变量以及方法如上图所示,主要有插入、排序、删除以及查找等方法。键采用泛型,继承 IComparable, 便于比较。

其中节点的类如下图:

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     }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day33 Java容器类详解(十五)PriorityQueue详解

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

14410
来自专栏编程札记

java之hashtable和hashmap

19560
来自专栏拭心的安卓进阶之路

Java 集合深入理解(13):Stack 栈

今天心情不错,再来一篇 Stack ! 数据结构中的 栈 数据结构中,栈是一种线性数据结构,遵从 LIFO(后进先出)的操作顺序,所有操作都是在顶部进行 ...

239100
来自专栏静默虚空的博客

[算法题] 计算结构体的大小

计算结构体的大小      C代码中定义的结构体是一块连续内存,各成员按照定义的顺序依次在其中存放。编译器在完成语法分析后,需要计算它的大小,然后才能正确地为结...

315100
来自专栏ml

hihocoder-平衡树·SBT

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

27950
来自专栏java达人

数字的陷阱

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

19880
来自专栏前端迷

前端常见算法的JS实现

11730
来自专栏软件开发 -- 分享 互助 成长

C++ STL之排序算法

排序算法和查找算法差不多,也涉及到迭代器区间问题,关于该问题的注意事项就不在啰嗦了 一、全部排序sort、stable_sort sort是一种不稳定排序,使用...

21150
来自专栏码匠的流水账

聊聊flink的OperatorStateBackend

flink-runtime_2.11-1.7.0-sources.jar!/org/apache/flink/runtime/state/OperatorSta...

30620
来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

95930

扫码关注云+社区

领取腾讯云代金券