完全二叉树你需要了解一下

完全二叉树介绍

完全二叉树（Complete Binary Tree）是一种特殊的二叉树，它的定义是：如果设二叉树的深度为h，除第h层外，其它各层（1~h-1）的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

• 完全二叉树的性质包括：

1. 深度为k的完全二叉树，节点数在2k到2k+1−1之间。
2. 若根节点编号为1，则第i个节点的编号为i。
3. 对于任意一节点i，其左儿子的编号为2i，右儿子的编号为2i+1。
4. 如果i不是根节点，它的父节点编号为i/2（向下取整）。

通过这些性质，我们可以方便地计算完全二叉树的节点个数和深度，也可以快速找到一个节点的父节点和子节点。

完全二叉树应用场景

1. 文件系统：在文件系统中，树和森林被用来构造文件系统。例如，我们看到的Windows和Linux等文件管理系统都是树型结构。
2. 编译系统：在编译系统中，如C编译器源代码中，二叉树的中序遍历形式被用来存放C语言中的表达式。
3. 二叉排序树：被用于数据的排序和快速查找。
4. 高级语言中的map和hashmap：它们的底层实现有二叉树的影子。

完全二叉树和满二叉树的区别

满二叉树和完全二叉树的区别如下：

1. 节点性质 ：满二叉树的每一层，除最后一层外，都是完全填满的，且最后一层的节点都集中在最左边。完全二叉树则允许最后一层有空缺结点，但这些空缺结点必须位于最后一层的右边。
2. 叶子结点 ：满二叉树的叶子结点只可能出现在最后一层，且最后一层的节点都集中在最左边。完全二叉树的叶子结点只出现在最后一层和次最后一层，且最后一层的叶子结点都集中在最左边，次最后一层的叶子结点都集中在最右边。
3. 节点计算 ：满二叉树的深度为k，则节点数为2^k - 1。完全二叉树的节点数为n，其深度为(log2n)+1（向下取整）。
4. 插入操作：如果一个节点有两个子节点，那么插入一个新节点后，满二叉树将变为一个完全二叉树。而在完全二叉树中，如果要插入一个新节点，则需要先检查新节点的位置，如果新节点的位置在最后一层且不是最左边或最右边，那么该树就不是完全二叉树。

总的来说，满二叉树是完全二叉树的特例。

完全二叉树代码示例

以下是一个使用Java实现完全二叉树的示例代码：

class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class CompleteBinaryTree {
    Node root;

    CompleteBinaryTree(int n) {
        root = insertLevelOrder(1, 1, n);
    }

    Node insertLevelOrder(int arr[], int i, int n) {
        if (i < n) {
            Node temp = new Node(arr[i]);
            temp.left = insertLevelOrder(arr, 2 * i + 1, n);
            temp.right = insertLevelOrder(arr, 2 * i + 2, n);
            return temp;
        }
        return null;
    }

    void printPostorder(Node node) {
        if (node == null) {
            return;
        } else {
            printPostorder(node.left);
            printPostorder(node.right);
            System.out.print(node.data + " ");
        }
    }

    public static void main(String args[]) {
        CompleteBinaryTree tree = new CompleteBinaryTree(7);
        System.out.println("Postorder traversal of complete binary tree is ");
        tree.printPostorder(tree.root);
    }
}
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
36
37
38
39
40
41
42
43

在这个示例中，我们定义了一个Node类来表示二叉树的节点，它包含一个数据项和左右子节点的引用。我们还定义了一个CompleteBinaryTree类，它包含一个根节点和一个构造函数，用于创建完全二叉树。构造函数使用插入顺序的方式构建完全二叉树，并使用后序遍历打印树的内容。在main函数中，我们创建一个CompleteBinaryTree对象，并使用7个元素构建完全二叉树。最后，我们打印后序遍历的结果。

拓展

AVL树你需要了解一下

红黑树你需要了解一下

满二叉树你需要了解一下