Android版本数据结构和算法（八）: 二进制排序树

在前两篇文章中，我们学习了树的一些基本概念和常见操作. 在本文中，我们将学习一种特殊形式的二叉树: Binary Sort Tree，也称为Binary Search Tree. 树），也称为二进制搜索树.

二进制排序树是具有以下属性的空树或二进制树:

也就是说，二进制排序树中的左子树节点值小于根节点值，右子树节点值大于跟随者节点值，左右子树也满足上述约定

如下所示，它是一个二进制排序树:

从二叉树的定义中可以知道二叉排序树查找算法，通过以中间顺序遍历二叉树，我们可以按降序排列二叉树中的所有元素.

如上所示，顺序遍历的结果是: 35、40、42、45、50、67

在这里，我们通过Java代码在二进制排序树中实现了几种核心方法

我们首先来看一下每个节点类的定义:

 1class TreeNode{
 2        private int data;
 3        private TreeNode leftChild;
 4        private TreeNode rightChild;
 5        private TreeNode parent;
 6
 7        public TreeNode(int data) {
 8            this.data = data;
 9            this.leftChild = null;
10            this.rightChild = null;
11            this.parent = null;
12        }
13}

这很简单. 每个节点记录有关其自身，其子代及其父代的信息.

创建二进制排序树是在其中添加元素.

总体思路是:

源代码:

 1    public TreeNode put(int data){
 2        TreeNode node = root;
 3        TreeNode parent = null;
 4        //判断二叉排序树根结点是否存在，不存在则创建
 5        if (root == null){
 6            root = new TreeNode(data);
 7            return root;
 8        }
 9        //查找其父类
10        while (node != null){
11            parent = node;//记录其父亲节点
12            if (data > node.data){
13                node = node.rightChild;
14            }else if (data < node.data){
15                node = node.leftChild;
16            }else {
17                //已经存在则直接返回
18                return node;
19            }
20        }
21        //创建新节点并插入原有树中
22        node = new TreeNode(data);
23        if (data < parent.data){
24            parent.leftChild = node;
25        }else {
26            parent.rightChild = node;
27        }
28        node.parent = parent;
29        return node;
30    }

在二元排序树中搜索相对简单，想法是:

源代码:

 1    public TreeNode searchNode(int data) {
 2        TreeNode node = root;
 3        if (node == null){
 4            return null;
 5        }else {
 6            while (node != null && data != node.data){
 7                if (data < node.data){
 8                    node = node.leftChild;
 9                }else {
10                    node = node.rightChild;
11                }
12            }
13        }
14        return node;
15    }

二进制排序树的删除操作分为4种情况:

源代码: 在这里，我们选择右子树的最小节点

 1    public void deleteNode(int data){
 2        TreeNode node = searchNode(data);
 3        if (node == null){
 4            throw new RuntimeException("未找到要删除的节点");
 5        }else {
 6            delete(node);
 7        }
 8    }
 9
10    private void delete(TreeNode node) {
11        if (node == null){
12            throw new RuntimeException("未找到要删除的节点");
13        }else {
14            TreeNode parent = node.parent;
15            //删除的节点无左右孩子
16            if (node.leftChild == null && node.rightChild == null){
17                if (parent.leftChild == node){
18                    parent.leftChild = null;
19                }else {
20                    parent.rightChild = null;
21                }
22                return;
23            }
24            //删除的节点有左无右
25            if (node.leftChild != null
26                    && node.rightChild == null){
27                if (parent.leftChild == node){
28                    parent.leftChild = node.leftChild;
29                }else {
30                    parent.rightChild = node.leftChild;
31                }
32                return;
33            }
34            //删除的节点有右无左
35            if (node.leftChild == null
36                    && node.rightChild != null){
37                if (parent.leftChild == node){
38                    parent.leftChild = node.rightChild;
39                }else {
40                    parent.rightChild = node.rightChild;
41                }
42                return;
43            }
44            //删除的结点左右都有
45            TreeNode rightMinNode = getRightMinNode(node.rightChild);
46            delete(rightMinNode);
47            node.data = rightMinNode.data;
48        }
49    }
50
51    //获取右子树最小的结点
52    private TreeNode getRightMinNode(TreeNode node) {
53        TreeNode minNode = node;
54        while (minNode != null && minNode.leftChild != null){
55            minNode = minNode.leftChild;
56        }
57        System.out.println("minNode" + minNode.data);
58        return minNode;
59    }

测试代码:

 1 SearchBinaryTree ss = new SearchBinaryTree();
 2 int[] array = {77,88,34,55,66,2,34,67,78};
 3 for (int data : array) {
 4     ss.put(data);
 5 }
 6 ss.midIter(ss.getRoot());
 7 System.out.println();
 8 SearchBinaryTree.TreeNode node = ss.searchNode(66);
 9 System.out.println("find node:"+node.getData());
10 ss.deleteNode(66);
11 SearchBinaryTree.TreeNode dnode = ss.searchNode(66);
12 if (dnode != null){
13     System.out.println("find node:"+node.getData());
14 }else {
15     System.out.println("not find node");
16 }
17 ss.midIter(ss.getRoot());

打印信息如下:

1    2 34 55 66 67 77 78 88
2    find node:66
3    not find node
4    2 34 55 67 77 78 88

在最佳情况下，二元排序树的搜索性能最佳，这与二元搜索方法相近.

但是在某些情况下，构造的二进制排序树类似于链表，其搜索性能为O（n）二叉排序树查找算法，如下所示:

绝对不是我们想要建造这样的树. 您需要调整此树以达到平衡的效果. 在这里，您需要一个二进制平衡树（AVL树）. AVL树将在后续章节中介绍. 树有这个问题.

本文主要介绍二进制平衡树和Java代码实现其核心的核心方法. 希望您能理解它与普通二叉树之间的区别以及存在的问题. 好吧，这部电影到此结束.

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