Java 数据结构树 - 高级方法-柚子小站

接着继续来看树的一些相关的方法.

高度和节点个数
遍历二叉树 - 递归遍历
遍历二叉树 - 中序迭代遍历和迭代器
二叉树的实现 - 节点类BinaryNode
二叉树的实现 - 组装树的方法

高度和节点个数

在开始计算之前, 要明白Tree结构是在Node外边包装了一层, 所以可以把方法写在BinaryNode中. 首先是高度. 高度的计算方法很简单, 如果自己的数据是null, 就返回0, 否则返回两个子树中较高的值加上1(即自己的高度). 具体来写方法的时候, 由于getHeight是树接口的方法, 所以可以在其中调用根节点的获取高度的方法. 所以要编写两套方法, 一个是树接口的方法, 一个是给BinaryNode增加计算高度的方法(一个公有一个私有):

class BinaryNode<T> {

    ......

    public int getHeight() {
        return getHeight(this);
    }

    private int getHeight(BinaryNode<T> node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(getHeight(node.getLeftNode()), getHeight(node.getRightNode()));
        }
    }

}

有了这个方法之后, 还需要在BinaryTree中加上一个调用就行了:

@Override
public int getHeight() {
    if (root == null) {
        return 0;
    } else {
        return root.getHeight();
    }
}

然后是节点个数. 这个同样可以使用递归, 一棵树的总节点个数等于左树的节点个数加上右树的节点个数加上1(即自己), 所以继续在BinaryNode中编写方法:

class BinaryNode<T> {

    ......

    public int getNumberOfNodes() {
        return getNumberOfNodes(this);
    }

    private int getNumberOfNodes(BinaryNode<T> node) {
        if (node == null) {
            return 0;
        } else {
            return getNumberOfNodes(node.getLeftNode()) + 1 + getNumberOfNodes(node.getRightNode());
        }
    }
}

之后也给BinaryTree中加上一个调用:

@Override
public int getNumberOfNodes() {
    if (root == null) {
        return 0;
    } else {
        return root.getNumberOfNodes();
    }
}

这样就完成了统计节点个数的方法. 靠递归操作树确实很方便.

遍历二叉树 - 递归遍历

遍历也是操作数的核心内容. 这里分成两个部分, 一个是一次性遍历树, 还有一个是创建迭代器. 先来看看一次性遍历的方式. 一次性遍历之前说了四种方式, 先不考虑层序遍历, 而是先来看看三种序遍历. 这三种遍历实际上都是一样的, 可以通过递归操作. 来编写一下三套遍历方法, 由于是遍历, 很显然需要做点事情, 比如获取或者显示, 这里我们可以传入一个Consumer.

//前序遍历的公有方法
public void preOrderTraversal(Consumer<T> consumer) {
    this.preOrderTraversal(root, consumer);
}

//前序遍历的私有方法
private void preOrderTraversal(BinaryNode<T> node, Consumer<T> consumer) {
    if (node != null) {
        consumer.accept(node.getData());
        preOrderTraversal(node.getLeftNode(),consumer);
        preOrderTraversal(node.getRightNode(),consumer);
    }

}

//中序遍历的公有方法
public void inOrderTraversal(Consumer<T> consumer) {
    this.inOrderTraversal(root, consumer);
}


//中序遍历的私有方法
private void inOrderTraversal(BinaryNode<T> node, Consumer<T> consumer) {
    if (node != null) {
        inOrderTraversal(node.getLeftNode(),consumer);
        consumer.accept(node.getData());
        inOrderTraversal(node.getRightNode(),consumer);
    }

}

//后序遍历的公有方法
public void postOrderTraversal(Consumer<T> consumer) {
    this.postOrderTraversal(root, consumer);
}


//后序遍历的私有方法
private void postOrderTraversal(BinaryNode<T> node, Consumer<T> consumer) {
    if (node != null) {
        postOrderTraversal(node.getLeftNode(),consumer);
        postOrderTraversal(node.getRightNode(),consumer);
        consumer.accept(node.getData());
    }

}

