数据结构-二叉树

1. 概念

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

1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成

2. 两种特殊的二叉树

满二叉树和完全二叉树是二叉树的两种特定类型。以下是它们的定义和区别：

满二叉树

• 定义：每个节点都有两个子节点，或者是叶子节点（没有子节点）。换句话说，除了最后一层，所有层的节点数都是满的。
• 特点：
  • 所有叶子节点都在同一层。
  • 如果树的深度为 $h$，那么节点总数为 $2^h-1$。

完全二叉树

• 定义：除了最后一层外，所有层的节点都被填满，并且最后一层的节点从左到右填充。
• 特点：
  • 最后一层的节点可以不满，但必须从左侧开始填充。
  • 节点总数可以是 $1$ 到 $2^h-1$ 之间的任意数。

区别

• 节点填充：满二叉树的每个节点都必须有两个子节点，而完全二叉树的最后一层可以不满，但必须左对齐。
• 结构：满二叉树的结构更为严格，而完全二叉树则允许最后一层的灵活性。

示例

• 满二叉树示例：

          A
        /   \
       B     C
      / \   / \
     D   E F   G
  

• 完全二叉树示例：

          A
        /   \
       B     C
      / \   /
     D   E F
  

3. 二叉树的性质

1. 若规定根结点的层数为第1层，则一棵非空二叉树的第i层上最多有$2^{i-1}$(i>0)个结点
2. 若规定根结点的层数为第1层，则深度为K的二叉树的最大结点数是$2^k-1$(k>=0)
3. 对任何一棵二叉树, 如果其叶结点个数为 $n_0$, 度为2的非叶结点个数为 $n_2$,则有$n_0＝n_2+1$
4. 具有n个结点的完全二叉树的深度k为$lo{g}_2(n+1)$上取整
5. 对于具有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 链式存储

• 定义：链式存储是使用链表结构来存储二叉树的节点，每个节点包含数据部分和指向其左子节点和右子节点的指针。

// 二叉链
struct TreeNode {
    char data;          // 数据部分
    TreeNode* left;    // 指向左子节点的指针
    TreeNode* right;   // 指向右子节点的指针
};
// 三叉链
struct TreeNode {
    char data;          // 数据部分
    TreeNode* left;    // 指向左子节点的指针
    TreeNode* right;   // 指向右子节点的指针
    TreeNode* parent;  // 当前节点的根节点
};

5. 二叉树的基本操作

5.1 二叉树的创建

5.1.1 手动创建

手动创建二叉树可以直接定义节点，适合于小规模的树。

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

5.1.2 递归创建

通过递归函数来创建二叉树，适合于根据特定规则生成树。

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

5.1.3 层序遍历输入

public TreeNode createTree() {
    Scanner scanner = new Scanner(System.in);
    System.out.println("输入节点值（-1 表示空节点，输入 -1 结束）:");
    int val = scanner.nextInt();

    if (val == -1) return null;

    TreeNode root = new TreeNode(val);
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        System.out.println("输入 " + current.val + " 的左子节点值:");
        val = scanner.nextInt();
        if (val != -1) {
            current.left = new TreeNode(val);
            queue.offer(current.left);
        }

        System.out.println("输入 " + current.val + " 的右子节点值:");
        val = scanner.nextInt();
        if (val != -1) {
            current.right = new TreeNode(val);
            queue.offer(current.right);
        }
    }
    return root;
}

5.2 二叉树的遍历

1. 前中后序遍历 递归，非递归
2. 层序遍历

5.3 二叉树的基本操作

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