Java数据结构之二叉树

一.定义：

树状图是一种数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。

二.基本术语：

三.树的种类：

四.树的基本操作：

1.树的数据结构

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    public TreeNode(int val) {
        this.val = val;
    }
}
1
2
3
4
5
6
7
8
9
10

2.前序遍历
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树(递归实现)。

	public static void PreOrder(TreeNode head) {
       if (head == null) {
            return;
       }
       System.out.print(head.val + " ");
       PreOrder(head.left);
       PreOrder(head.right);
    }
1
2
3
4
5
6
7
8

3.中序遍历
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树(递归实现)。

 public static void InOrder(TreeNode head) {
        if (head == null){
            return;
        }
        InOrder(head.left);
        System.out.print(head.val + " ");
        InOrder(head.right);
    }

1
2
3
4
5
6
7
8
9

4.后序遍历
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点(递归实现)。

 public static void PostOrder(TreeNode head) {
        if (head == null){
            return;
        }
        PostOrder(head.left);
        PostOrder(head.right);
        System.out.print(head.val + " ");
    }
1
2
3
4
5
6
7
8

5.层次遍历
层次遍历直接按照二叉树层次对每一层进行遍历

public static void levelOrder(TreeNode head) {
		if (head == null){
			return;
		}
		Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
		queue.add(head);
		while (!queue.isEmpty()) {
			TreeNode temp = queue.poll();
			System.out.print(temp.val);
			if (temp.left != null)
				queue.add(temp.left);
			if (temp.right != null)
				queue.add(temp.right);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6.二叉树的高度
递归计算出左子树与右子树的高度，找出左子树与右子树高度的较大者，最后加1，得出二叉树的高度

	public static int depth(TreeNode head) {
		int h1, h2;
		if (head == null) {
			return 0;
		} else {
			h1 = deep(head.left);
			h2 = deep(head.right);
			return (h1 < h2) ? h2 + 1 : h1 + 1;
		}
	}
1
2
3
4
5
6
7
8
9
10