数据结构：二叉树基础入门_二叉树的左子树和右子树

定义

二叉树由一个根节点和两个互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

二叉树种类

满二叉树

对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。

完全二叉树

除了叶子节点外每一个节点都有左右子叶且叶子节点都处在最底层的二叉树。

对于完全二叉树，若某个节点数为i，左子节点位2i+1，右子节点为2i+2。

二叉搜索树

又称二叉查找树或者二叉排序树。二叉搜索树具有下列性质：

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值
• 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值
• 左、右子树也分别为二叉排序树
• 没有键值相等的节点

二分查找的时间复杂度是O(log N)，最坏情况下的时间复杂度是O(N)

平衡二叉树

又称AVL树。它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

红黑树

红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树插入，删除，查找的复杂度都是O（log N）。

哈夫曼树

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

结论

• 二叉树的第i层至多有2^(i-1)个节点, 深度为k的二叉树至多共有2^(k-1)个节点
• 与树不同，树的节点个数至少为1，而二叉树的节点个数可以为0
• 树中节点的最大度数没有限制，而二叉树节点的最大度数为2
• 树的节点无左、右之分，而二叉树的节点有左、右之分

遍历方式

二叉树的遍历可以分为深度优先遍历和广度优先遍历。深度优先遍历可以分为先序遍历、中序遍历、后序遍历。广度优先遍历就是层次遍历。

节点类TreeNode：

public class TreeNode {
    public int value; // 节点val
    public TreeNode leftChild;// 左子树 left
    public TreeNode rightChild;// 右子树 right

    public TreeNode(int value) {
        super();
        this.value = value;
    }
    
    public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

生成完全二叉树：

private  int[] treeNodeValue= {10,6,14,4,8,12,16};
private  ArrayList<TreeNode> list = new ArrayList<>();

public static TreeNode createTree() {
		 
		 for (int i = 0; i < treeNodeValue.length; i++) {
	            TreeNode treeNode = new TreeNode(treeNodeValue[i]);
	            list.add(treeNode);
	        }
		 //根据完全二叉树的性质，i节点的左子树是2*i+1，右节点字数是2*i+2
		 for (int i = 0; i < list.size() / 2; i++) {
	            TreeNode treeNode = list.get(i);
	            //判断左子树是否越界
	            if (i * 2 + 1 < list.size()) {
	                TreeNode leftTreeNode = list.get(i * 2 + 1);
	                treeNode.setLeftChild(leftTreeNode);
	            }
	            //判断右子树是否越界
	            if (i * 2 + 2 < list.size()) {
	                TreeNode rightTreeNode = list.get(i * 2 + 2);
	                treeNode.setRightChild(rightTreeNode);
	            }
	        }
		 
		 return list.get(0);
	 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

深度优先遍历（DFS）

尽可能去遍历二叉树的深度。

先序遍历

先访问根节点，再访问左孩子和右孩子

• 递归方式

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 非递归方式

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

先序遍历结果：10->6->4->8->14->12->16

中序遍历

先访问左孩子，再访问根节点和右孩子

• 递归方式

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 非递归方式

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stk = new LinkedList<TreeNode>();
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中序遍历结果：4->6->8->10->12->14->16

后序遍历

先访问左孩子，再访问右孩子，再访问根节点

• 递归方式

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        postorder(root, res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 非递归方式

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

后序遍历结果：4->8->6->12->16->14->10

广度优先遍历（BFS）

实际上就是一层一层的遍历，按照层次输出二叉树的各个节点

层次遍历

按照所在层数，从下往上遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

层次遍历结果：10->6->14->4->8->12->16