数据布局-二叉树

1. 概念

一棵二叉树是结点的一个有限聚集，该聚集：

• 大概为空
  
• 大概是由一个根节点加上两棵别称为左子树和右子树的二叉树构成
  

2. 两种特别的二叉树

满二叉树和完全二叉树是二叉树的两种特定范例。以下是它们的界说和区别：
满二叉树

• 界说：每个节点都有两个子节点，大概是叶子节点（没有子节点）。换句话说，除了末了一层，全部层的节点数都是满的。
  
• 特点：
  
  
  
  • 全部叶子节点都在同一层。
    
  • 假如树的深度为                                              h                                      h                        h，那么节点总数为                                                          2                                  h                                          −                               1                                      2^h - 1                        2h−1。
    
  
  

完全二叉树

• 界说：除了末了一层外，全部层的节点都被填满，而且末了一层的节点从左到右添补。
  
• 特点：
  
  
  
  • 末了一层的节点可以不满，但必须从左侧开始添补。
    
  • 节点总数可以是                                              1                                      1                        1 到                                                          2                                  h                                          −                               1                                      2^h - 1                        2h−1 之间的恣意数。
    
  
  

区别

• 节点添补：满二叉树的每个节点都必须有两个子节点，而完全二叉树的末了一层可以不满，但必须左对齐。
  
• 布局：满二叉树的布局更为严酷，而完全二叉树则允许末了一层的机动性。
  

示例

• 满二叉树示例：
  
  1.         A
  2.       /   \
  3.      B     C
  4.     / \   / \
  5.    D   E F   G

  复制代码
• 完全二叉树示例：
  
  1.         A
  2.       /   \
  3.      B     C
  4.     / \   /
  5.    D   E F

  复制代码

3. 二叉树的性子

• 若规定根结点的层数为第1层，则一棵非空二叉树的第i层上最多有                                             2                                       i                               −                               1                                                 2^{i-1}                  2i−1(i>0)个结点
  
• 若规定根结点的层数为第1层，则深度为K的二叉树的最大结点数是                                             2                            k                                  −                         1                              2^k-1                  2k−1(k>=0)
  
• 对任何一棵二叉树, 假如其叶结点个数为                                              n                            0                                       n_0                  n0​, 度为2的非叶结点个数为                                              n                            2                                       n_2                  n2​,则有                                             n                            0                                  ＝                                   n                            2                                  +                         1                              n_0＝n_2+1                  n0​＝n2​+1
  
• 具有n个结点的完全二叉树的深度k为                                   l                         o                                   g                            2                                  (                         n                         +                         1                         )                              log_2(n+1)                  log2​(n+1)上取整
  
• 对于具有n个结点的完全二叉树，假如按照从上至下从左至右的序次对全部节点从0开始编号，则对于序号为i的结点有：
  
  
  
  • 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
    
  • 若2i+1<n，左孩子序号：2i+1，否则无左孩子
    
  • 若2i+2<n，右孩子序号：2i+2，否则无右孩子
    
  
  

4. 二叉树的存储

二叉树的存储布局分为：序次存储和雷同于链表的链式存储。
4.1 序次存储

• 界说：序次存储是通过数组来存储二叉树的节点。根节点存储在数组的第一个位置，子节点按照条理序次依次存储。
  

4.2 链式存储

• 界说：链式存储是使用链表布局来存储二叉树的节点，每个节点包罗数据部门和指向其左子节点和右子节点的指针。
  

1. // 二叉链
2. struct TreeNode {
3.     char data;          // 数据部分
4.     TreeNode* left;    // 指向左子节点的指针
5.     TreeNode* right;   // 指向右子节点的指针
6. };
7. // 三叉链
8. struct TreeNode {
9.     char data;          // 数据部分
10.     TreeNode* left;    // 指向左子节点的指针
11.     TreeNode* right;   // 指向右子节点的指针
12.     TreeNode* parent;  // 当前节点的根节点
13. };

复制代码

5. 二叉树的根本操纵

5.1 二叉树的创建

5.1.1 手动创建

手动创建二叉树可以直接界说节点，得当于小规模的树。

1. // 创建一个简单的二叉树
2. public class BinaryTree {
3.     public TreeNode createTree() {
4.         TreeNode root = new TreeNode(1);
5.         root.left = new TreeNode(2);
6.         root.right = new TreeNode(3);
7.         root.left.left = new TreeNode(4);
8.         root.left.right = new TreeNode(5);
9.         return root;
10.     }
11. }

复制代码

5.1.2 递归创建

通过递归函数来创建二叉树，得当于根据特定规则天生树。

1. public TreeNode createTree(int[] arr, int index) {
2.     if (index >= arr.length || arr[index] == -1) { // -1 表示空节点
3.         return null;
4.     }
5.     TreeNode node = new TreeNode(arr[index]);
6.     node.left = createTree(arr, 2 * index + 1);  // 左子节点
7.     node.right = createTree(arr, 2 * index + 2); // 右子节点
8.     return node;
9. }

复制代码

5.1.3 层序遍历输入

1. public TreeNode createTree() {
2.     Scanner scanner = new Scanner(System.in);
3.     System.out.println("输入节点值（-1 表示空节点，输入 -1 结束）:");
4.     int val = scanner.nextInt();
6.     if (val == -1) return null;
8.     TreeNode root = new TreeNode(val);
9.     Queue<TreeNode> queue = new LinkedList<>();
10.     queue.offer(root);
12.     while (!queue.isEmpty()) {
13.         TreeNode current = queue.poll();
15.         System.out.println("输入 " + current.val + " 的左子节点值:");
16.         val = scanner.nextInt();
17.         if (val != -1) {
18.             current.left = new TreeNode(val);
19.             queue.offer(current.left);
20.         }
22.         System.out.println("输入 " + current.val + " 的右子节点值:");
23.         val = scanner.nextInt();
24.         if (val != -1) {
25.             current.right = new TreeNode(val);
26.             queue.offer(current.right);
27.         }
28.     }
29.     return root;
30. }

复制代码

5.2 二叉树的遍历

• 前中后序遍历 递归，非递归
  
• 层序遍历
  

5.3 二叉树的根本操纵

1. // 获取树中节点的个数
2. int size(Node root);
4. // 获取叶子节点的个数
5. int getLeafNodeCount(Node root);
7. // 子问题思路-求叶子结点个数
9. // 获取第K层节点的个数
10. int getKLevelNodeCount(Node root,int k);
12. // 获取二叉树的高度
13. int getHeight(Node root);
15. // 检测值为value的元素是否存在
16. Node find(Node root, int val);
18. //层序遍历
19. void levelOrder(Node root);
21. // 判断一棵树是不是完全二叉树
22. boolean isCompleteTree(Node root);

复制代码