- 所谓二叉树的遍历就是把所有元素都访问一遍
- 线性数据结构的遍历比较简单;分为正序遍历、逆序遍历
- 根据节点访问顺序的不同,二叉树的常见遍历方式有以下 4种.
前序遍历
- 其访问顺序是,先访问根节点,再前序遍历左子树,然后再前序遍历右子树
前序遍历-非递归
- 利用栈实现一
- 设置 node =root
- 循环执行一下操作
- 如果 node != null
对 node 进行访问
将 node.right 入栈
设置 node = node.left - 如果 node == null
如果栈为空,结束遍历
如果栈不为空,弹出栈顶元素并赋值给 node
- 如果 node != null
- 利用栈实现二
1.将 root 入栈
2.循环执行一下操作,直到栈为空- 弹出栈顶节点 top,进行访问
- 将 top.right 入栈
- 将 top.left 入栈
前序遍历-递归
- 利用递归实现: 分别递归遍历左子树和右子树
public void preorder(BinarySearchTree.Visitor<E> visitor) {
if (visitor != null) {
this.preorder(this.root, visitor);
}
}
private void preorder(BinarySearchTree.Node<E> node, BinarySearchTree.Visitor<E> visitor) {
if (node != null && !visitor.stop) {
visitor.stop = visitor.visit(node.element);
this.preorder(node.left, visitor);
this.preorder(node.right, visitor);
}
}
中序遍历
- 中序遍历访问顺序是,中序遍历左子树,在访问跟节点,再中序遍历右子树
- 二叉搜索树的中序遍历结果是升序或者降序的
中序遍历-非递归
- 利用栈实现
1.设置 node=root
2.循环执行以下操作- 如果 node != null
将 node入栈
设置 node=node.left - 如果 node == null
如果栈为空,结束遍历
如果栈不为空,弹出栈顶元素并赋值给 node
对 node 进行访问
设置 node = node.right
- 如果 node != null
中序遍历-递归
public void inorder(BinarySearchTree.Visitor<E> visitor) {
if (visitor != null) {
this.inorder(this.root, visitor);
}
}
private void inorder(BinarySearchTree.Node<E> node, BinarySearchTree.Visitor<E> visitor) {
if (node != null && !visitor.stop) {
this.inorder(node.left, visitor);
if (!visitor.stop) {
visitor.stop = visitor.visit(node.element);
this.inorder(node.right, visitor);
}
}
}
后序遍历
- 后序遍历访问顺序是 后序遍历左子树、后序遍历右子树、根节点
后序遍历-非递归
- 利用栈实现
1.将 root 入栈
2.循环执行一下操作,知道栈为空- 如果栈顶节点是叶子节点或者上一次访问的节点是栈顶节点的子节点
弹出栈顶节点,进行访问 - 否则
将栈顶节点的 right 、left 按顺序入栈
- 如果栈顶节点是叶子节点或者上一次访问的节点是栈顶节点的子节点
后序遍历-递归
public void postorder(BinarySearchTree.Visitor<E> visitor) {
if (visitor != null) {
this.postorder(this.root, visitor);
}
}
private void postorder(BinarySearchTree.Node<E> node, BinarySearchTree.Visitor<E> visitor) {
if (node != null && !visitor.stop) {
this.postorder(node.left, visitor);
this.postorder(node.right, visitor);
if (!visitor.stop) {
visitor.stop = visitor.visit(node.element);
}
}
}
层序遍历
- 访问顺序是从上到下、从左到右一次访问每一个节点
- 使用队列实现
1.将根节点入队
2.循环执行一下操作,直到队列为空
将队头节点 A 出队,进行访问
将 A 的左子节点入队
将 A 的右子节点入队
public void levelOrder(BinarySearchTree.Visitor<E> visitor) {
if (this.root != null && visitor != null) {
Queue<BinarySearchTree.Node<E>> queue = new LinkedList();
queue.offer(this.root);
while(!queue.isEmpty()) {
BinarySearchTree.Node<E> node = (BinarySearchTree.Node)queue.poll();
if (visitor.visit(node.element)) {
return;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
}
访问器的实现
- 我们对二叉树遍历的目的就是取出里面的数据来用,具体要怎么使用需要调用者实现,二叉树内部并不知道外部用二叉树里面的数据做什么用,所以当我们实现二叉树的遍历的时候需要调用者传入一个回调,用这个回调把遍历到的数据回调给调用者。
- 有时候调用者在遍历二叉树的时候在某种条件下想终止遍历,比如说取到了自己想要的数据,那么二叉树就没有必要在继续遍历下去,这样的话,我们还需要在回调对象里有个标志,来标志是否要停止二叉树的遍历
- 针对上面的两点需求我们实现下面的访问器,
在二叉树的内部定义一个抽象类,这个抽象类中定义一个停止的标识和访问回调
public class BinarySearchTree<E> implements BinaryTreeInfo {
private int size;
private Node<E> root;
......
public static abstract class Visitor<E> {
boolean stop;
/**
* @return 如果返回true，就代表停止遍历
*/
public abstract boolean visit(E element);
}
二叉树遍历的应用
- 前序遍历: 树状结构展示(注意左右子树的顺序)
public String toString() {
StringBuilder sb = new StringBuilder();
this.toString(this.root, sb, "");
return sb.toString();
}
private void toString(BinarySearchTree.Node<E> node, StringBuilder sb, String prefix) {
if (node != null) {
this.toString(node.left, sb, prefix + "L---");
sb.append(prefix).append(node.element).append("\n");
this.toString(node.right, sb, prefix + "R---");
}
}
- 中序遍历: 二叉搜索树的中序遍历按升序或者降序处理节点
- 后续遍历: 适用于一些先子后父的操作
- 层序遍历:
1、计算二叉树的高度
递归的实现方式
private int height(BinarySearchTree.Node<E> node) {
return node == null ? 0 : 1 + Math.max(this.height(node.left), this.height(node.right));
}
迭代的方式实现,使用层序遍历
public int height() {
if (this.root == null) {
return 0;
} else {
int height = 0;
int levelSize = 1;
Queue<BinarySearchTree.Node<E>> queue = new LinkedList();
queue.offer(this.root);
while(!queue.isEmpty()) {
BinarySearchTree.Node<E> node = (BinarySearchTree.Node)queue.poll();
--levelSize;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (levelSize == 0) {
levelSize = queue.size();
++height;
}
}
return height;
}
}
2、判断一颗树是否为完全二叉树
-
如果树为空,返回 false
-
如果树不为空,开始层序遍历二叉树(用队列)
- 如果 node.left != null,将 node.left 入队
- 如果 node.left == null && node.right != null,返回 false
- 如果 node.right != null, 将 node.right 入队
- 如果 node.right == null
那么后面遍历的节点应该都为叶子节点,才是完全二叉树
否则返回 false - 遍历结束,返回 true
public boolean isComplete() {
if (this.root == null) {
return false;
} else {
Queue<BinarySearchTree.Node<E>> queue = new LinkedList();
queue.offer(this.root);
boolean leaf = false;
while(!queue.isEmpty()) {
BinarySearchTree.Node<E> node = (BinarySearchTree.Node)queue.poll();
if (leaf && !node.isLeaf()) {
return false;
}
if (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) {
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else {
leaf = true;
}
}
return true;
}
}
根据遍历结果重构还原二叉树
- 以下结果可以保证还原出唯一的一颗二叉树
- 前序遍历 + 中序遍历
- 后序遍历 + 中序遍历
- 前序遍历+ 后序遍历
- 如果它是一颗真二叉树,结果是唯一的
- 不然结果不唯一
前驱节点
- 前驱节点:中序遍历时的前一个节点,如果是二叉搜索树,前驱节点就是前一个比它小的节点
- 如果 node.left != null ,predecessor = node.left.right.right.right.... ,终止条件时 right 为 null
- 如果 node.left == null && node.parent != null , predecessor = node.parent.parent.parent...... , 终止条件: node 在 parent 的右子树中
- 如果 node.left == null && node.parent == null, 那就没有前驱节点,例如没有左子树的根节点
后继节点
- 中序遍历时的后一个节点,如果是二叉搜索树,后继节点就是后一个比它大的节点
- 如果node.left != null, successor = node.right.left.left.left.... ,终止条件 left 为 null
- 如果node.right == null && node.parent.parent.parent...... , 终止条件 node在 parent 的左子树中
- 如果node.right == null && node.parent == null , 那么就没有后继节点,例如 没有右子树的根节点
网友评论