java版数据结构：二叉树

05-14 阅读 0评论

引言：什么是树

树是一种非线性的数据结构，由节点组成，节点之间以边连接。树结构中最重要的特点是，每个节点可以有多个子节点，但每个节点只有一个父节点（除了根节点）。树结构中没有环路，即任意两个节点之间只有唯一的路径。

树结构通常由根节点、子节点、叶子节点、父节点、深度、高度等基本概念组成：

根节点：树的顶层节点称为根节点，是整棵树的起始节点。
子节点：每个节点可以有多个子节点，子节点是直接连接到该节点的下一级节点。
叶子节点：没有子节点的节点称为叶子节点，即树的末端节点。
父节点：每个节点除了根节点外，都有一个父节点，即其直接连接到它的上一级节点。
深度：节点的深度是指从根节点到该节点的唯一路径的边数。根节点的深度为0，其子节点的深度为1，依此类推。
高度：节点的高度是指从该节点到最远叶子节点的最长路径的边数。叶子节点的高度为0，根节点的高度为树的高度。

数与二叉树之间的关系：

树是一种更一般化的结构：树是一种非线性的数据结构，由节点和边组成，节点之间以边连接。在树结构中，每个节点可以有多个子节点，但只有一个父节点（除了根节点）。树结构中没有环路，任意两个节点之间只有唯一的路径。
二叉树是树的特殊形式：二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树具有树的所有特性，但限制了每个节点的子节点数量为最多两个。
二叉树是树的一种重要实现方式：在实际应用中，二叉树是树结构的一种重要实现方式。通过限制每个节点的子节点数量为两个，可以更方便地进行操作和处理，例如二叉搜索树、堆、表达式树等都是基于二叉树的实现。

二叉树可以看作是树的特殊情况：从结构上看，二叉树可以看作是树的特殊情况，即每个节点最多有两个子节点的树。因此，二叉树是树结构的一种特殊形式，具有更加严格的约束条件。

二叉树

1. 二叉树的概念：

定义：一棵二叉树是节点的一个有限集合，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以为空，或者由一个根节点和两棵分别称为左子树和右子树的二叉树组成。

2. 二叉树的性质：

有序性：二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。
度的限制：二叉树不存在度大于2的节点，每个节点最多有两个子节点。

递归性质：对于任意的二叉树，都是由根节点、左子树和右子树组成的。

3. 满二叉树和完全二叉树的区别：

满二叉树：一棵二叉树，如果每层的节点数都达到最大值，则这棵二叉树就是满二叉树。满二叉树的所有非叶子节点都有两个子节点，且所有叶子节点都在同一层。

完全二叉树：完全二叉树是一种效率很高的数据结构，是由满二叉树演化而来的。对于深度为K，有n个节点的二叉树，当且仅当每个节点都与深度为K的满二叉树中编号从0至n-1的节点一一对应时，称之为完全二叉树。完全二叉树的叶子节点都集中在最下面两层，并且最后一层的叶子节点靠左排列。

4. 二叉树的存储：

二叉树的存储结构分为顺序存储和链式存储。链式存储通过节点之间的引用来表示树的结构，常见的表示方式有孩子表示法和孩子双亲表示法。

二叉树的基本操作

1. 二叉树的遍历：

前序遍历（Preorder Traversal）：先访问根节点，然后递归地前序遍历左子树和右子树。
中序遍历（Inorder Traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
后序遍历（Postorder Traversal）：先递归地后序遍历左子树和右子树，然后访问根节点。

层序遍历（Level Order Traversal）：从上到下，从左到右逐层访问二叉树的节点。

2. 二叉树的构建：

手动创建：通过节点的引用关系手动构建二叉树，可以按照前序、中序、后序等方式构建。

根据遍历序列构建：根据二叉树的前序遍历和中序遍历序列或中序遍历和后序遍历序列构建二叉树。

3. 二叉树的存储结构：

链式存储：通过节点之间的引用关系来表示二叉树的结构，常见的链式存储方式有孩子表示法和孩子双亲表示法。

顺序存储：通过数组等数据结构来存储二叉树的节点，通常按照层序遍历的顺序存储节点，可以方便地进行层序遍历。

