一、前序遍历
1.递归写法
- 以二叉搜索树代码为例
递归方法
二、中序遍历
1.递归写法
-
以二叉搜索树代码为例
递归方法
三、后序遍历
1.递归写法
- 以二叉搜索树代码为例
四.层序遍历
- 以二叉搜索树代码为例
image.png
附：二叉搜索树的代码
package com.weyan;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import com.weyan.printer.BinaryTreeInfo;
@SuppressWarnings("unused")
//使用自定义打印器 需要实现BinaryTreeInfo类中的几个方法：root/ left/ right/ string
public class BinarySearchTree<E> implements BinaryTreeInfo {
private int size;
//根节点
private Node<E> root;
private Comparator<E> comparator;
//构造函数 不传入参数
public BinarySearchTree() {
this(null);
}
//构造函数 传入参数：比较器
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
}
public void add(E element) {
elementNotNullCheck(element);
//添加第一个节点
if (root == null) {
root = new Node<>(element, null);
size ++;
return;
}
//添加的不是第一个节点
//找到父节点
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
while (node != null) {
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
}else if(cmp < 0) {
node = node.left;
}else {//相等
node.element = element;
return;
}
}
//看看插入到父节点的哪个位置
Node<E> newNode = new Node<E>(element, parent);
if (cmp > 0) {
parent.right = newNode;
}else if(cmp < 0) {
parent.left = newNode;
}
size ++;
}
public void remove(E element) {
}
public boolean contains(E element) {
return false;
}
//比较两个节点,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
@SuppressWarnings("unchecked")
private int compare(E e1 , E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>) e1).compareTo(e2);
}
//判断一个节点是否为空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
//前序遍历（递归方法）
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
//中序遍历（递归方法）
public void inorderTraversal() {
preorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
preorderTraversal(node.left);
System.out.println(node.element);
preorderTraversal(node.right);
}
//后序遍历（递归方法）
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
preorderTraversal(node.left);
preorderTraversal(node.right);
System.out.println(node.element);
}
//层序遍历(通过链表实现)
private void levelorderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
//入队
queue.offer(root);
while (!queue.isEmpty()) {
//出队
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
private static class Node<E> {
E element;
//左子节点
Node<E> left;
//右子节点
Node<E> right;
//父节点
Node<E> parent;
//构造函数
public Node(E element,Node<E> parent) {
this.element = element;
this.parent = parent;
}
}
/*使用自定义打印器 需要实现以下几个方法
*
*/
@Override
public Object root() {
// TODO Auto-generated method stub
return root;
}
@SuppressWarnings("unchecked")
@Override
public Object left(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).left;
}
@SuppressWarnings("unchecked")
@Override
public Object right(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).right;
}
@SuppressWarnings("unchecked")
@Override
public Object string(Object node) {
// TODO Auto-generated method stub
//打印出parent
Node<E> myNode = (Node<E>) node;
String parentString = "null";
if (myNode.parent != null) {
parentString = myNode.parent.element.toString();
}
return myNode.element + "_(" + parentString + ")";
}
}
五、遍历的应用
1.计算二叉树的高度
- 递归写法
- 采用层序遍历
/**---层序遍历写法---**/
//二叉树的高度
public int height() {
if (root == null) return 0;
int height = 0;
//存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> 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;
}
六、练习
（一）
代码-以二叉搜索树为例
package com.weyan;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import com.weyan.printer.BinaryTreeInfo;
@SuppressWarnings("unused")
//使用自定义打印器 需要实现BinaryTreeInfo类中的几个方法：root/ left/ right/ string
public class BinarySearchTree<E> implements BinaryTreeInfo {
private int size;
//根节点
private Node<E> root;
private Comparator<E> comparator;
//构造函数 不传入参数
public BinarySearchTree() {
this(null);
}
//构造函数 传入参数：比较器
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
}
public void add(E element) {
elementNotNullCheck(element);
//添加第一个节点
if (root == null) {
root = new Node<>(element, null);
size ++;
return;
}
//添加的不是第一个节点
//找到父节点
Node<E> parent = root;
Node<E> node = root;
int cmp = 0;
while (node != null) {
parent = node;
cmp = compare(element, node.element);
if (cmp > 0) {
node = node.right;
}else if(cmp < 0) {
node = node.left;
}else {//相等
node.element = element;
return;
}
}
//看看插入到父节点的哪个位置
Node<E> newNode = new Node<E>(element, parent);
if (cmp > 0) {
parent.right = newNode;
}else if(cmp < 0) {
parent.left = newNode;
}
size ++;
}
public void remove(E element) {
}
public boolean contains(E element) {
return false;
}
/**---递归写法---**/
//二叉树的高度
// public int height() {
// return nodeHeight(root);
// }
//节点高度
// private int nodeHeight(Node<E> node) {
// if (node == null) return 0;
// return 1 + Math.max(nodeHeight(node.left), nodeHeight(node.right));
// }
/**---层序遍历写法---**/
//二叉树的高度
public int height() {
if (root == null) return 0;
int height = 0;
//存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> 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;
}
//比较两个节点,返回值==0代表e1和e2相等;返回值>0代表e1>e2;返回值<0代表e1<e2
@SuppressWarnings("unchecked")
private int compare(E e1 , E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>) e1).compareTo(e2);
}
//判断一个节点是否为空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
//前序遍历（递归方法）
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
//中序遍历（递归方法）
public void inorderTraversal() {
preorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
preorderTraversal(node.left);
System.out.println(node.element);
preorderTraversal(node.right);
}
//后序遍历（递归方法）
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
preorderTraversal(node.left);
preorderTraversal(node.right);
System.out.println(node.element);
}
//层序遍历(通过链表实现)
private void levelorderTraversal() {
if (root == null) return;
Queue<Node<E>> queue = new LinkedList<>();
//入队
queue.offer(root);
while (!queue.isEmpty()) {
//出队
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
///判断一棵树是否为完全二叉树
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> 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;
}
private static class Node<E> {
E element;
//左子节点
Node<E> left;
//右子节点
Node<E> right;
//父节点
Node<E> parent;
//构造函数
public Node(E element,Node<E> parent) {
this.element = element;
this.parent = parent;
}
//是否是叶子节点
public boolean isLeaf() {
return left == null && right == null;
}
}
/*使用自定义打印器 需要实现以下几个方法
*
*/
@Override
public Object root() {
// TODO Auto-generated method stub
return root;
}
@SuppressWarnings("unchecked")
@Override
public Object left(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).left;
}
@SuppressWarnings("unchecked")
@Override
public Object right(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).right;
}
@SuppressWarnings("unchecked")
@Override
public Object string(Object node) {
// TODO Auto-generated method stub
//打印出parent
Node<E> myNode = (Node<E>) node;
String parentString = "null";
if (myNode.parent != null) {
parentString = myNode.parent.element.toString();
}
return myNode.element + "_(" + parentString + ")";
}
}
（二）翻转二叉树
package 二叉树;
import java.util.LinkedList;
import java.util.Queue;
/*url:https://leetcode-cn.com/problems/invert-binary-tree/
* 翻转二叉树
*/
public class _226_翻转二叉树 {
/*--------------递归方法-------------*/
// 1.前序遍历
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
// invertTree(root.left);
// invertTree(root.right);
// return root;
// }
// 2.后序遍历
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
// invertTree(root.left);
// invertTree(root.right);
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
// return root;
// }
// 3.中序遍历
// public TreeNode invertTree(TreeNode root) {
// if (root == null) return root;
// invertTree(root.left);
// TreeNode tmp = root.left;
// root.left = root.right;
// root.right = tmp;
// invertTree(root.left);
// return root;
// }
/*--------------迭代（非递归）-------------*/
// 4.层序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null)
return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
验证结果
（三）重构二叉树
