首页 > 其他分享 >【数据结构】二叉树

【数据结构】二叉树

时间:2024-07-27 15:53:17浏览次数:21  
标签:遍历 TreeNode 二叉树 return 数据结构 root 节点

目录


二叉树

二叉树(Binary Tree)是n(n >= 0 )个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
二叉树

特殊二叉树

有以下三种特殊二叉树:

1.斜树:所有的节点都只有左子树的二叉树叫斜树。所有的节点只有右子树
的二叉树叫右斜树。两者统称为斜树。
2.满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子节点都在同一层上,这样的二叉树称为满二叉树。
3.完全二叉树:对一棵具有n个节点的二叉树按照层序编号,如果编号为i(1 <= i <= n)的节点与同样深度的满二叉树中编号节点为i的节点在二叉树中的位置相同,则这棵二叉树为完全二叉树。

特殊树

二叉树的性质

二叉树的5个性质:

  1. 规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i - 1) (i>0)个结点。
  2. 规定只有根结点的二叉树的深度为1,则深度为K的二叉树的最大结点数是 2^k - 1 (k>=0)。
  3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1。
  4. 具有N个结点的完全二叉树的深度k为log(N+1)以2为底向上取整。
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0开始编号,则对于序号为i的结点有:
    若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点;
    若2i+1<n,左孩子序号:2i+1,否则无左孩子;
    若2i+2<n,右孩子序号:2i+2,否则无右孩子。

二叉树的模拟实现

我们用代码模拟实现一个二叉树。

存储结构

在讲解树的时候就讲解了树有两种存储方式,顺序存储和链式存储。
二叉树的顺序存储在下一文讲解堆在介绍。
本文主要讲解链式存储,使用孩子表示法。

接口实现

实现的接口(成员方法)如下:

public class BinaryTree {
    // 前序遍历
    public void preOrder(TreeNode root) {}
    // 中序遍历
    void inOrder(TreeNode root) {}
    // 后序遍历
    void postOrder(TreeNode root) {}
    // 获取节点的个数:子问题的思路
    int size2(TreeNode root) {}
    //获取叶子节点的个数:子问题
    int getLeafNodeCount2(TreeNode root) {}
    //获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root, int k) {}
    //获取二叉树的高度 时间复杂度:O(N)
    int getHeight(TreeNode root) {}
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {}
    //层序遍历
    void levelOrder(TreeNode root) {}
    // 判断一棵树是不是完全二叉树
    boolean isCompleteTree(TreeNode root) {}
}

内部类

我们使用孩子表示法来存储二叉树,那么在节点内部类中就要包含左孩子和右孩子的引用。

static class TreeNode {
        public char val;
        public TreeNode left;//左孩子的引用
        public TreeNode right;//右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

遍历

二叉树的遍历(traversing binary tree)是指从根节点出发,按照某种次序依次访问二叉树的所有节点,使得每个节点被访问一次且仅被访问一次。

前序遍历

前序遍历的规则就是:若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,再前序遍历右子树。

以打印为例:通俗讲就是遇根节点就打印,然后走左子树,再进右子树。
前序

// 前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

中序遍历

中序遍历的规则就是:若二叉树为空,则空操作返回,否则从根节点开始(注意不是先访问根节点),中序遍历根节点的左子树,再前序遍历右子树。

以打印为例:通俗讲就是先进左子树,遇根节点如果该根节点的左子树已经打印完了就打印该根节点,再进右子树。
中序

// 中序遍历
    void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

后序遍历

后序遍历的规则就是:若二叉树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右节点。
以打印为例:通俗讲就是先进左子树,再进右子树,遇根节点如果该根节点的左子树和右子树都已经打印完了就打印该根节点。
后序

// 后序遍历
    void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

遍历确定二叉树

根据前中后遍历的特点:

  • 前序遍历从前向后的节点是每颗树根节点。
  • 中序遍历的特点就是每个节点的左边是左子树的节点,右边是右子树的节点。
  • 后序遍历是从后向前的节点是每棵树根节点。

我们只要中序遍历加任一遍历就可以确定当前二叉树。
以前序遍历和中序遍历为例:
根据前序遍历依次往后拿到节点,第一个节点是整棵树的根节点,往后拿到的节点根据中序遍历结果观察是在已确定的二叉树中确定该节点的父亲节点,然后左边就是左孩子,右边就是右孩子。

层序遍历

层序遍历的规则就是:若二叉树为空,则空操作返回,否则从树的第一层,也就是根节点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对节点逐个访问。
层序

代码实现思路:
进行层序遍历时,我们要用到队列(先进先出)这个数据结构,

  1. 将根结点先放进队列去。
  2. 每次都记录队列的节点,如果该节点左右孩子不为空就入队。
  3. 直到队列为空为止。

这样我们入队列是层序遍历的顺序,那出队列也是这个顺序了。

//层序遍历
    void levelOrder(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

获取节点个数

代码思路:

  1. 如果树为空,返回0。
  2. 不为空,直接返回左子树和右子树的节点树加上根。
int size2(TreeNode root) {
        if (root == null) return 0;
        return size2(root.left)
                + size2(root.right) + 1;
    }

获取叶子节点的个数

代码思路:

  1. 如果树为空,返回0。
  2. 不为空,如果节点左子树和右子树为空则返回1。
  3. 最后返回根节点左子树和右子树的叶子结点之和。
int getLeafNodeCount2(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
    }

获取第K层节点的个数

代码思路:

  1. 如果树为空,返回0。
  2. 不为空,如果层数为1并且该节点不为空则返回1。
  3. 最后返回根节点左子树和右子树的第k-1层结点之和。
int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) return 0;
        if (k == 1) return 1;
        return getKLevelNodeCount(root.left, k - 1) +
                getKLevelNodeCount(root.right, k - 1);
    }