4. 二叉树的基本操作：

获取节点个数：计算二叉树中节点的个数。
获取叶子节点个数：计算二叉树中叶子节点的个数。
获取第K层节点个数：计算二叉树中第K层节点的个数。
获取二叉树的高度：计算二叉树的高度或深度。
查找特定值的节点：在二叉树中查找特定值的节点。

判断是否为完全二叉树：判断二叉树是否为完全二叉树。

举例：

class Node {
    int value;
    Node left;
    Node right;
    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree {
    private Node root;
    // 获取树中节点的个数
    public int size(Node root) {
        if (root == null) {
            return 0;
        }
        return 1 + size(root.left) + size(root.right);
    }
    // 获取叶子节点的个数
    public int getLeafNodeCount(Node root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }
    // 获取第K层节点的个数
    public int getKLevelNodeCount(Node root, int k) {
        if (root == null || k  
 针对二叉树各种操作的测试代码： 
 public class BinaryTreeTest {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        // 创建一棵二叉树
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        // 测试获取节点个数
        System.out.println("节点个数：" + binaryTree.size(root));
        // 测试获取叶子节点个数
        System.out.println("叶子节点个数：" + binaryTree.getLeafNodeCount(root));
        // 测试获取第K层节点个数
        int k = 2;
        System.out.println("第" + k + "层节点个数：" + binaryTree.getKLevelNodeCount(root, k));
        // 测试获取二叉树的高度
        System.out.println("二叉树的高度：" + binaryTree.getHeight(root));
        // 测试查找特定值的节点
        int valueToFind = 5;
        Node foundNode = binaryTree.find(root, valueToFind);
        if (foundNode != null) {
            System.out.println("找到值为 " + valueToFind + " 的节点");
        } else {
            System.out.println("未找到值为 " + valueToFind + " 的节点");
        }
        // 测试层序遍历
        System.out.println("层序遍历结果：");
        binaryTree.levelOrder(root);
        // 测试判断是否为完全二叉树
        System.out.println("\n是否为完全二叉树：" + binaryTree.isCompleteTree(root));
    }
} 
 运行结果： 
  
 
 二叉树的存储： 
 二叉树的存储结构主要包括顺序存储和链式存储两种方式。 
 顺序存储：

顺序存储是将二叉树的节点按照某种顺序依次存储在数组中。通常采用完全二叉树的顺序存储方式，即按照从上到下、从左到右的顺序依次存储节点。对于完全二叉树，可以通过数组的下标来表示节点之间的父子关系。例如，对于数组中下标为i的节点，其左子节点的下标为2i+1，右子节点的下标为2i+2，父节点的下标为(i-1)/2。
顺序存储的优点是可以节省存储空间，但缺点是对于非完全二叉树会造成空间浪费，而且插入和删除节点时需要移动大量元素。

顺序存储方式示例：

public class ArrayBinaryTree {
    private int[] array; // 用数组存储二叉树的节点数据
    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }
    // 获取父节点的下标
    private int parent(int index) {
        return (index - 1) / 2;
    }
    // 获取左子节点的下标
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    // 获取右子节点的下标
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    public void printTree() {
        for (int i = 0; i  
 链式存储：

链式存储是通过节点之间的引用关系来表示二叉树的存储结构。每个节点包含数据域和指向左右子节点的引用。链式存储方式更直观和灵活，适用于任意形状的二叉树，不会浪费空间。常见的链式存储方式包括孩子表示法和孩子双亲表示法。
孩子表示法：每个节点包含左孩子和右孩子的引用。这种方式简单直观，但可能会导致节点之间的指向关系不够清晰。
孩子双亲表示法：每个节点包含左孩子、右孩子和父节点的引用。通过父节点的引用可以方便地找到当前节点的父节点，便于在树中进行上行操作。

链式存储方式示例：

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree {
    private Node root;
    public BinaryTree(Node root) {
        this.root = root;
    }
    public void printTree(Node node) {
        if (node == null) {
            return;
        }
        System.out.println("Node " + node.value);
        printTree(node.left);
        printTree(node.right);
    }
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        BinaryTree binaryTree = new BinaryTree(node1);
        binaryTree.printTree(binaryTree.root);
    }
}