数据结构 - 二叉树

文章目录

大家好,这篇博客给大家带来二叉树的概念,特性和基本操作的实现

目标:

1. 掌握树的基本概念

2. 掌握二叉树概念及特性

3. 掌握二叉树的基本操作

---

一 . 树型结构

1.1 树的概念(了解)

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

1.有一个特殊的结点，称为根结点，根结点没有前驱结点

2.除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

3.树是递归定义的。

1.2 数的常用术语 (掌握)

结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6

树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6

叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点

双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点

孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点

根结点：一棵树中，没有双亲结点的结点；如上图：A

结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由m（m>=0）棵互不相交的树组成的集合称为森林

1.3 树的应用(了解)

1. 文件系统：文件系统通常使用树的结构来组织文件和目录，每个目录都可以包含多个子目录和文件。

2. 数据库索引：数据库中的索引通常使用树的结构来快速定位和访问数据。

3. 网络路由：网络路由器使用树的结构来决定数据包的传输路径，以实现高效的数据传输。

4. 组织架构：组织架构通常使用树的结构来表示不同部门、岗位和员工之间的关系。

5. 表达式求值：编译器和计算器可以使用树的结构来解析和求值数学表达式。

6. 人工智能：决策树和搜索树是人工智能中常用的算法，用于决策和规划。

7. 图形学：图形学中的场景图和层次模型使用树的结构来表示和操作图形对象。

8. 数据压缩：哈夫曼树是一种常用的数据压缩算法，用于将频率较高的字符编码为较短的编码。

9. 操作系统：操作系统中的进程调度和内存管理等功能通常使用树的结构来组织和管理进程和内存资源。

10. AI算法：神经网络和决策树等AI算法中使用树的结构来表示和处理数据。

 总而言之,树这种数据结构应用十分广泛,基本上涵盖了生活的方方面面,十分重要!

1.4 树相较于数组和链表的优势(了解)

1. 快速插入和删除：树的结构允许快速插入和删除节点，时间复杂度为O(log n)，而数组的插入和删除操作通常需要移动其他元素，时间复杂度为O(n)。
2. 快速搜索：树的结构使得搜索操作更加高效，时间复杂度为O(log n)，而数组需要遍历所有元素，时间复杂度为O(n)。
3. 有序性：树的结构可以保持元素的有序性，使得范围查询等操作更加高效。
4. 灵活性：树的结构可以适应动态变化的数据集，可以很容易地添加、删除和修改节点，而数组的大小通常是固定的。
5. 适用于层次结构：树的结构可以很好地表示层次结构的数据，比如文件系统、组织架构等。
6. 适用于排序和搜索算法：树的结构可以很好地支持排序和搜索算法，比如二叉搜索树、平衡二叉树等。

总之，树的结构在插入、删除、搜索等操作上具有较高的效率，并且适用于表示层次结构和支持排序和搜索算法。

二 . 二叉树(重点)

接下来就进入了树的重点内容了,大家打起精神来!

2.1 二叉树的概念

二叉树是一种特殊的树结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的特点是每个节点最多有两个子节点，且子节点的顺序是固定的，即左子节点在前，右子节点在后。

二叉树可以为空树，即没有任何节点。如果二叉树不为空，则根节点是二叉树的唯一一个没有父节点的节点，如上图。

2.2 两种特殊的二叉树

1. 满二叉树:  一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵 二叉树的层数为K，且结点总数是2的k次方-1 ，则它就是满二叉树。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完 比特就业课 全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

 2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

设树的节点数为N 则连接树的边为N-1,设度为0的节点为n0 度为1的节点为n1 度为2的节点为n2

0 x n0+1 x n1+2 x n2 = N-1;

n0+n1+n2 = N;

解之: n0 = n2 + 1

4. 具有n个结点的完全二叉树的深度k为 上取整

2.4 二叉树的基本操作

为了二叉树中的方法,我们先来准备一个二叉树

BTNode为节点类,使用内部类的方式,私有化成员变量root

调用createBinaryTree方法模拟下图的二叉树

public class BinaryTree {
    public static class BTNode {
        BTNode left;
        BTNode right;
        int value;

        BTNode(int value) {
            this.value = value;
        }
    }

    private BTNode root;

    public void createBinaryTree(){
        BTNode node1 = new BTNode(1);
        BTNode node2 = new BTNode(2);
        BTNode node3 = new BTNode(3);
        BTNode node4 = new BTNode(4);
        BTNode node5 = new BTNode(5);
        BTNode node6 = new BTNode(6);
        root = node1;
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }
}

 

2.4.1 二叉树的前序遍历

前序遍历指的是遍历的顺序为 根节点->左子节点->右子节点

我们有两种实现方式,一种是通过递归实现,还有一种是通过非递归的方式来实现

递归方式:

public void preOrder(BTNode root){
    if(root == null){
        return;
    }
    System.out.println(root.value);
    preOrder(root.left);
    preOrder(root.right);
}

 

 

非递归方式:

步骤:

1.打印当前cur节点的val值

2.如果cur节点有右节点,将其压入栈

3.如果cur节点有左节点,将其压入栈

4.循环上述过程,直到栈为空为止

count 解释: 标志位 保证开始栈为空时不能进入循环,同时用来记录循环的次数

public void preOrder2(BTNode root){
    if(root == null){
        return;
    }
    Stack stack = new Stack();
    BTNode cur = null;
    int count = 0; // 标志位 同时记录循环进行的次数


    while (count == 0 || !stack.empty()){
        if(stack.empty()){
            cur = root;
        }else{
           cur = stack.pop();
        }

        System.out.println(cur.value);

        if(cur.right != null){
            stack.push(cur.right);
        }

        if(cur.left != null){
            stack.push(cur.left);
        }
        count++;
    }
}

