二叉树

Posted on | Edited on | In ,

树定义

非线性的数据结构，线性数据结构（数组、链表等数据结构）。
树节点的关系：同级的节点叫做兄弟节点、下级节点叫做子节点、上级节点叫父节点、如果父节点为空叫做做根节点、最下层节点叫叶子节点。
常用的名词：
高度：从叶子节点到跟节点的距离
深度：从根节点到叶子节点的距离
层：深度-1

二叉树

  • 满二叉树：所有叶子节点均在最后一层，除叶子节点以外的节点都是满节点状态。
  • 完全二叉树：所有叶子节点均在最后俩层，最后一层的叶子节点都在左边，并且非叶子节点都是满节点状态。

二叉树的遍历

见代码，都会用到递归算法。

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
//前序遍历：自己-->left-->right
public static void frontForeach(TreeNode node) {
    if (node != null) {
        System.out.println(node.value);
        frontForeach(node.left);
        frontForeach(node.right);
    }
}

//中序遍历：left-->自己-->right
public static void midForeach(TreeNode node) {
    if (node != null) {
        midForeach(node.left);
        System.out.println(node.value);
        midForeach(node.right);
    }
}

//后续遍历：left-->right-->自己
public static void backForeach(TreeNode node) {
    if (node != null) {
        backForeach(node.left);
        backForeach(node.right);
        System.out.println(node.value);
    }
}

什么样的二叉树适合用数组表示

满二叉树以及完全二叉树适合用数组标识因为节点的公式是,根节点是数组下标为1的元素开始，他的子节点节点依次是2(arrayIndx)，2(arrayIndx)+1。因为普通的二叉树会浪费很多空间。