当前位置: 首页 > article >正文

【数据结构与算法】Java描述:第四节:二叉树

一、树的相关概念

编程中的树是模仿大自然中的树设计的,呈现倒立的结构,我们着重掌握 二叉树 。

1.1 基本概念:

结点的度:一个结点有几个子结点度就是几; 如上图:A的度为3

树的度:一棵树中,所有结点 度 的 最大值 称为 树的度; 如上图:树的度为3

叶子结点或终端结点度为0的结点称为叶子结点; 如上图:J F K L H I...等节点为叶结点

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

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

根结点:一棵树中,没有双亲结点的结点;如上图:A

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


1.2 树的表现形式:

树有多种表现方式,如双亲表示法,孩子表示法、孩子双亲表示法、孩子兄弟表示法,下图为孩子兄弟表示法

我们在操作一棵树时,主要操作的结点,对每一个树的结点进行操作,所以我的 Tree 类中会定义结点类 Tree Node 

class Node {    
        int value;              // 树中存储的数据    
        Node firstChild;        // 第一个孩子引用    
        Node nextBrother;       // 下一个兄弟引用
}


二、二叉树

2.1 二叉树的概念

二叉树是树的一种,它的特点是每个结点的度最大为2,并且两边分别称为 左子树 ,右子树

2.2 两种特殊的二叉树

满二叉树:所有结点都是满的,如果一棵二叉树的层数为K,且结点总数是 2^{k}-1,则它就是满二叉树。

完全二叉树:从左往右,从上往下,完全二叉树是一棵深度最小的二叉树,其除了最后一层可能不是满的,其他每一层都必须是满的,并且节点从左到右依次排列。


2.3 相关性质:

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})上取整


5. 完全二叉树通常使用数组来表示,因为它的特性能够通过数组的索引来 快速定位 每个节点的位置。在数组中,根节点位于索引0,如果一个节点的索引为i,那么它的左子节点索引为2i+1右子节点索引为2i+2


6.给定结点数,求叶子结点数:

2.4 二叉树的基本操作:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public abstract class BinaryTree {
    public class TreeNode{
       public int val;
       public TreeNode left;
       public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    // 获取树中节点的个数
   public int size(TreeNode root){
       if(root==null){
           return 0;
       }
        return size(root.left)+ size(root.right) + 1;
   }
   // 获取叶子节点的个数
   public int getLeafNodeCount(TreeNode 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(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(root!=null && k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
                getKLevelNodeCount(root.right,k-1);
    }


    // 获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.max(leftHeight,rightHeight)+1;
    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        } else {

            if (root.left != null) {
                find(root.left, val);
                return root.left;
            }
            if (root.right != null) {
                find(root.right, val);
                return root.right;
            }
            return null;
        }
    }
    //层序遍历
    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);
            }
        }
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null){ //记得判空
            return ret;
        }
        Queue <TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){//用方法不是null

            int size = queue.size();//size不是length
            List<Integer> retsamll  =  new ArrayList<>();

            while(size!=0){
                TreeNode cur = queue.poll();//在循环内,每次cur都是队列出去的元素
                retsamll.add(cur.val);//在循环内,把一行的元素都添加完

                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                size--;//记得把size最终变成小于零的,这样就进行下一列了
            }
            ret.add(retsamll);
        }
        return ret;
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){

        return false;
    }
}

方法未完待续........

二叉树的层序遍历

判断是否是完全二叉树


http://www.kler.cn/a/588437.html

相关文章:

  • DVWA 命令注入从 Low 到 Impossible 教程及源码分析
  • 监控易对各类服务器硬件的广泛支持和深入监控能力
  • pybind11出现的问题
  • 每天五分钟深度学习框架pytorch:常见神经网络层的维度信息总结
  • Linux mount和SSD分区
  • 垃圾回收机制是什么 ?JVM 核心结构?
  • Linux-进程概念
  • 麒麟服务器操作系统Sqlite部署手册
  • 笔记:代码随想录算法训练营day48:739. 每日温度\496.下一个更大元素 I\503.下一个更大元素II
  • 【专项测试】限流测试
  • Java算法OJ(12)
  • Vue 3 组件库主题化与可扩展性深度剖析:设计模式与实现策略 - 构建灵活适应多场景的组件库架构
  • Java缓存String(字符串常量池)、Integer (-128 到 127 )
  • 计算机基础:二进制基础12,十进制数转换为十六进制
  • 联想台式电脑启动项没有U盘
  • 【医学影像 AI】大型语言模型生成 ROP 患者信息材料的能力
  • 编程题《牛牛的链表删除》的python可以用非链表的方式
  • 某省政务信创案例:3阶段实施×5类工具链选型经验分享
  • Word 小黑第18套
  • 用DasViewer的时候3Dtiles 转osgb 可以直接指定目标坐标系吗?