【DSA】数据结构与算法 03 树
树是由结点和边组成的不存在任何环的一种数据结构。
1 二叉树
二叉树：二叉树的每个结点至多只有二棵子树（不存在度大于2的结点），二叉树的子树有左右之分，次序不能颠倒。
二叉树的性质：
- 在非空二叉树中，第
i层的结点总数不超过2 ^ (i - 1), i >= 1; - 深度为
h, (h >= 1)的二叉树最多有2 ^ h - 1个结点，最少有h个结点; - 对于任意一棵二叉树，如果其叶结点数为
N0，而度数为2的结点总数为N2，则N0 = N2 + 1; - 具有
n个结点的完全二叉树的深度为log2(n + 1); - 有
N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：- 若
I为结点编号则如果I>1，则其父结点的编号为I/2； - 如果
2I <= N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子； - 如果
2I + 1 <= N，则其右儿子的结点编号为2I + 1；若2I + 1 > N，则无右儿子。
- 若
- 设有
i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J = I + 2i。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。
满二叉树的性质：
- 一颗树深度为
h，最大层数为k，深度与最大层数相同，k = h； - 叶子数为
2 ^ h； - 第k层的结点数是：
2 ^ (k - 1)； - 总结点数是：
2 ^ (k - 1)，且总节点数一定是奇数。
完全二叉树：完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
完全二叉树性质：
- 假设
n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数n = n0 + n1 + n2；n = 1 + n1 + 2 * n2；
1.1 遍历
递归版本实现起来非常简单，非递归版本需要用一个stack来模拟递归时的函数调用。对于三种遍历，我们都使用 push 当前节点-> push 左子树-> pop 左子树-> push 右子树-> pop 右子树的方式。但是打印时机有所不同。对于前序遍历来说，每次访问到一个节点就打印；对于中序遍历来说，每次将右子节点进栈时，把当前节点打印；对于后序遍历来说，每次 pop 的时候打印，还需要一个临时节点指向上一个打印的节点。
先序遍历：根 - 左 - 右
public static void preOrder(TreeNode root) {
if (root == null)
return;
System.out.print(root.val + " ");
preOrder(root.left);
preOrder(root.right);
}
public static void preOrderNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode t = root;
while (t != null || !stack.isEmpty()) {
if (t != null) {
System.out.print(t.val + " ");
stack.push(t);
t = t.left;
} else {
t = stack.pop();
t = t.right;
}
}
}
中序遍历：左 - 根 - 右
public static void inOrder(TreeNode root) {
if (root == null)
return;
inOrder(root.left);
System.out.print(root.val + " ");
inOrder(root.right);
}
public static void inOrderNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode t = root;
while (t != null || !stack.isEmpty()) {
if (t != null) {
stack.push(t);
t = t.left;
} else {
t = stack.pop();
System.out.print(t.val + " ");
t = t.right;
}
}
}
后序遍历：左 - 右 - 根
public static void postOrder(TreeNode root) {
if (root == null)
return;
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val + " ");
}
public static void postOrderNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode t = root, pre = null;
while (t != null || !stack.isEmpty()) {
while (t != null) {
stack.push(t);
t = t.left;
}
t = stack.peek();
if (t.right == null || pre == t.right) {
System.out.print(t.val + " ");
pre = stack.pop();
t = null;
} else
t = t.right;
}
}
层次遍历
public static void levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode t = queue.poll();
System.out.print(t.val + " ");
if (t.left != null)
queue.offer(t.left);
if (t.right != null)
queue.offer(t.right);
}
}