Java 数据结构树 - 概念与基础实现-柚子小站

Java的HashMapn内部的实现是数组加上红黑树. 所以想要真正的了解散列表, 原来自行实现的那种不是最好的. 现在就是要重新杀到树了, 来看看这种数据结构. 上次看算法第四版的时候, 图和树只是略略看过, 那本书有点太深, 直接看的话有点懵逼, 现在第二次, 感觉就好多了. 还是那句话, 看不懂就硬看加实践, 多来几次, 也就明白了.

树和相关概念
二叉树
树的接口
二叉树的实现 - 节点类BinaryNode
二叉树的实现 - 组装树的方法
二叉树的实现 - 访问器和赋值方法及辅助方法

树和相关概念

树和之前学过的数据结构最大的区别就是, 树不是线性的, 而是有层次的. 当然也可以说我们的散列表也叫作有层次, 但实际上, 散列表这种线性组合起来的数据结构, 依然带有线性的色彩. 而树就完全不同, 是彻底的层次结构. 树是一组由(边edge)相连的节点(node), 边表示层之间的联系. 没有父节点的节点叫做根节点. 没有子节点的节点叫做叶子节点. 有同一个父节点的子节点是兄弟节点, 也称为后代. 父节点也称为他们的祖先. 没有规定每个父节点有几个子节点的树叫做一般树. 规定了有N个节点的, 叫做N叉树. 任意节点和其后代组成一颗所在的树的子树, 因此二叉树可以很方便的用递归描述. 比如常见的树的高度, 等于其最高的子树+1, 这就可以用递归表示. 很多数据结构比如Python的列表, 只要进行嵌套, 就可以很容易的组成一个树结构. 并非一定要使用一个Node对象. 只要能装入N个内容的容器嵌套, 都可以组成树形结构, 当然好不好操作就是另外一回事情了.

二叉树及其操作

二叉树其实用脑子简单想一下, 就知道很类似于二分查找的概念, 每次都分为两个. 所以是一种常见的树形数据结构. 二叉树如果在最低一层全部节点都不是null, 就是一个满二叉树. 不满的情况下, 最下边一层从左至右填充, 而且倒数第二层是满的, 叫做完全树. 所有节点都有两个高度完全相等的子树, 叫做完全平衡二叉树, 也就是满树. 如果高度相差<=1, 叫做平衡二叉树, 一般通常意义上的平衡二叉树就是指此种情况. 子树高度<=1的节点叫做平衡节点. 最关键的操作, 就来看一下遍历. 这个不像线性表, 遍历是线性的,而是有着各种方法. 由于二叉树可以很好的用递归来遍历, 所以很有意思:

前序遍历: 先访问根节点的内容, 再访问左子树->右子树(或者右->左), 这种方式,二叉树的实际访问可以想象的到, 是会沿着最左边一路到底, 然后在倒数第二层访问其左侧, 然后又会一路到底, 整个二叉树的左半部分会先于右侧访问完毕, 左上方的元素比右下的先访问完毕.
中序遍历: 先访问左节点的内容, 然后是根节点, 最后是右节点. 这种方式实际是从二叉树最左下开始, 然后先向上再向右访问, 中间节点在整棵树的中间访问, 左侧比右侧先访问.
后序遍历: 先访问左, 再访问右, 最后访问中间节点. 这种方式是从左树最下边一层逐步向上收回到根, 然后右树也收回到根, 最后访问根节点.
层序遍历: 这种有两种区分, 一种是每次访问一层的节点, 全部访问完毕之后, 再访问下一层的节点, 这叫做广度优先遍历(breadth-first traversal), 还有一种是先探查完一个子树再探查另一个, 结果就是第一次就会到达某个叶子节点, 叫做深度优先遍历(depth-first traversal).

其中广度和深度优先是最值得讨论的. 下边就来看看接口吧.

树的接口

树作为一个数据结构, 常用的就是获取根节点, 是否为空, 获取高度和节点的数量, 现在能想到的一般树也就这些内容. 然后就是遍历这个树, 先设置出来吧:

public interface TreeInterface<T>  {

    T getRootData();

    int getHeight();

    int getNumberOfNodes();

    boolean isEmpty();

    void clear();
}

public interface TreeIterator<T> {

    Iterator<T> iterator();

}

目前我们最关心二叉树, 所以创建一个二叉树接口来继承上边两个接口:

public interface BinaryTreeInterface<T> extends TreeInterface<T>, TreeIterator<T> {