可以看看这三个方法就是递归时候的操作先后顺序不同, 写一个小测试就可以很容易看出来差异:

public class Test {

    public static void main(String[] args) {

        BinaryTree<String> tree2 = new BinaryTree<>("cony");
        BinaryTree<String> tree4 = new BinaryTree<>("owl");
        BinaryTree<String> tree6 = new BinaryTree<>("saner");
        BinaryTree<String> tree7 = new BinaryTree<>("wood");
        BinaryTree<String> tree5 = new BinaryTree<>("sitong", tree6, tree7);
        BinaryTree<String> tree3 = new BinaryTree<>("minko", tree4, tree5);
        BinaryTree<String> tree1 = new BinaryTree<>("jenny", tree3, tree2);

        System.out.println("-------------------------前序遍历---------------------------");
        tree1.preOrderTraversal(System.out::println);
        System.out.println("---------------------------中序遍历-------------------------");
        tree1.inOrderTraversal(System.out::println);
        System.out.println("---------------------------后序遍历-------------------------");
        tree1.postOrderTraversal(System.out::println);
    }

}

遍历二叉树 - 中序迭代遍历和迭代器

如果树太深, 一般递归调用到1000左右, 栈就不够用了. 这个时候就需要考虑使用迭代的方式. 递归可以转换成栈, 只需要用一个栈结构来进行辅助, 就可以不断的向下寻找, 然后按照顺序把节点压入栈中, 之后再取出来就可以了. 所以我们的算法就是, 只要当前节点不为空, 就把自己压入栈中, 然后替换成左节点继续向下寻找. 每次弹出栈的时候, 获取其右结点, 然后再对其右节点进行相同的操作.

//迭代中序遍历的公有方法
public void inOrderIterationTraversal(Consumer<T> consumer) {
    this.inOrderIterationTraversal(root, consumer);
}

//迭代中序遍历的私有方法
private void inOrderIterationTraversal(BinaryNode<T> node, Consumer<T> consumer) {

    LinkedListStack<BinaryNode<T>> stack = new LinkedListStack<>();

    BinaryNode<T> currentNode = root;

    while (!stack.isEmpty() || currentNode != null) {

        //一路压到最左边的节点
        while (currentNode != null) {
            stack.push(currentNode);
            currentNode = currentNode.getLeftNode();
        }

        //然后弹栈, 弹一个出来看看有没有右结点
        if (!stack.isEmpty()) {
            BinaryNode<T> nextNode = stack.pop();
            //弹出之后应用函数
            consumer.accept(nextNode.getData());

            //将当前节点变换成右侧节点, 继续进行相同的操作.
            currentNode = nextNode.getRightNode();
        }
    }
}

这里得好好体会一下这种思路, 其实就是一路到底, 然后从底部开始再选左侧一路到底,最后全部遍历完, 还需要注意栈弹出和应用函数的时点, 这个就造成了顺序的不一致. 相比递归无法控制, 这里可以敏锐的发现, 外层循环:

while (!stack.isEmpty() || currentNode != null)

其实就可以充当迭代器的hasNext()判断, 然后内层每次就返回一个pop的内容, 所以可以将这个方法中的临时变量等抽取到一个迭代器类中, 编写一个内部迭代器类和相应的方法:

//覆盖接口中的方法
@Override
public Iterator<T> iterator() {
    return new BinaryTreeIterator();
}

//内部迭代器类
private class BinaryTreeIterator implements Iterator<T> {

    LinkedListStack<BinaryNode<T>> stack = new LinkedListStack<>();

    BinaryNode<T> currentNode = root;

    //外层循环充当判断条件
    @Override
    public boolean hasNext() {
        return !stack.isEmpty() || currentNode != null;
    }