获取二叉树的高度

代码思路:

  1. 如果树为空,返回0。
  2. 不为空,求根节点的左子树的高度和根节点右子树的高度。
  3. 返回子树高度的最大值然后加上根节点这一层。
int getHeight(TreeNode root) {
        if (root == null) return 0;
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return leftH > rightH ? leftH + 1 : rightH + 1;
    }

检测值为value的元素是否存在

代码思路:
4. 如果树为空,返回空。
5. 不为空,看根节点是不是所求节点,是返回。
6. 不是就在左子树查看,返回值不是空就返回。
7. 左子树结果是空,查看右子树,返回结果。

TreeNode find(TreeNode root, char val) {
        if (root == null) return null;
        if (root.val == val) return root;

        TreeNode ret = find(root.left, val);
        if (ret != null) {
            return ret;
        }
        ret = find(root.right, val);
        return ret;
    }

判断一棵树是不是完全二叉树

我们需要使用队列这个数据结构。
如果是完全二叉树,那么层序遍历结果下节点之间就不会有空值。
代码思路:

  1. 如果根节点为空直接返回false。
  2. 不为空将根放入队列。
  3. 取出队列值,如果值不为空就将左孩子和右孩子入队,为空直接出循环。
  4. 因为前面是拿到队列中的空节点出循环的,遍历剩余节点如果遇到不为空的节点那该树就不是完全二叉树。
boolean isCompleteTree(TreeNode root) {
        if (root == null) return false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else {
                break;
            }
        }
        //第2次遍历队列 判断队列当中 是否存在非空的元素
        while(!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            if (cur == null) {
                queue.poll();
            } else {
                return false;
            }
        }
        return true;
    }
}

练习链接

相同的树

另一棵树的子树

翻转二叉树

平衡二叉树

对称二叉树

二叉树遍历

二叉树层序遍历

二叉树的公共祖先

从前序遍历和中序遍历构建二叉树

从中序遍历和后序遍历构建二叉树

根据二叉树构建字符串

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

标签:遍历,TreeNode,二叉树,return,数据结构,root,节点
From: https://blog.csdn.net/yj20040627/article/details/140506114

相关文章

  • 数据结构基础第7讲
    数据结构基础第7讲查找考点一:查找的基本概念1.概念静态查找动态查找分类2.查找性能计算平均查找长度:考点二:顺序查找1.顺序查找2.优劣考点三:折半查找(二分搜索)1.概念2.过程3.构建为判定树构建向上取整:左少右多向右偏向下取整:左多右少......
  • 数据结构基础第8讲
    数据结构基础第8讲排序考点一:排序的概念和性能分析1.排序的概念稳定性根据相对位置是否改变判断内排序2.排序的性能考点二:插入类排序1.直接插入排序\(复杂度O(n^2)\)3.折半插入排序改进了比较次数未改变移动次数,因此复杂度仍为\(O(n^2)\)3.希尔排序时......
  • 数据结构-线性表
    目录王道章节内容知识框架考纲内容引入方法1:顺序存储结构的直接表示方法2:顺序存储结构表示非0项方法3:链表结构存储非零项线性表定义线性表的主要操作(ADT)顺序存储结构定义结构代码实现操作及实现初始化获得查找插入删除链式存储结构单链表定义结构代码......
  • 二叉树的遍历
    提纲挈领的说,先序中序后序的遍历区别在于遍历根节点的时机。 1.先序        1.1递归形式 遍历过程为:①访问根结点;②先序遍历其左子树;③先序遍历其右子树。voidPreOrderTraversal(BinTreeBT){if(BT){printf(“%d”,BT->Data);......
  • 手撕数据结构---------顺序表和链表
    1.线性表线性表(linearlist)是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构,常⻅的线性表:顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的,线性表在物理上存储时,通常......
  • 【数据结构】:用Java实现链表
    在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低,因此ArrayList不适合做任意位置插入和删除比较多的场景。因此:java集合中又引入了LinkedList,即链表结构。概念顺序表是物理上连续,逻辑上也是连续的链表......
  • 【数据结构】:顺序表里一些主要功能的实现
    框架线性表是n个具有相同特征的数据元素的有限序列常见的线性表:顺序表、链表、栈、队列…线性表在逻辑上是线性结构,也就是连续的一条直线但在物理结构上不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式进行存储顺序表顺序表其实就是一个数......
  • 数据结构(Java):HashMap源码解析【JDK17】
    1、整体总结 2、成员属性table哈希数组DEFAULT_INITIAL_CAPACITY哈希表默认容量值(16)MAXIMUM_CAPACITY最大容量值DEFAULT_LOAD_FACTOR默认负载因子threshold当前存放元素数量达到该值时就会触发数组扩容TREEIFY_THRESHOLD树化条件之一(转化为红黑树的阈值)MIN_......
  • 数据结构day4(栈)
    seqstack系统中的栈是在缓存区上  数据结构中的栈在堆上  ========================1、空增栈2、空减栈3、满增栈4、满减栈  空栈,top指示器,表示的是新元素待插入的位置满栈,top指示器指的是,最后压栈的元素的位置顺序栈的基本操作:#include"seqstack.h"......
  • MySQL数据结构和索引
    一、MySQL数据结构InnoDB引擎MySQL默认引擎是InnoDB引擎,这个引擎的主要特点是支持事务和行锁,数据结构2.1二叉树(二叉查找树)二叉树是一种特殊的树,二叉树中每个节点的度都不能大于2,就是说每个节点最多只能有左右两个子节点当我们像二叉查找树储存数据的时候,是安装从大到小(或......