声明，本文不涉及基础的树知识，主要详解的是二叉树相关的基础知识，为后续了解指定树的结构时奠定基础知识。
什么是二叉树？
二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2，也就是说节点最多只能有左右两个孩子。
2、左子树和右子树是有顺序的，次序不能颠倒，儿子就是儿子，闺女就是闺女。
3、即使某结点只有一个子树，也要区分左右子树，孩子要分男女啊。
下面开始介绍一些常见的二叉树结构图：
1. 斜二叉树，所有的结点都只有左子树（左斜树），或者只有右子树（右斜树），这种是最坑比的树，效率和普通链表结构差不多，后面讲解AVLTree时会介绍如何形成此结构。
image
2. 满二叉树，所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。这是最完美圆满的二叉树，树十分平衡，现有节点没有一颗浪费。
image
3. 完全二叉树，对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。满二叉树必须是完全二叉树，反过来不一定成立。
特点：
叶子结点只能出现在最下一层（满二叉树继承而来）
最下层叶子结点一定集中在左 部连续位置。
倒数第二层，如有叶子节点，一定出现在右部连续位置。
同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。
image
上面的这三个是特殊的二叉树，在一般使用时，较少用到，因为完美的事情总是少数派。
二叉树树的存储方式与表示
顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
image
链式存储：
image
二叉树的四种遍历方式和代码实现
二叉树遍历：从树的根节点出发，将树中所有的节点按照某种规则依次遍历完即可。
先序遍历：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即【父—左—右】
image
遍历的结果：
递归代码实现：
/**
* 先序遍历
* 递归
*/
public void preOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
System.out.print(Node.element + " ");
preOrder(Node.left);
preOrder(Node.right);
}
}
非递归代码实现：
/**
* 先序遍历
* 非递归
*/
public void preOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
while(Node != null || !stack.empty())
{
while(Node != null)
{
System.out.print(Node.element + " ");
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
Node = Node.right;
}
}
}
中序遍历：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即【左—父—右】
递归：
/**
* 中序遍历
* 递归
*/
public void midOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
midOrder(Node.left);
System.out.print(Node.element + " ");
midOrder(Node.right);
}
}
非递归：
/**
* 中序遍历
* 非递归
*/
public void midOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
while(Node != null || !stack.empty())
{
while (Node != null)
{
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
System.out.print(Node.element + " ");
Node = Node.right;
}
}
}
后序遍历：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即【左—右—父】
递归：
/**
* 后序遍历
* 递归
*/
public void posOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
posOrder(Node.left);
posOrder(Node.right);
System.out.print(Node.element + " ");
}
}
非递归：
/**
* 后序遍历
* 非递归
*/
public void posOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
int i = 1;
while(Node != null || !stack1.empty())
{
while (Node != null)
{
stack1.push(Node);
stack2.push(0);
Node = Node.left;
}
while(!stack1.empty() && stack2.peek() == i)
{
stack2.pop();
System.out.print(stack1.pop().element + " ");
}
if(!stack1.empty())
{
stack2.pop();
stack2.push(1);
Node = stack1.peek();
Node = Node.right;
}
}
}
层序遍历：
递归：需要写辅助方法
/*
* 层序遍历
* 递归
*/
public void levelOrder(BinaryNode<AnyType> Node) {
if (Node == null) {
return;
}
int depth = depth(Node);
for (int i = 1; i <= depth; i++) {
levelOrder(Node, i);
}
}
private void levelOrder(BinaryNode<AnyType> Node, int level) {
if (Node == null || level < 1) {
return;
}
if (level == 1) {
System.out.print(Node.element + " ");
return;
}
// 左子树
levelOrder(Node.left, level - 1);
// 右子树
levelOrder(Node.right, level - 1);
}
public int depth(BinaryNode<AnyType> Node) {
if (Node == null) {
return 0;
}
int l = depth(Node.left);
int r = depth(Node.right);
if (l > r) {
return l + 1;
} else {
return r + 1;
}
}
非递归
/*
* 层序遍历
* 非递归
*/
public void levelOrder1(BinaryNode<AnyType> Node) {
if (Node == null) {
return;
}
BinaryNode<AnyType> binaryNode;
Queue<BinaryNode> queue = new LinkedList<>();
queue.add(Node);
while (queue.size() != 0) {
binaryNode = queue.poll();
System.out.print(binaryNode.element + " ");
if (binaryNode.left != null) {
queue.offer(binaryNode.left);
}
if (binaryNode.right != null) {
queue.offer(binaryNode.right);
}
}
}
完整代码使用了泛型接收扩展类型的数据，详细如下：
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Tree<AnyType extends Comparable<? super AnyType>>
{
private static class BinaryNode<AnyType>
{
BinaryNode(AnyType theElement)
{
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt)
{
element = theElement;
left = lt;
right = rt;
}
AnyType element;
BinaryNode<AnyType> left;
BinaryNode<AnyType> right;
}
private BinaryNode<AnyType> root;
public void insert(AnyType x)
{
root = insert(x, root);
}
public boolean isEmpty()
{
return root == null;
}
private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t)
{
if(t == null)
{
return new BinaryNode<>(x, null, null);
}
int compareResult = x.compareTo(t.element);
if(compareResult < 0)
{
t.left = insert(x, t.left);
}
else if(compareResult > 0)
{
t.right = insert(x, t.right);
}
else
{
;
}
return t;
}
/**
* 前序遍历
* 递归
*/
public void preOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
System.out.print(Node.element + " ");
preOrder(Node.left);
preOrder(Node.right);
}
}
/**
* 前序遍历
* 非递归
*/
public void preOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
while(Node != null || !stack.empty())
{
while(Node != null)
{
System.out.print(Node.element + " ");
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
Node = Node.right;
}
}
}
/**
* 中序遍历
* 递归
*/
public void midOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
midOrder(Node.left);
System.out.print(Node.element + " ");
midOrder(Node.right);
}
}
/**
* 中序遍历
* 非递归
*/
public void midOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack = new Stack<>();
while(Node != null || !stack.empty())
{
while (Node != null)
{
stack.push(Node);
Node = Node.left;
}
if(!stack.empty())
{
Node = stack.pop();
System.out.print(Node.element + " ");
Node = Node.right;
}
}
}
/**
* 后序遍历
* 递归
*/
public void posOrder(BinaryNode<AnyType> Node)
{
if (Node != null)
{
posOrder(Node.left);
posOrder(Node.right);
System.out.print(Node.element + " ");
}
}
/**
* 后序遍历
* 非递归
*/
public void posOrder1(BinaryNode<AnyType> Node)
{
Stack<BinaryNode> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
int i = 1;
while(Node != null || !stack1.empty())
{
while (Node != null)
{
stack1.push(Node);
stack2.push(0);
Node = Node.left;
}
while(!stack1.empty() && stack2.peek() == i)
{
stack2.pop();
System.out.print(stack1.pop().element + " ");
}
if(!stack1.empty())
{
stack2.pop();
stack2.push(1);
Node = stack1.peek();
Node = Node.right;
}
}
}
/*
* 层序遍历
* 递归
*/
public void levelOrder(BinaryNode<AnyType> Node) {
if (Node == null) {
return;
}
int depth = depth(Node);
for (int i = 1; i <= depth; i++) {
levelOrder(Node, i);
}
}
private void levelOrder(BinaryNode<AnyType> Node, int level) {
if (Node == null || level < 1) {
return;
}
if (level == 1) {
System.out.print(Node.element + " ");
return;
}
// 左子树
levelOrder(Node.left, level - 1);
// 右子树
levelOrder(Node.right, level - 1);
}
public int depth(BinaryNode<AnyType> Node) {
if (Node == null) {
return 0;
}
int l = depth(Node.left);
int r = depth(Node.right);
if (l > r) {
return l + 1;
} else {
return r + 1;
}
}
/*
* 层序遍历
* 非递归
*/
public void levelOrder1(BinaryNode<AnyType> Node) {
if (Node == null) {
return;
}
BinaryNode<AnyType> binaryNode;
Queue<BinaryNode> queue = new LinkedList<>();
queue.add(Node);
while (queue.size() != 0) {
binaryNode = queue.poll();
System.out.print(binaryNode.element + " ");
if (binaryNode.left != null) {
queue.offer(binaryNode.left);
}
if (binaryNode.right != null) {
queue.offer(binaryNode.right);
}
}
}
public static void main( String[] args )
{
int[] input = {8, 2, 4, 1, 3, 5, 7, 9, 11};
Tree<Integer> tree = new Tree<>();
for(int i = 0; i < input.length; i++)
{
tree.insert(input[i]);
}
System.out.print("递归前序遍历 ：");
tree.preOrder(tree.root);
System.out.print("\n非递归前序遍历：");
tree.preOrder1(tree.root);
System.out.print("\n递归中序遍历 ：");
tree.midOrder(tree.root);
System.out.print("\n非递归中序遍历 ：");
tree.midOrder1(tree.root);
System.out.print("\n递归后序遍历 ：");
tree.posOrder(tree.root);
System.out.print("\n非递归后序遍历 ：");
tree.posOrder1(tree.root);
System.out.print("\n递归层序遍历：");
tree.levelOrder(tree.root);
System.out.print("\n非递归层序遍历 ：");
tree.levelOrder1(tree.root);
}
}
