二叉树笔记
本文共 10402 字，大约阅读时间需要 34 分钟。
二叉树
1.树的基本概念
-
节点、根节点、父节点、子节点、兄弟节点
-
一棵树可以没有任何节点，称为空树
-
一棵树可以只有 1 个节点，也就是只有根节点
-
子树、左子树、右子树
-
节点的度（degree）：子树的个数
-
树的度：所有节点度中的最大值
-
叶子节点（leaf）：度为 0 的节点
-
非叶子节点：度不为 0 的节点
-
层数（level）：根节点在第 1 层，根节点的子节点在第 2 层，以此类推（有些教程也从第 0 层开始计算）
-
节点的深度（depth）：从根节点到当前节点的唯一路径上的节点总数
-
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
-
树的深度：所有节点深度中的最大值
-
树的高度：所有节点高度中的最大值
-
树的深度 等于 树的高度
2.二叉树（Binary Tree）
-
特点
- 每个节点的度最大为 2（最多拥有 2 棵子树）
- 左子树和右子树是有顺序的
- 即使某节点只有一棵子树，也要区分左右子树
-
- 性质
-
非空二叉树的第 i 层，最多有 x i − 1 x^{i-1} xi−1个节点（ i ≥ 1 ）
-
在高度为 h 的二叉树上最多有 x h − 1 x^h-1 xh−1 个结点（ h ≥ 1 ）
-
对于任何一棵非空二叉树，如果叶子节点个数为 n0，度为 2 的节点个数为 n2，则有: n 0 = n 2 + 1 n0 = n2 + 1 n0=n2+1
假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n = n 0 + n 1 + n 2 n = n0 + n1 + n2 n=n0+n1+n2
二叉树的边数 T = n 1 + 2 ∗ n 2 = n – 1 = n 0 + n 1 + n 2 – 1 T = n1 + 2 * n2 = n – 1 = n0 + n1 + n2 – 1 T=n1+2∗n2=n–1=n0+n1+n2–1
因此 n 0 = n 2 + 1 n0 = n2 + 1 n0=n2+13.真二叉树
定义：所有节点的度都要么为 0，要么为 2
4.满二叉树
定义：最后一层节点的度都为 0，其他节点的度都为 2
-
在同样高度的二叉树中，满二叉树的叶子节点数量最多、总节点数量最多
-
满二叉树一定是真二叉树，真二叉树不一定是满二叉树
5.完全二叉树（Complete Binary Tree）
- 定义：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应
-
叶子节点只会出现最后 2 层，最后 1 层的叶子结点都靠左对齐
-
完全二叉树从根结点至倒数第 2 层是一棵满二叉树
-
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
- 性质
- 度为 1 的节点只有左子树
- 度为 1 的节点要么是 1 个，要么是 0 个
- 同样节点数量的二叉树，完全二叉树的高度最小
- 一棵有 n 个节点的完全二叉树（n > 0），从上到下、从左到右对节点从 1 开始进行编号，对任意第 i 个节点
-
假设完全二叉树的高度为 h（ h ≥ 1 ），那么
至少有$ 2^{h-1} $个节点 最多有 2 h − 1 2^h-1 2h−1 个节点（ 满二叉树 ） 总节点数量为 n-
2 h − 1 ≤ n < 2 h 2^{h-1} ≤ n < 2^h 2h−1≤n<2h
-
$ h - 1 ≤ log2n < h$
-
$ h = floor( log2n ) + 1$
-
floor 是向下取整，另外，ceiling 是向上取整
-
6.遍历
-
方式
-
前序遍历
-
中序遍历
-
后序遍历
-
层序遍历
-
1.前序遍历
访问顺序：根节点、前序遍历左子树、前序遍历右子树
// vistor为抽象器，可以在他visit方法中实现操作者想对他实现的功能，具体在最下方代码 public void preorder(Visitorvisitor) { if (visitor == null) return; preorder(root, visitor); } private void preorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; visitor.stop = visitor.visit(node.element); preorder(node.left, visitor); preorder(node.right, visitor); }
2.中序遍历
访问顺序：中序遍历左子树、根节点、中序遍历右子树
public void inorder(Visitorvisitor) { if (visitor == null) return; inorder(root, visitor); } private void inorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; inorder(node.left, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); inorder(node.right, visitor); }
3.后序遍历
访问顺序：后序遍历左子树、后序遍历右子树、根节点
public void postorder(Visitorvisitor) { if (visitor == null) return; postorder(root, visitor); } private void postorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; postorder(node.left, visitor); postorder(node.right, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); }
4.层序遍历
访问顺序：一层一层，从左向右
public void levelOrder(Visitorvisitor) { if (root == null || visitor == null) return; Queue > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (visitor.visit(node.element)) return; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } }
7.全部代码
//此为二叉搜索树的代码，import java.util.Comparator;import java.util.LinkedList;import java.util.Queue;@SuppressWarnings("unchecked")public class BinarySearchTree implements BinaryTreeInfo { private int size; private Node root; private Comparator comparator; public BinarySearchTree() { this(null); } public BinarySearchTree(Comparator comparator) { this.comparator = comparator; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void clear() { root = null; size = 0; } public void add(E element) { elementNotNullCheck(element); // 添加第一个节点 if (root == null) { root = new Node<>(element, null); size++; return; } // 添加的不是第一个节点 // 找到父节点 Node parent = root; Node node = root; int cmp = 0; do { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { // 相等 node.element = element; return; } } while (node != null); // 看看插入到父节点的哪个位置 Node newNode = new Node<>(element, parent); if (cmp > 0) { parent.right = newNode; } else { parent.left = newNode; } size++; } public void remove(E element) { remove(node(element)); } public boolean contains(E element) { return node(element) != null; } private void remove(Node node) { if (node == null) return; size--; if (node.hasTwoChildren()) { // 度为2的节点 // 找到后继节点 Node s = successor(node); // 用后继节点的值覆盖度为2的节点的值 node.element = s.element; // 删除后继节点 node = s; } // 删除node节点（node的度必然是1或者0） Node replacement = node.left != null ? node.left : node.right; if (replacement != null) { // node是度为1的节点 // 更改parent replacement.parent = node.parent; // 更改parent的left、right的指向 if (node.parent == null) { // node是度为1的节点并且是根节点 root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; } } else if (node.parent == null) { // node是叶子节点并且是根节点 root = null; } else { // node是叶子节点，但不是根节点 if (node == node.parent.left) { node.parent.left = null; } else { // node == node.parent.right node.parent.right = null; } } } private Node node(E element) { Node node = root; while (node != null) { int cmp = compare(element, node.element); if (cmp == 0) return node; if (cmp > 0) { node = node.right; } else { // cmp < 0 node = node.left; } } return null; } public void preorder(Visitor visitor) { if (visitor == null) return; preorder(root, visitor); } private void preorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; visitor.stop = visitor.visit(node.element); preorder(node.left, visitor); preorder(node.right, visitor); } public void inorder(Visitor visitor) { if (visitor == null) return; inorder(root, visitor); } private void inorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; inorder(node.left, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); inorder(node.right, visitor); } public void postorder(Visitor visitor) { if (visitor == null) return; postorder(root, visitor); } private void postorder(Node node, Visitor visitor) { if (node == null || visitor.stop) return; postorder(node.left, visitor); postorder(node.right, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); } public void levelOrder(Visitor visitor) { if (root == null || visitor == null) return; Queue > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); if (visitor.visit(node.element)) return; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } public boolean isComplete() { if (root == null) return false; Queue > queue = new LinkedList<>(); queue.offer(root); boolean leaf = false; while (!queue.isEmpty()) { Node node = queue.poll(); if (leaf && !node.isLeaf()) return false; if (node.left != null) { queue.offer(node.left); } else if (node.right != null) { // node.left == null && node.right != null return false; } if (node.right != null) { queue.offer(node.right); } else { // node.right == null leaf = true; } } return true; } // public boolean isComplete() { // if (root == null) return false;// // Queue > queue = new LinkedList<>();// queue.offer(root);// // boolean leaf = false;// while (!queue.isEmpty()) { // Node node = queue.poll();// if (leaf && !node.isLeaf()) return false;//// if (node.left != null && node.right != null) { // queue.offer(node.left);// queue.offer(node.right);// } else if (node.left == null && node.right != null) { // return false;// } else { // 后面遍历的节点都必须是叶子节点// leaf = true;// if (node.left != null) { // queue.offer(node.left);// }// }// }// // return true;// } public int height() { if (root == null) return 0; // 树的高度 int height = 0; // 存储着每一层的元素数量 int levelSize = 1; Queue > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); levelSize--; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (levelSize == 0) { // 意味着即将要访问下一层 levelSize = queue.size(); height++; } } return height; } public int height2() { return height(root); } private int height(Node node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } @Override public String toString() { StringBuilder sb = new StringBuilder(); toString(root, sb, ""); return sb.toString(); } private void toString(Node node, StringBuilder sb, String prefix) { if (node == null) return; toString(node.left, sb, prefix + "L---"); sb.append(prefix).append(node.element).append("\n"); toString(node.right, sb, prefix + "R---"); } /** * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2 */ private int compare(E e1, E e2) { if (comparator != null) { return comparator.compare(e1, e2); } return ((Comparable )e1).compareTo(e2); } private void elementNotNullCheck(E element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } } @SuppressWarnings("unused") private Node predecessor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right....） Node p = node.left; if (p != null) { while (p.right != null) { p = p.right; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.left) { node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; } private Node successor(Node node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.right) { node = node.parent; } return node.parent; } public static abstract class Visitor { boolean stop; /** * @return 如果返回true，就代表停止遍历 */ public abstract boolean visit(E element); } private static class Node { E element; Node left; Node right; Node parent; public Node(E element, Node parent) { this.element = element; this.parent = parent; } public boolean isLeaf() { return left == null && right == null; } public boolean hasTwoChildren() { return left != null && right != null; } }} 转载地址：http://rnnwi.baihongyu.com/
你可能感兴趣的文章
read obj in matlab
查看>>
find out the neighbour matrix of a mesh
查看>>
Operators and special characters in matlab
查看>>
As-Conformal-As-Possible Surface Registration
查看>>
qmake Variable Reference
查看>>
Lesson 2 Gradient Desent
查看>>
find border vertex
查看>>
matlab sliced variable
查看>>
create symbolic array
查看>>
TAUCS库的编译（vs2010）
查看>>
color vector using in plotting example points and lines between corresponding vertices
查看>>
mex 里面调用matlab函数
查看>>
matlab中cuda编程中分配grid和block dimension的时候的注意事项
查看>>
GPU CUDA and MEX Programming
查看>>
arrayfun用法
查看>>
矩阵积分
查看>>
optimization on macOS
查看>>
Template-Based 3D Model Fitting Using Dual-Domain Relaxation
查看>>
install libfreenect2 on ubuntu 16.04
查看>>
how to use automake to build files
查看>>