【数据结构与算法】详解二叉树以及模拟实现二叉树

简介: 二叉树在学习数据结构中是一种很重要的类型,也是学习数据结构中比较困难的一种结构,但是在平时用的也是非常多,因此二叉树尤为重要.本篇文章中会涉及到大量的递归代码,如果一些地方不太理解,可以尝试画图梳理代码执行流程关于文章中的二叉树源码→点击即可跳转 需要的可以去看一看

前言:

二叉树在学习数据结构中是一种很重要的类型,也是学习数据结构中比较困难的一种结构,但是在平时用的也是非常多,因此二叉树尤为重要.

本篇文章中会涉及到大量的递归代码,如果一些地方不太理解,可以尝试画图梳理代码执行流程

关于文章中的二叉树源码→点击即可跳转 需要的可以去看一看


1.二叉树的定义

2.png


二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树


2.二叉树的相关术语


①节点:包含一个数据元素及若干指向子树分支的信息 。

②节点的度:一个节点拥有子树的数目称为节点的度 。

③叶子节点:也称为终端节点,没有子树的节点或者度为零的节点。

④分支节点:也称为非终端节点,度不为零的节点称为非终端节点 。

⑤树的度:树中所有节点的度的最大值。

⑥节点的层次:从根节点开始,假设根节点为第1层,根节点的子节点为第2层,依此类推,如果某一个节点位于第L层,则其子节点位于第L+1层。

⑦树的深度:也称为树的高度,树中所有节点的层次最大值称为树的深度。

⑧有序树:如果树中各棵子树的次序是有先后次序,则称该树为有序树。

⑨无序树:如果树中各棵子树的次序没有先后次序,则称该树为无序树。

⑩森林:由m(m≥0)棵互不相交的树构成一片森林。如果把一棵非空的树的根节点删除,则该树就变成了一片森林,森林中的树由原来根节点的各棵子树构成


3.二叉树的性质


性质1:二叉树的第i层上至多有2i-1(i≥1)个节点 。

性质2:深度为h的二叉树中至多含有2h-1个节点。

性质3:若在任意一棵二叉树中,有n0个叶子节点,有n2个度为2的节点,则必有n0=n2+1。

性质4:具有n个节点的满二叉树深为log2n+1。

性质5:若对一棵有n个节点的完全二叉树进行顺序编号(1≤i≤n),那么,对于编号为i(i≥1)的节点:

当i=1时,该节点为根,它无双亲节点 。

当i>1时,该节点的双亲节点的编号为i/2 。

若2i≤n,则有编号为2i的左节点,否则没有左节点 。

若2i+1≤n,则有编号为2i+1的右节点,否则没有右节点 。

4.特殊的二叉树


1、满二叉树:如果一棵二叉树只有度为0的节点和度为2的节点,并且度为0的节点在同一层上,则这棵二叉树为满二叉树。

2、完全二叉树:深度为k,有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时,称为完全二叉树 。

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上,并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

5.二叉树的遍历


二叉树的遍历主要有前序遍历,中序遍历,后序遍历以及层序遍历,前面三种遍历主要是采用递归的方式进行遍历的,如果看不懂,建议画图梳理一下代码执行流程

前序遍历

       public void preOrder(TreeNode root) {

           if(root == null){

               return;

           }

           System.out.print(root.val+" ");

           preOrder(root.left);

           preOrder(root.right);

       }

中序遍历

      public 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+" ");

       }

层序遍历

   public 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);

           }

       }

   }


6.获取树中节点的个数


方法1:遍历思想

   public static int nodeSize = 0;// 记录二叉树的结点个数

   public void size(TreeNode root) {

       if(root == null){

           return;

       }

       nodeSize++;

       size(root.left);

       size(root.right);

   }

方法2:子问题的思想

   public int size2(TreeNode root) {

       if(root == null){

           return 0;

       }

       // 难点 -> 画图 在叶子结点时 会返回1 根是最后加上的

       return size2(root.left)+size2(root.right)+1;

   }

7.获取叶子节点的个数


叶子结点的左子树和右子树都为null,因此只要看哪些结点符合条件的就可以了

方法1:遍历思想

  public static int leafSize = 0;

   public void getLeafNodeCount1(TreeNode root) {

       if(root == null){

           return;

       }

       if(root.left == null && root.right == null){

           leafSize++;

       }

       getLeafNodeCount1(root.left);

       getLeafNodeCount1(root.right);

   }

方法2:子问题的思想

  public 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);

   }


8.获取第K层节点的个数


  public int getKLevelNodeCount(TreeNode root, int k) {

       if(root == null){

           return 0;

       }

       if(k <= 0){

           return 0;

       }

       if(k == 1){

           return 1;

       }

       k--;

       return getKLevelNodeCount(root.left,k) + getKLevelNodeCount(root.right,k);

   }


9.获取二叉树的高度


  public int getHeight(TreeNode root) {

       if(root == null){

           return 0;

       }

       int leftHeight = getHeight(root.left);

       int rightHeight = getHeight(root.right);

       return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;

   }


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


这里实现的时候返回值设置的是TreeNode,如果不喜欢可以换成boolean

  public TreeNode find(TreeNode root, char val) {

       if(root == null) {

           return null;

       }

       if(root.val == val){

           return root;

       }

       TreeNode treeNode1 = find(root.left,val);

       if(treeNode1 != null){

           return treeNode1;

       }

       TreeNode treeNode2 = find(root.right,val);

       if(treeNode2 != null){

           return treeNode2;

       }

       return null;

   }


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


判断是不是完全二叉树,这里使用的是队列做的.也涉及到分层遍历的思想,将每层的结点以及最后一层结点的孩子结点存下来,然后对第一次出现null时后的数据开始进行判断.如果是完全二叉树,那么最后一次遍历的数据都是null,如果不是完全二叉树,那么就是结点和null并存的情况,而且一定是在结点前有个null

   public boolean isCompleteTree(TreeNode root) {

       if (root == null) {

           return true;

       }

       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;

           }

       }

       while (!queue.isEmpty()) {

           TreeNode ret = queue.poll();

           if (ret != null){

               return false;

           }

       }

       return true;

   }

相关文章
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
82 4
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
1月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
58 5
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
132 8
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
45 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
32 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
37 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
31 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
29 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学