定义
二叉树是一棵树，其中每个节点都不能有多于两个的儿子。
实现
二叉树的节点就是由element（元素）的信息加上两个到其他节点的引用（left和right）组成的结构。二叉树可以由根节点表示。
class Node<E extends Comparable<E>> {
E value;
Node<E> left;
Node<E> right;
Node(E value) {
this.value = value;
left = null;
right = null;
}
}
二叉树的各种遍历
深度优先遍历
深度优先遍历又可以分为前序遍历，中序遍历，后序遍历，这里介绍递归和非递归两种方式实现三种深度优先遍历。
递归方式：
/**
* 先序遍历二叉树（递归）
* @param node
*/
public void preOrderTraverse(Node<E> node) {
System.out.print(node.value + " ");
if (node.left != null)
preOrderTraverse(node.left);
if (node.right != null)
preOrderTraverse(node.right);
}
/**
* 中序遍历二叉树（递归）
* @param node
*/
public void inOrderTraverse(Node<E> node) {
if (node.left != null)
inOrderTraverse(node.left);
System.out.print(node.value + " ");
if (node.right != null)
inOrderTraverse(node.right);
}
/**
* 后序遍历二叉树（递归）
* @param node
*/
public void postOrderTraverse(Node<E> node) {
if (node.left != null)
postOrderTraverse(node.left);
if (node.right != null)
postOrderTraverse(node.right);
System.out.print(node.value + " ");
}
非递归方式
深度优先遍历的实现一般使用Stack。
/**
* 先序遍历二叉树（非递归）
* @param root
*/
public void preOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = null;
stack.push(root);
while (!stack.isEmpty()) {
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
if (currentNode.right != null)
stack.push(currentNode.right);
if (currentNode.left != null)
stack.push(currentNode.left);
}
}
/**
* 中序遍历二叉树（非递归）
* 算法:
* 1.遍历到最左节点, 入栈路径上的左节点;
* 2.出栈并打印当前节点, 对此节点的右节点重复上述过程;
* @param root
*/
public void inOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉树最左端的叶子结点(currentNode是null)
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
System.out.print(currentNode.value + " ");
currentNode = currentNode.right;
}
}
/**
* 后序遍历二叉树（非递归）
* 算法:
* 1. 遍历到最左节点, 入栈路径上的节点;
* 2. 出栈当前节点, 有如下两种处理情况
* A) 直接打印的情况: 当前节点的右节点为null(说明当前节点是个左节点) 或者 当前节点的右节点为上一个打印的节点(说明当前节点是个根节点, 且左右分支都已经打印完毕)
* B) 重新入栈, 先处理右节点(重复上述过程)的情况: 当前节点的右节点不为null且尚未打印
* @param root
*/
public void postOrderTraverseNoRecursion(Node<E> root) {
LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
Node<E> currentNode = root;
Node<E> lastOutput = null;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点(currentNode是null)
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
// 当前结点没有右结点 或者 当前节点的右节点是上一个已经输出的结点, 则输出当前结点
while (currentNode.right == null || currentNode.right == lastOutput) {
System.out.print(currentNode.value + " ");
lastOutput = currentNode;
if (stack.isEmpty()) {
return; // root已输出, 则遍历结束
}
currentNode = stack.pop();
}
stack.push(currentNode); // 还有右结点没有遍历, 不能立刻打印, 所以重新入栈, 先处理右节点
currentNode = currentNode.right;
}
}
广度优先遍历
广度优先遍历一般使用队列Queue。
/**
* 广度优先遍历二叉树，又称层次遍历二叉树
* @param root
*/
public void breadthFirstTraverse(Node<E> root) {
Queue<Node<E>> queue = new LinkedList<Node<E>>();
Node<E> currentNode = null;
queue.offer(root);
while (!queue.isEmpty()) {
currentNode = queue.poll();
System.out.print(currentNode.value + " ");
if (currentNode.left != null)
queue.offer(currentNode.left);
if (currentNode.right != null)
queue.offer(currentNode.right);
}
}
网友评论