当前位置： 云海天教程网 > 技术新闻 > 编程语言 > 正文

二叉树

  • 作者： 佚名     来源： 网络转载
  • 时间：2019-12-04

二叉树是一种树型结构，它的特点是每个结点至多只有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

先上代码，二叉树的结点定义：

class Node {
    public Object data;
    public Node left;
    public Node right;
}

可以看到，我们除了定义了一个结点的左孩子和右孩子，还定义一个data变量用于存储数据。我们写一段代码，来实际地创建一棵二叉树：

public class Main {
    public static void main(String args[]) {
        Node a = new Node(Integer.valueOf(1));
        Node b = new Node(Integer.valueOf(2));
        Node c = new Node(Integer.valueOf(3));
        a.left = b;
        a.right = c;
    }
}

class Node {
    public Object data;
    public Node left;
    public Node right;

    public Node(Object d) {
        this.data = d;
    }
}

我们通过这种方式，手动地创建了一个二叉树，这个二叉树，如果使用图画出来，就是以下的样子：图片1

我们称 1 是父节点，2 是左孩子结点，3 是右孩子结点。如果一个节点没有子结点，例如图中的 2 和 3 ，那这个节点也是叶子节点。如果一个结点有子结点，也可以称其为内部结点，或者是非叶子结点。

树的层次是这样定义的，把树按照上图所示的情况画出来，1 位于第一层，2 和 3 位于第二层。树中结点的最大层次称为树的高度，2 和 3 位于第二层，所以这棵树的高度就是 2。再练习一下，下面这幅图中，树有多少层？每层几个结点？树的高度是多少？共有多少个叶子结点？多少个非叶子结点？图片2

答案是：3层，第一层一个结点是 1， 第二层两个结点是2 和 3，第三层两个结点 4 和 5；树中结点的最大层数是3，所以树的高度就是3；共有三个叶子结点，分别是2， 4， 5；两个非叶结点，1和3。

二叉查找树的规则是，对于树中的任意一个结点，都满足，它的左孩子上的所有结点的值都比该结点小，而它的右孩子上的所有结点的值都比该结点大。与该结点值相同的的结点可以放在左孩子上，也可以放在右孩子上，这个可以根据实际情况灵活实现。

根据这个定义，二叉查找树的插入过程就是递进地判断待插入数据与树中结点值的大小关系，找到待插入数据应该出现的位置。

如果待插入数据比根结点的数据小，就去检查根结点的左孩子。如果左孩子不为空，就继续向下检查，如果左孩子为空，就说明已经找到应该插入数据的位置了。向右的情况则与向左的情况互为镜像，只是条件判断的符号换了一下而已。

class BinarySearchTree<t extends comparable<t>&gt; {
    public Node root;

    public boolean insert(T i) {
        if (root == null) {
            root = new Node(i);
            return true;
        }

        Node current = root;
        while (true) {
            // 如果 i 比当前结点的值小
            if (i.compareTo((T) current.data) &lt; 0) {
                if (current.left != null) {
                    current = current.left;
                } else {
                    current.left = new Node(i);
                    break;
                }
            } else {
                if (current.right != null)
                    current = current.right;
                else {
                    current.right = new Node(i);
                    break;
                }
            }
        }
        return true;
    }
}

在二叉查找树中找一个数据的思路与插入数据的思路很相似，唯一的不同之处是遇到空指针就是查找失败，说明待查找数据没在树中。程序不再列出，请读者自行实现。

好了。今天就讲这么多吧。今天的讲解少，作业多，大家一定要动起手来，多看多想多写。争取把今天讲的概念全部牢牢记住。今天的作业：

  1. 为BinarySearchTree这个类添加一个方法：
public boolean contains(T t);

检查一个数据是否在BST中，如果在，则返回true，否则返回 false。多写几个例子，测试一下你的代码对不对。

  1. 以不同的顺序往BST中插入数字，然后在纸上画一下，看看BST会变成什么样？举个例子，如果以(3, 2, 1, 5, 4, 6)的顺序插入的话，就会变成这个样子：
    图片3

尤其，一定要画一下(1, 2, 3, 4, 5, 6) 和 (6, 5, 4, 3, 2, 1)的图