接着继续来看树的一些相关的方法.
高度和节点个数
在开始计算之前, 要明白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树(典型代表就是红黑树).
红黑树就先看看原理吧, 可能还得找个视频看看才行.