文档章节

常见的查找算法(五):树表查找之一 ---- 二叉查找树

o
 osc_wws45aot
发布于 2019/08/21 19:42
字数 1425
阅读 12
收藏 0

二叉查找树英语:Binary Search Tree),也称为二叉搜索树有序二叉树ordered binary tree)或排序二叉树sorted binary tree),是指一棵空树或者具有下列性质的二叉树

  1. 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  2. 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  3. 任意节点的左、右子树也分别为二叉查找树;
  4. 没有键值相等的节点。

 

二叉查找树的节点

 1     //二叉树节点
 2     static class BSTNode<T> {
 3         T data;
 4         BSTNode<T> parent;
 5         BSTNode<T> left;
 6         BSTNode<T> right;
 7 
 8         public BSTNode() {
 9             this.data = null;
10             this.left = left;
11             this.right= right;
12         }
13 
14         public BSTNode(T data) {
15             this(data,null, null);
16         }
17 
18         public BSTNode(T data, BSTNode<T> left, BSTNode<T> right) {
19             this.data = data;
20             this.left = left;
21             this.right = right;
22         }
23     }

查找操作

 1     /******************************* 查找 start *******************************/
 2 
 3     /**
 4      * 从根节点查找
 5      *
 6      * @param data 要查找的元素
 7      * @return
 8      */
 9     public boolean searchBST(T data) {
10         return searchBST(data, root);
11     }
12 
13     /**
14      * 递归查找指定元素是否在树中
15      *
16      * @param node 树中节点
17      * @param data 要查找的元素
18      * @return
19      */
20     public boolean searchBST(T data, BSTNode<T> node) {
21         if (node == null)
22             return false;
23 
24         count++;
25         int result = data.compareTo(node.data);
26 
27         if (result > 0) {
28             return searchBST(data, node.right);//往右子树查询
29         } else if (result < 0) {
30             return searchBST(data, node.left);//往左子树查询
31         } else {
32             return true;
33         }
34     }
35 
36     /**
37      * 寻找二叉树中最大的元素
38      *
39      * @return
40      */
41     public T findMax() {
42         if (isEmpty()) {
43             System.out.println("二叉树为空");
44             return null;
45         } else {
46             return findMax(root).data;
47         }
48     }
49 
50     /**
51      * 寻找二叉树中最大的元素
52      *
53      * @param node 当前的结点
54      * @return
55      */
56     public BSTNode<T> findMax(BSTNode<T> node) {
57         if (node == null) {
58             return null;
59         } else if (node.right == null) {
60             return node;
61         } else {
62             //迭代
63             while (node.right != null) {
64                 node = node.right;
65             }
66             return node;
67         }
68     }
69 
70     /**
71      * 寻找二叉树中最小的元素
72      *
73      * @return
74      */
75     public T findMin() {
76         if (isEmpty()) {
77             System.out.println("二叉树为空");
78             return null;
79         } else {
80             return findMin(root).data;
81         }
82     }
83 
84     /**
85      * 寻找二叉树中最小的元素
86      *
87      * @param node 当前节点
88      * @return
89      */
90     public BSTNode<T> findMin(BSTNode<T> node) {
91         if (node == null)
92             return null;
93         else if (node.left == null)
94             return node;
95         return findMin(node.left);
96     }
97 
98     /******************************* 查找 end *******************************/

时间复杂度分析:根据二叉查找树的性质,给定一个元素,去查找树中的元素,是从根节点那开始一层层比较节点的值,从而选定在树中查找的方向。当查找到该元素时,已经比较了n层,也就是元素在树中的层数(根节点为第一层),每层比较一个节点,然而二叉树的高度与它的节点数量有关,为log₂(n+1),所以二叉查找树的朝招时间复杂度为O(log₂n)。

插入操作

  1. 此树是空树,则直接将插入的结点作为根结点插入。
  2. 插入的值等于插入的值的根结点的数据的值,则直接返回,否则。
  3. 插入的值小于此树根结点的数据的值,则将要插入的结点的位置改变为此树左子树,否则4。
  4. 插入的值的结点的位置改变为此树右子树
 1     /******************************* 插入 start *******************************/
 2     //插入元素
 3     public void insert(T t) {
 4         root = insert(t, root);
 5     }
 6 
 7     /**
 8      * 构建一个二叉查找树
 9      *
10      * @param t    插入元素
11      * @param node 插入结点
12      * @return
13      */
14     public BSTNode<T> insert(T t, BSTNode<T> node) {
15         if (node == null)
16             return new BSTNode<T>(t, null, null);
17         int result = t.compareTo(node.data);
18         if (result < 0) {
19             node.left = insert(t, node);
20         } else if (result > 0) {
21             node.right = insert(t, node);
22         } else {
23             System.out.println("插入失败");
24         }
25         return node;
26     }
27     /******************************* 插入 end *******************************/

