数据结构和算法之旅（七）- 二叉树
树中每个节点最多俩个子节点，不同于完全二叉树，不需要每层都满。
定义
树中每个节点最多俩个子节点，不同于完全二叉树，不需要每层都满。
这种数据结构表示方式有俩种：
一种是TreeNode。
一种是数组。
TreeNode
数组
二叉树的遍历
层序遍历即是广度优先遍历，需要配合队列实现。
注：
以队列来层序遍历时针对TreeNode这种方式表示的二叉树。
如果用数组形式实现二叉树，则直接遍历数组即可，自然为层序遍历。
package org.example.datastructure.treetraversal;
/**
* 递归方式遍历二叉树，前序、中序、后序
*/
public class TreeTraversal {
public static void main(String[] args) {
/**
* 1
* / \
* 2 3
* / /\
* 4 5 6
*
*/
TreeNode root = new TreeNode(
new TreeNode(
new TreeNode(4), 2, null), 1,
new TreeNode(new TreeNode(5), 3, new TreeNode(6)
)
);
System.out.println("前序遍历：");
preOrder(root);
System.out.println("\n中序遍历：");
inOrder(root);
System.out.println("\n后序遍历：");
postOrder(root);
}
/**
* 前序遍历
*/
public static void preOrder(TreeNode node) {
if (node == null) return;
System.out.print(node.val + "\t");
preOrder(node.left);
preOrder(node.right);
}
/**
* 中序遍历
*/
public static void inOrder(TreeNode node) {
if (node == null) return;
inOrder(node.left);
System.out.print(node.val + "\t");
inOrder(node.right);
}
/**
* 后序遍历
*/
public static void postOrder(TreeNode node) {
if (node == null) return;
postOrder(node.left);
postOrder(node.right);
System.out.print(node.val + "\t");
}
}