    void setTree(T rootData);

    void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree);

}

由于不能强制指定构造方法, 因此这里设置了两个方法, 一个创建只有一个节点的树, 一个使用根节点和两棵子树创建一个树. 这里即使是单个节点, 我们也将其视作一棵只有一个节点的树, 这样操作就比较简单. 当然, 一般树也是应用很广泛的, 最常见的就是语法树, 只要定义一个符合语法规则, 就可以使用程序来解析树, 一个节点的子节点可以是一批树. 不过说实在自己写一个Parse确实不容易. 此外数据结构堆基于二叉树, 每个节点都是一个Comparable对象, 每个节点的数据对象不小于(或者不大于)其后代的所有对象, 而且是一个完全二叉树. 二叉查找树则是节点中的数据大于左子树中的所有数据, 小于右子树中的所有数据(或者相反)的一棵二叉树.

二叉树的实现 - 节点类BinaryNode

在这里, 我们把树定义为指向一棵树的根节点的数据类型. 每个节点, 我们定义一个特殊的类. 类似于链表中的节点Node, 我们这次可以将节点类BinaryNode写在包里, 而不是内部类. 首先思考一下, 每个节点内部至少需要有三个数据, 一个左引用指向左节点, 一个右引用指向右节点, 还有一个引用来保存数据对象. 因此可以写出类如下:

class BinaryNode<T> {

    private T data;
    private BinaryNode<T> leftNode;
    private BinaryNode<T> rightNode;

    public BinaryNode() {
        this(null);
    }

    public BinaryNode(T data) {
        this.data = data;
    }

    public BinaryNode(T data, BinaryNode<T> leftNode, BinaryNode<T> rightNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public BinaryNode<T> getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(BinaryNode<T> leftNode) {
        this.leftNode = leftNode;
    }

    public BinaryNode<T> getRightNode() {
        return rightNode;
    }

    public void setRightNode(BinaryNode<T> rightNode) {
        this.rightNode = rightNode;
    }

    public boolean isLeaf() {
        return leftNode == null && rightNode == null;
    }
}

这个节点类创建了各种构造器, 可以直接使用数据对象或者创建无对象的节点. 然后是各种setter和getter方法. 加上了一个判断是不是叶子节点的方法. 可能后续还需要扩充这个节点的方法. 现在先来看看在节点的基础上创建二叉树数据结构. 回到前边的概念, 我们将树定义为指向一棵二叉树的根节点, 所以树数据结构中, 节点只需要一个, 就是根节点.

二叉树的实现 - 组装树的方法

按照之前的定义, 树里边只需要一个节点即可. 先来把最基础的类和构造器写出来:

public class BinaryTree<T> implements BinaryTreeInterface<T> {

    private BinaryNode<T> root;

    public BinaryTree() {
        root = null;
    }

    public BinaryTree(T data) {
        root = new BinaryNode<>(data);
    }

    public BinaryTree(T data, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
        privateSetTree(data, leftTree, rightTree);
    }
    