删除操作

对于二叉查找树的删除操作(这里根据值删除,而非结点)分三种情况:

  1. 如果结点为叶子结点(没有左、右子树),此时删除该结点不会破坏树的结构,直接删除即可,并修改其父结点指向它的引用为null
  2. 如果其结点只包含左子树,或者右子树的话,此时直接删除该结点,并将其左子树或者右子树设置为其父结点的左子树或者右子树即可,此操作不会破坏树结构
  3. 当结点的左、右子树都不空的时候,一般的删除策略是用其右子树的最小数据(容易找到)代替 要删除的结点数据递归删除该结点(此时为null)
 1     /******************************* 删除 start *******************************/
 2     /**
 3      * 删除元素
 4      * @param t
 5      */
 6     public void remove(T t) {
 7         root = remove(t, root);
 8     }
 9 
10     /**
11      * 删除某个位置的结点
12      * @param t
13      * @param node
14      * @return
15      */
16     public BSTNode<T> remove(T t, BSTNode<T> node) {
17         if (node == null) {
18             System.out.println("删除失败");
19             return node;
20         }
21         int result = t.compareTo(node.data);
22         if (result > 0) {
23             node.right = remove(t, node.right);
24         } else if (result < 0) {
25             node.left = remove(t, node.left);
26         } else if (node.left != null && node.right != null) {
27             node.data = findMin(node.right).data;
28             node.right = remove(node.data, node.right);
29         } else {
30             node = (node.left != null) ? node.left : node.right;
31         }
32         return node;
33     }
34     /******************************* 删除 end *******************************/

遍历二叉查找树(先序遍历):

1     public void preOrder(BSTNode node) {
2         if (node != null) {
3             System.out.print(node.data + " ");
4             preOrder(node.left);
5             preOrder(node.right);
6         }
7     }

测试代码:

 1     public static void main(String[] args) {
 2         BSTNode<Integer> node3 = new BSTNode<>(3);
 3         BSTNode<Integer> node1 = new BSTNode<>(1);
 4         BSTNode<Integer> node4 = new BSTNode<>(4, node3, null);
 5         BSTNode<Integer> node2 = new BSTNode<>(2, node1, node4);
 6         BSTNode<Integer> node8 = new BSTNode<>(8);
 7         BSTNode<Integer> root = new BSTNode<>(6, node2, node8);
 8 
 9         BSTree bsTree = new BSTree<>();
10         bsTree.root = root;
11         bsTree.preOrder(bsTree.root);
12         //bsTree.remove(4);
13         //System.out.println();
14         //bsTree.preOrder(bsTree.root);
15         bsTree.searchBST(3);
16         System.out.println("查找次数:" + count);
17     }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

如何在Ruby中生成随机字符串 - How to generate a random string in Ruby

问题: I'm currently generating an 8-character pseudo-random uppercase string for "A" .. "Z": 我目前正在为“ A” ..“ Z”生成一个8个字符的伪随机大写字符串: value = ""; 8.times{......

法国红酒甜
今天
20
0
Python中的mkdir -p功能[重复] - mkdir -p functionality in Python [duplicate]

问题: This question already has an answer here: 这个问题在这里已有答案: How can I safely create a nested directory? 如何安全地创建嵌套目录? 25 answers 25个答案 Is there a way...

技术盛宴
今天
21
0
原价500元的认证证书,限时免费考取!

本文作者:y****n 百度云智学院致力于为百度ABC战略(人工智能、大数据、云计算)提供人才生态体系建设,包括基于百度ABC、IoT的课程体系,整合百度优势技术能力的深度学习技术、Apollo无人车...

百度开发者中心
昨天
17
0
在virtualenv中使用Python 3 - Using Python 3 in virtualenv

问题: Using virtualenv , I run my projects with the default version of Python (2.7). 使用virtualenv ,我使用默认版本的Python(2.7)运行项目。 On one project, I need to use Pyth......

富含淀粉
今天
16
0
Python的__init__和self是做什么的? - What __init__ and self do on Python?

问题: I'm learning the Python programming language and I've came across something I don't fully understand. 我正在学习Python编程语言,遇到了一些我不太了解的东西。 In a method ......

javail
今天
15
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部