    //每次返回从栈中弹出的数据, 在返回之前, 先更新currentNode
    @Override
    public T next() {
        while (currentNode != null) {
            stack.push(currentNode);
            currentNode = currentNode.getLeftNode();
        }

        if (!stack.isEmpty()) {
            BinaryNode<T> nextNode = stack.pop();

            currentNode = nextNode.getRightNode();
            return nextNode.getData();
        } else {
            throw new RuntimeException("出现意外");
        }
    }
}

遍历二叉树 - 前序迭代遍历

前序遍历指的是中-左-右, 采取这样的策略:

先把中入栈, 然后看左节点.
如果左节点是null, 把中出栈, 然后设置当前节点是右节点, 可见栈里保存的仅仅是为了获取右结点的内容
如果左节点不是null, 就把左节点push进栈, 然后将当前设置为左节点.

遍历操作的时机选择很重要, 由于是中在先, 在入栈之前就直接对其操作, 出栈的时候不再进行操作. 说实在这个还挺绕, 写的代码如下:

//迭代前序遍历的公有方法
public void preOrderIterationTraversal(Consumer<T> consumer) {
    this.preOrderIterationTraversal(root, consumer);
}

//迭代前序遍历的私有方法
private void preOrderIterationTraversal(BinaryNode<T> node, Consumer<T> consumer) {

    LinkedListStack<BinaryNode<T>> stack = new LinkedListStack<>();

    BinaryNode<T> currentNode = root;

    while (!stack.isEmpty() || currentNode != null) {
        //当前节点不为空直接应用Consumer, 然后入栈
        if (currentNode != null) {
            consumer.accept(currentNode.getData());
            stack.push(currentNode);
            currentNode = currentNode.getLeftNode();
        //当前节点为空
        } else {
            BinaryNode<T> nextNode = stack.pop();
            currentNode = nextNode.getRightNode();
        }
    }
}

后序迭代遍历有点难, 让我消化消化, 然后再考虑一下. leetCode上有一个倒转实现很不错. 不过要注意访问的时机要在最后倒转之后, 如果要在访问的时候做的话, 就比较麻烦了.

遍历二叉树 - 层序遍历

递归和迭代版本的层序遍历都还没有写. 这个遍历我自己想了一下, 发现迭代版本比较好写, 用队列比较好写. 实际的操作是, 首先将根节点入队列, 然后从队列中弹出根节点, 此时将其左右节点压入队列, 不断反复即可.

//迭代层序遍历的公有方法
public void levelOrderIterationTraversal(Consumer<T> consumer) {
    this.levelOrderIterationTraversal(root, consumer);
}

//迭代层序遍历的私有方法
private void levelOrderIterationTraversal(BinaryNode<T> node, Consumer<T> consumer) {

    LinkedQueue<BinaryNode<T>> queue = new LinkedQueue<>();

    BinaryNode<T> currentNode = root;

    //先把根节点塞进队列
    if (currentNode != null) {
        queue.enqueue(root);
    }

    //然后开始出队, 每出一个队, 就应用Consumer, 然后把当前对象的两个不为空的节点压入队. 这样就保证整个队列是按照层级排序的.
    while (!queue.isEmpty()) {
        BinaryNode<T> nextNode = queue.dequeue();
        consumer.accept(nextNode.getData());
        if (nextNode.getLeftNode() != null) {
            queue.enqueue(nextNode.getLeftNode());
        }

        if (nextNode.getRightNode() != null) {
            queue.enqueue(nextNode.getRightNode());
        }
    }
}

递归的方法有了雏形, 但是还没有想明白. 不过有了迭代的也算方便. 到目前为止, 算是写出了一个树. 果然数据结构越到后来越复杂, 还可能会需要其他数据结构的辅助. 各种遍历方法, 还有递归=栈的这种思想, 还需要好好研究一下. 现在总算弄出来一个普通的树, 就像线性数据结构一样, 也是从无序的包, 一直过渡到有序线性表. 树后边的也有好多数据结构, 现在普通的二叉树, 然后是有序的二叉查找树, 然后堆, 最后就是传说中的AVL树(典型代表就是红黑树). 红黑树就先看看原理吧, 可能还得找个视频看看才行.