    //辅助方法, 将两棵树中的根节点, 设置到当前树的根节点的左右分支上
    private void privateSetTree(T data, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
        root = new BinaryNode<>(data);
        root.setLeftNode(leftTree.root);
        root.setRightNode(rightTree.root);
    }
    
}

这其中仅有一个指向根节点的引用. 然后就是构造器, 由于在包中, 可以直接访问类的root对象, 所以可以编写一个私有方法, 用来辅助设置相关的节点, privateSetTree实际上就是将两棵树挂在同一个节点下, 构造一棵新树. 然后需要逐个实现接口中的方法. 先是BinaryTreeInterface中的两个, 也可以使用这个私有方法:

//这个方法本质上和构造器一样, 新建一个节点. 原来的树会丢失
@Override
public void setTree(T rootData) {
    root = new BinaryNode<>(rootData);
}

//内部调用privateSetTree, 需要强制转型, 这个转型是安全的
@Override
public void setTree(T rootData, BinaryTreeInterface<T> leftTree, BinaryTreeInterface<T> rightTree) {
    privateSetTree(rootData, (BinaryTree<T>) leftTree, (BinaryTree<T>) rightTree);
}

然后这里有两个问题需要解决. 首先是复制的问题. 由于我们目前的类只是单纯连接, 可能无法阻止原来对一些树的引用, 还可能客户需要将两棵树都挂在同一棵树下边, 所以需要编写一个复制的方法.

树的复制 - 递归复制节点

所谓复制也很简单, 就是给BinaryNode中新增加一个方法, 先复制当前节点, 再复制左子树和右子树的节点, 这实际上是一个Composite模式的递归调用方法:

public BinaryNode<T> copy() {
    BinaryNode<T> newRoot = new BinaryNode<>(data);

    if (leftNode != null) {
        newRoot.setLeftNode(leftNode.copy());
    }

    if (rightNode != null) {
        newRoot.setRightNode(rightNode.copy());
    }
    return newRoot;
}

当这个方法被调用时, 会发生什么呢? 以一个两层三个节点的树为例, 会先创建一个和根节点的数据一样的节点, 然后根据代码, 会先执行leftNode.copy() , 得到左节点的一个新的复制对象, 然后将其设置到新节点的左, 右侧也是一样. 很显然, 如果再多一层, 第二层会先创建一个以自己相同的节点, 然后继续往下复制第三层. 所以全部结束之后, 实际上得到一个复制的整颗子树的根节点引用. 可见Composite模式之妙.

避免外部访问

目前的方法, 可以组装一棵新树, 但是作为参数的leftTree或者rightTree的root节点, 也指向被连接的子树. 所以很显然, privateSetTree方法需要改进, 将一棵树连接到新树上之后, 需要将原来的树对象的root节点置为null. 这样原来的树对象无法访问新树. 此外还要注意左子树和右子树不能是同一颗. 改进的privateSetTree方法如下:

private void privateSetTree(T data, BinaryTree<T> leftTree, BinaryTree<T> rightTree) {
    root = new BinaryNode<>(data);

    if ((leftTree != null) && !leftTree.isEmpty()) {
        root.setLeftNode(leftTree.root);
    }

    if ((rightTree != null) && !rightTree.isEmpty()) {
        if (rightTree != leftTree) {
            root.setRightNode(rightTree.root);
        //如果左右子树是同一棵, 就复制一份挂载上去.
        } else {
            root.setRightNode(rightTree.root.copy());
        }
    }

    //全部挂载完毕之后, 将参数的两个树清空, 这样便无法在外部访问新树
    if ((leftTree != null) && leftTree != this) {
        leftTree.clear();
    }
    
    if ((rightTree != null) && rightTree != this) {
        rightTree.clear();
        
    }

}

当然, 此时还没有编写.clear()方法, 但是这个方法的作用是清空, 所以可以先用上.

二叉树的实现 - 访问器和赋值方法及辅助方法

这里的一些方法主要是getter和setter方法, 以及isEmpty()和isClear()方法, 主要是如下:

@Override
public T getRootData() {
    if (isEmpty()) {
        throw new RuntimeException("树已经为空");
    } else {
        return root.getData();
    }
}

public void setRootData(T rootData) {
    root.setData(rootData);
}

@Override
public boolean isEmpty() {
    return root == null;
}

@Override
public void clear() {
    root = null;
}

public BinaryNode<T> getRoot() {
    return root;
}

public void setRoot(BinaryNode<T> root) {
    this.root = root;
}

目前, 去掉迭代器的部分, 还有两个方法没有实现, 一个是int getHeight(), 一个是int getNumberOfNodes(). 写到这里今天先喘口气, 在脑子里仔细想一想目前为止的树结构. 可以说, 我们的关键是依赖于将BinaryNode节点有效的连接, 然后在外层包了一个指向根节点的类, 就是树. 所以本质上直接操作节点, 和操作树也没有本质的区别, 这个数据结构在脑子里先想一晚. 后边的获取高度在当时看CS61A的时候自己用Python写出来过, 回头看看, 这个嵌套列表实际上相当于一般树, 即树的每个节点都是一个列表, 第一项是值, 第二项是一个树的列表, 需要用递归的方式, 思路就是之前说的, 等于最大高度的子树加上1:

def height(tree):
    # 如果没有子节点, 就是1
    if len(branches(tree)) == 0:
        return 1
    # 否则返回其所有子树的最大值加上1
    else:
        return max([height(t) for t in branches(tree)]) + 1

很显然这里也需用递归的方式, 设计模式中的Composite模式最典型的就是树形结构, 只要是嵌套的同种数据类型, 都可以使用Composite模式. 此外还有递归的数节点的方式, 很显然, 一个树的总节点等于左子树的节点数加上右子树的节点数再加1. 这两个加上遍历树的方式, 明天再研究了, 今晚现在脑子里好好想想树, 毕竟树之后的内容都没怎么学好.