recherche
MaisonJavajavaDidacticielQuelles sont les connaissances et concepts de base des arbres binaires en Java ?

    1. Structure arborescente

    1.1 Concept

    L'arbre est une structure de données non linéaire, qui est un ensemble de relations hiérarchiques composées de n (n>=0) nœuds limités. On l’appelle arbre parce qu’il ressemble à un arbre à l’envers, c’est-à-dire qu’il a les racines tournées vers le haut et les feuilles tournées vers le bas.

    Quelles sont les connaissances et concepts de base des arbres binaires en Java ?

    1.2 Concept (Important)

    a Le degré du nœud : le nombre de sous-arbres du nœud comme indiqué ci-dessus : le degré de A est 6, le degré de J est 2

    b. degré de l'arbre : le numéro de l'arbre , le degré du plus grand nœud est le degré du nombre comme indiqué dans la figure ci-dessus : le degré de l'arbre est 6

    c Nœud feuille (nœud terminal) : a. nœud de degré 0 (nœud sans sous-arbre)

    d. Nœud parent Point/nœud parent : Comme indiqué dans l'image ci-dessus : D est le nœud parent de H

    Nœud enfant/nœud enfant : Comme indiqué dans l'image ci-dessus : H est le nœud enfant de D

    e. Nœud racine : Un nœud sans parents comme indiqué dans l'image ci-dessus : A

    f .Le niveau du nœud : à partir de la définition de la racine, la racine est le premier niveau, les nœuds enfants de la racine sont le deuxième niveau, et ainsi de suite ;

    g La hauteur ou la profondeur de l'arbre : le niveau maximum du nœud dans l'arbre comme indiqué ci-dessus : La hauteur de l'arbre est. 4

    2. Arbre binaire (point clé)

    2.1 Concept

    Chaque nœud a au plus deux sous-arbres, degré

    2.2 La forme de base de l'arbre binaire

    Quelles sont les connaissances et concepts de base des arbres binaires en Java ?

    2.3 Deux types d'arbre binaire spécial

    Quelles sont les connaissances et concepts de base des arbres binaires en Java ?

    a. Arbre binaire complet : le degré non cotylédon est 2

    b Arbre binaire complet : il manque le "coin inférieur droit" de l'arbre binaire

    2.4 Propriétés des arbres binaires

    a. arbre

    1. La hauteur est K, alors il y a 2^k-1 nœuds

    2 Le niveau est K, alors la couche a 2^(k-1) nœuds

    3. de nœuds - 1

    4. Il y a n0 de degré 0 et n2 de degré 2, alors n0 = n2 + 1

    b Arbre binaire complet

    1. enfant gauche

    2. Il ne peut y avoir qu'un seul nœud de degré 1

    2.5 Stockage de l'arbre binaire

    La structure de stockage de l'arbre binaire est divisée en : stockage séquentiel et stockage lié similaire à la liste chaînée.

    Stockage séquentiel : seuls les arbres binaires complets peuvent être stockés

    Stockage en chaîne : arbres binaires ordinaires

    Cette fois, nous montrons le stockage en chaîne

    Le stockage en chaîne des arbres binaires est référencé par les nœuds un par un La représentation commune est binaire et. représentation ternaire,

    Quelles sont les connaissances et concepts de base des arbres binaires en Java ?

    prenez cette photo comme exemple, les détails sont les suivants :

    // 孩子表示法
    private static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;
     
        public TreeNode(char val) {
            this.val = val;
        }
    }

    Initialisation :

        public static TreeNode build(){
            TreeNode nodeA=new TreeNode('A');
            TreeNode nodeB=new TreeNode('B');
            TreeNode nodeC=new TreeNode('C');
            TreeNode nodeD=new TreeNode('D');
            TreeNode nodeE=new TreeNode('E');
            TreeNode nodeF=new TreeNode('F');
            TreeNode nodeG=new TreeNode('G');
            TreeNode nodeH=new TreeNode('H');
            nodeA.left=nodeB;
            nodeA.right=nodeC;
            nodeB.left=nodeD;
            nodeB.right=nodeE;
            nodeE.right=nodeH;
            nodeC.left=nodeF;
            nodeC.right=nodeG;
            return nodeA;
        }

    2.6 Opérations de base des arbres binaires

    2.6.1 Traversée d'arbre binaire (récursion)

    1. NLR : ancien parcours de précommande (également connu sous le nom de parcours de précommande) - visitez le nœud racine ---> le sous-arbre gauche de la racine --->

        //先序遍历 : 根左右
        public static void preOrder(TreeNode root){
            if(root==null){
                return;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

    2. LNR : Inorder Traversal (Inorder Traversal)—— Le sous-arbre gauche de la racine --->

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

    3. LRN : Postorder Traversal - sous-arbre gauche de la racine ---> sous-arbre droit du nœud racine --->

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

    2.6.2 Traversée d'arbre binaire (itération)

    1. Traversée de pré-ordre

        //方法2(迭代)
        //先序遍历 (迭代)
        public static void preOrderNonRecursion(TreeNode root){
            if(root==null){
                return ;
            }
            Deque<TreeNode> stack=new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode cur=stack.pop();
                System.out.print(cur.val+" ");
                if(cur.right!=null){
                    stack.push(cur.right);
                }
                if(cur.left!=null){
                    stack.push(cur.left);
                }
            }
        }

    2. Traversée d'ordre inverse

        //方法2(迭代)
        //中序遍历 (迭代)
        public static void inorderTraversalNonRecursion(TreeNode root) {
            if(root==null){
                return ;
            }
     
            Deque<TreeNode> stack=new LinkedList<>();
            // 当前走到的节点
            TreeNode cur=root;
            while (!stack.isEmpty() || cur!=null){
                // 不管三七二十一,先一路向左走到根儿~
                while (cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
                // 此时cur为空,说明走到了null,此时栈顶就存放了左树为空的节点
                cur=stack.pop();
                System.out.print(cur.val+" ");
                // 继续访问右子树
                cur=cur.right;
            }
        }

    3. nœuds (récursion et itération)

        //方法2(迭代)
        //后序遍历 (迭代)
        public static void postOrderNonRecursion(TreeNode root){
            if(root==null){
                return;
            }
            Deque<TreeNode> stack=new LinkedList<>();
            TreeNode cur=root;
            TreeNode prev=null;
     
            while (!stack.isEmpty() || cur!=null){
                while (cur!=null){
                    stack.push(cur);
                    cur=cur.left;
                }
     
                cur=stack.pop();
                if(cur.right==null || prev==cur.right){
                    System.out.print(cur.val+" ");
                    prev=cur;
                    cur=null;
                }else {
                    stack.push(cur);
                    cur=cur.right;
                }
            }
        }

    2. Trouvez le nombre de nœuds feuilles (récursion et itération)

        //方法1(递归)
        //传入一颗二叉树的根节点,就能统计出当前二叉树中一共有多少个节点,返回节点数
        //此时的访问就不再是输出节点值,而是计数器 + 1操作
        public static int getNodes(TreeNode root){
            if(root==null){
                return 0;
            }
            return 1+getNodes(root.left)+getNodes(root.right);
        }
     
        //方法2(迭代)
        //使用层序遍历来统计当前树中的节点个数
        public static int getNodesNoRecursion(TreeNode root){
            if(root==null){
                return 0;
            }
            int size=0;
            Deque<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                size++;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            return size;
        }

    3 Trouvez le nombre de nœuds dans la kème couche

        //方法1(递归)
        //传入一颗二叉树的根节点,就能统计出当前二叉树的叶子结点个数
        public static int getLeafNodes(TreeNode root){
            if(root==null){
                return 0;
            }
            if(root.left==null && root.right==null){
                return 1;
            }
            return getLeafNodes(root.left)+getLeafNodes(root.right);
        }
     
        //方法2(迭代)
        //使用层序遍历来统计叶子结点的个数
        public static int getLeafNodesNoRecursion(TreeNode root){
            if(root==null){
                return 0;
            }
            int size=0;
            Deque<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()){
                TreeNode cur=queue.poll();
                if(cur.left==null && cur.right==null){
                    size++;
                }
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            return size;
        }

    4. Trouvez la hauteur de l'arbre

        //求出以root为根节点的二叉树第k层的节点个数
        public static int getKLevelNodes(TreeNode root,int k){
            if(root==null || k<=0){
                return 0;
            }
            if(k==1){
                return 1;
            }
            return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
        }

    . 5. Déterminez s'il existe un nœud avec une valeur dans le numéro de l'arbre binaire

        //传入一个以root为根节点的二叉树,就能求出该树的高度
        public static int height(TreeNode root){
            if(root==null){
                return 0;
            }
            return 1+ Math.max(height(root.left),height(root.right));
        }

    2.7 Parcours par ordre de niveau de l'arbre binaire

        //判断当前以root为根节点的二叉树中是否包含指定元素val,
        //若存在返回true,不存在返回false
        public static boolean contains(TreeNode root,char value){
            if(root==null){
                return false;
            }
            if(root.val==value){
                return true;
            }
            return contains(root.left,value) || contains(root.right,value);
        }

    Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

    Déclaration
    Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer
    带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

    Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

    完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

    一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

    详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

    本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

    Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

    java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

    封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

    归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

    本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

    See all articles

    Outils d'IA chauds

    Undresser.AI Undress

    Undresser.AI Undress

    Application basée sur l'IA pour créer des photos de nu réalistes

    AI Clothes Remover

    AI Clothes Remover

    Outil d'IA en ligne pour supprimer les vêtements des photos.

    Undress AI Tool

    Undress AI Tool

    Images de déshabillage gratuites

    Clothoff.io

    Clothoff.io

    Dissolvant de vêtements AI

    AI Hentai Generator

    AI Hentai Generator

    Générez AI Hentai gratuitement.

    Article chaud

    R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
    2 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌
    Repo: Comment relancer ses coéquipiers
    4 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌
    Hello Kitty Island Adventure: Comment obtenir des graines géantes
    4 Il y a quelques semainesBy尊渡假赌尊渡假赌尊渡假赌

    Outils chauds

    Navigateur d'examen sécurisé

    Navigateur d'examen sécurisé

    Safe Exam Browser est un environnement de navigation sécurisé permettant de passer des examens en ligne en toute sécurité. Ce logiciel transforme n'importe quel ordinateur en poste de travail sécurisé. Il contrôle l'accès à n'importe quel utilitaire et empêche les étudiants d'utiliser des ressources non autorisées.

    DVWA

    DVWA

    Damn Vulnerable Web App (DVWA) est une application Web PHP/MySQL très vulnérable. Ses principaux objectifs sont d'aider les professionnels de la sécurité à tester leurs compétences et leurs outils dans un environnement juridique, d'aider les développeurs Web à mieux comprendre le processus de sécurisation des applications Web et d'aider les enseignants/étudiants à enseigner/apprendre dans un environnement de classe. Application Web sécurité. L'objectif de DVWA est de mettre en pratique certaines des vulnérabilités Web les plus courantes via une interface simple et directe, avec différents degrés de difficulté. Veuillez noter que ce logiciel

    SublimeText3 version anglaise

    SublimeText3 version anglaise

    Recommandé : version Win, prend en charge les invites de code !

    Version crackée d'EditPlus en chinois

    Version crackée d'EditPlus en chinois

    Petite taille, coloration syntaxique, ne prend pas en charge la fonction d'invite de code

    SublimeText3 Linux nouvelle version

    SublimeText3 Linux nouvelle version

    Dernière version de SublimeText3 Linux