2.4.2 二叉树的中序遍历

左子节点 -> 根节点 -> 右子节点

递归

    public void infixOrder(BTNode root){
        if(root == null){
            return;
        }
        infixOrder(root.left);
        System.out.println(root);
        infixOrder(root.right);
    }

非递归

public void infixOrder2(BTNode root) {
    if (root == null) {
        return;
    }
    Stack stack = new Stack<>();
    BTNode cur = root;
    while (true) {
        //循环遍历向左找，直到为空
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        //2.如果为空，遍历结束
        if (stack.isEmpty()) {
            break;
        }
        //3.取栈顶元素并访问
        BTNode pop = stack.pop();
        System.out.println(pop.value);
        //4.从当前节点右子树出发
        cur = pop.right;
    }
}

2.4.3 二叉树的后序遍历

左子节点 -> 右子节点-> 根节点

递归

public void postOrder1(BTNode root){
    if(root == null){
        return;
    }
    postOrder1(root.left);
    postOrder1(root.right);
    System.out.println(root.value);
}

 可以看到,前中后序遍历都是相对于根节点来说的

2.4.4 获取树中节点的个数

/**
 * 获取树中节点的个数
 * @param root 根节点
 * @return 返回树中节点的个数
 */
public int getSize(BTNode root){
    if(root == null){
        return 0;
    }
    return getSize(root.left)+getSize(root.right)+1;
}

 这个题还有两种方式,一种是进行前中后序遍历,可解 另一种就是非递归方式,和上面的非递归本质上并无差别

2.4.5 获取叶子结点的个数

/**
 * 获取节点中叶子结点的个数
 * @param root 根节点
 * @return 返回叶子结点的个数
 */
public int getLeafSize(BTNode root){
    if(root == null){
        return 0;
    }
    if(root.left == null && root .right == null){
        return 1;
    }
    return getLeafSize(root.left)+getLeafSize(root.right);
}

 依旧是采用分治的实现,递归实现,把一个问题转化为与之相对应的小问题来解决

这里没有画图的必要,和上面的完全类似,上面能理解,这个就没问题

2.4.6 获取第k层节点的个数

/**
 * 获取的k层节点的个数 规定 root所处的层级为 1
 * @param root 根节点
 * @param k 层数
 * @return 返回值
 */
public int getKSize(BTNode root,int k){
    if(root == null){
        return 0;
    }
    if(k == 1){
        return 1;
    }
    return getKSize(root.left,k-1)+getKSize(root.right,k-1);
}

 

2.4.7 获取二叉树的高度

/**
 * 二叉树的最大高度
 * @param root 根节点
 * @return 返回值
 */
public int getHead(BTNode root){
    if(root == null){
        return 0;
    }
    return Math.max(getHead(root.left)+1,getHead(root.right)+1);
}

2.4.8 层序遍历

思路:

1.定义队列和辅助节点cur,将root赋值给cur

2.如果cur不为空,打印该节点的value值并将该节点入队列

3.从队列中poll出队头元素赋值给cur

4.如果cur节点的左节点不为空,将该节点入队列并打印该节点的value值

5.如果cur节点的右节点不为空,将给节点入队列并打印该节点的value值

6.重复3,4,5 直到队列为空为止

图解:

 

 

/**
 * 二叉树的层序遍历
 *
 * @param root 根节点
 */
public void LevelOrder(BTNode root) {
    BTNode cur = root;
    Queue queue = new ArrayDeque<>();

    if (cur != null) {
        queue.add(root);
        System.out.println(root.value);
    }

    while (!queue.isEmpty()) {
        cur = queue.poll();
        if (cur.left != null) {
            queue.add(cur.left);
            System.out.println(cur.left.value);
        }
        if (cur.right != null) {
            queue.add(cur.right);
            System.out.println(cur.right.value);
        }
    }
}

2.4.9 判断一棵树是否是完全二叉树

 还记得什么是完全二叉树?

 只可意会,不可言传!

思路分析:

在上面层序遍历的思想上加以改进即可

1.定义队列和辅助节点cur,将root赋值给cur

2.如果cur不为空,打印该节点的value值并将该节点入队列

3.从队列中poll出队头元素赋值给cur

4.判断当前cur是否为空

5.cur为空 循环出队列 将出队列的值赋值给cur ,在队列非空之前,只要cur有一次为非空,即为非完全二叉树

6.cur不为空 将cur节点的左右节点都添加到队列中,不用关心左右节点是否为空

7.重复3,4,5 直到队列为空为止

图解:

好好想想是不是这样的

完全二叉树图解

 

代码实现:

/**
 * 判断一个二叉树是否是完全二叉树
 *
 * @param root 二叉树根节点
 * @return 返回值为布尔, 代表是否是完全二叉树
 */
public Boolean IsCompleteBinaryTree(BTNode root) {
    BTNode cur = root;
    Queue queue = new LinkedList<>();

    if (cur != null) {
        queue.add(root);
    }

    while (true) {
        cur = queue.poll();
        if(cur == null){
            while(!queue.isEmpty()){
                cur = queue.poll();
                if(cur != null){
                    return false;
                }
            }
            return true;
        }else{
            queue.add(cur.left);
            queue.add(cur.right);
        }
    }

}

---

总结

树的知识远远不止这些,只能说是基础吧,大家好好消化,尤其是二叉树方面的代码一定要搞清楚

往后面试说不定就考到了。