【数据结构与算法之树结构】二叉树

小鱼儿 2024-03-25 12:36 103阅读 0赞

#### 【数据结构与算法之树结构】二叉树 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之树结构】二叉树
         *   *   *  1 二叉树的定义
                 *  2 满二叉树与完全二叉树
                 *  3 二叉树的存储形式

###### 1 二叉树的定义 ######

二叉树(Binary Tree) 或者为空，或者为由一个根节点加上根节点的左子树和右子树组成，要求左右子树互不相关，且都是二叉树。

![在这里插入图片描述][7379e78cbc0449d987e1e12cb163548a.png_pic_center]

二叉树中的每个节点至多有两个孩子节点，其中左边称为左孩子，右边称为右孩子。

###### 2 满二叉树与完全二叉树 ######

【满二叉树】二叉树的任意节点都是叶子节点或有两棵子树，同时叶子节点都位于二叉树的底层。

![在这里插入图片描述][1e260c176eb54a88853adc505de49e98.png_pic_center]

【完全二叉树】二叉树中最多只有最下面两层节点的度小于2，并且底层节点(叶子节点) 依次排列在该层最左边的位置上。

![在这里插入图片描述][bb8e24555ce847ed85e8b81d4cdf314a.png_pic_center]

二叉树的一些重要性质：

*  二叉树的第i层上至多有  2 i − 1 2^\{i - 1\} 2i−1 个节点( i ≥ 1)
 *  深度为k 的二叉树至多有  2 k − 1 2^k - 1 2k−1 个节点(k ≥ 1)
 *  对于任何一棵二叉树，如果叶子节点数为  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个节点的完全二叉树的深度为  ⌊ l o g 2 n + 1 ⌋ ⌊ log\_2^n + 1 ⌋ ⌊log2n\+1⌋

###### 3 二叉树的存储形式 ######

二叉树一般采用多重链表的形式存储。

二叉树的节点类用Java 可定义如下：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: BinaryTreeNode
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 13:22
     */
    
    public class BinaryTreeNode {
        
    
        int data; // 数据域
        BinaryTreeNode leftChild; // 左孩子
        BinaryTreeNode rightChild; // 右孩子
    
        public BinaryTreeNode(int data) {
        
            this.data = data;
            leftChild = null;
            rightChild = null;
        }
    
    }

二叉树类：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: BinaryTree
     * @Author: Ding Jiaxiong
     * @Data:2023/3/13 13:24
     */
    
    public class BinaryTree {
        
    
        private BinaryTreeNode root; // 根节点
    
        public BinaryTree() {
        
            root = null;
        }
    
    }

[7379e78cbc0449d987e1e12cb163548a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/224f676a2f4f42b8975f2e015c350662.png
[1e260c176eb54a88853adc505de49e98.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/00b7371a3db64858b45d00e30ae8ab5b.png
[bb8e24555ce847ed85e8b81d4cdf314a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b802e81ce09e4ba494fcd9a6d7f87cf3.png