Apakah pengetahuan asas dan konsep pokok binari di Jawa?

1. Struktur pokok

1.1 Konsep

Pokok ialah struktur data bukan linear, yang terdiri daripada n (n> ; =0) nod terhingga membentuk set dengan hubungan hierarki. Ia dipanggil pokok kerana ia kelihatan seperti pokok terbalik, iaitu akarnya menghadap ke atas dan daunnya menghadap ke bawah.

1.2 Konsep (Penting)

a ialah 6, J Darjah pokok ialah 2

b Darjah pokok: Dalam pokok, darjah nod terbesar ialah darjah nombor seperti yang ditunjukkan dalam rajah di atas: darjah pokok ialah 6

c. Nod daun ( Nod terminal): Nod dengan darjah 0 (nod ​​tanpa subpohon)

d : D ialah nod induk H

Nod anak/anak Nod: Seperti yang ditunjukkan dalam gambar di atas: H ialah nod anak bagi D

e. seperti yang ditunjukkan dalam gambar di atas: A

f Tahap nod: Bermula dari akar, akar adalah tahap 1, anak nod adalah tahap ke-2, dan seterusnya; 🎜>g. Ketinggian atau kedalaman pokok: tahap maksimum nod dalam pokok; 🎜>2.1 Konsep

Setiap nod mempunyai paling banyak dua subpokok, darjah

2.2 Bentuk asas pokok binari

2.3 Dua pokok binari istimewa

a hilang "penjuru kanan bawah"

2.4 Sifat pokok binari

a. Pokok binari penuh

1 ialah 2^k-1 nod

2. Tahapnya ialah K, maka lapisan mempunyai 2^(k-1) nod

3 🎜>4. Terdapat n0 untuk darjah 0 dan n2 untuk darjah 2, kemudian n0 = n2 + 1

b Pepohon binari lengkap

1. Jika ada anak kanan, mesti ada anak kiri

2. Hanya boleh ada satu nod dengan darjah 1

2.5 Penyimpanan pokok binari

Penyimpanan binari pokok Struktur terbahagi kepada: storan berurutan dan storan berpaut serupa dengan senarai terpaut.

Penyimpanan berurutan: hanya pokok binari yang lengkap boleh disimpan

Penyimpanan berantai: pokok binari biasa

Kali ini kami menunjukkan storan berantai

Penyimpanan berantai pokok binari dirujuk oleh nod satu demi satu, kaedah perwakilan biasa termasuk perwakilan binari dan tiga,

Ambil gambar ini sebagai contoh, butirannya adalah seperti berikut:

Permulaan:

2.6 Operasi asas pokok binari

2.6.1 Traversal pokok binari (rekursi)

NLR: Preorder traversal (Preorder Traversal (juga dikenali sebagai preorder traversal)—— Lawati nod akar---> subpokok kiri akar---> subpokok kanan akar.

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

2. LNR: Inorder Traversal (Inorder Traversal)—— Subpokok kiri akar --->

    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;
    }

3. LRN: Postorder Traversal—— Subpohon kiri akar --->

2.6.2 Binary tree traversal (iteration)

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

1. Pra-order traversal

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

2 >

3. Laluan selepas pesanan

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

2.6.3 Operasi asas pokok binari

1. Cari bilangan nod (rekursi & lelaran)

    //方法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. Cari bilangan nod daun (rekursi & lelaran)

    //方法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 Cari bilangan nod pada tahap ke-k

    //方法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;
            }
        }
    }

4 ketinggian pokok

5 Tentukan sama ada terdapat nod dengan nilai dalam nombor pepohon binari

    //方法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;
    }

2.7 Traversal tertib aras bagi pokok binari

    //方法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;
    }

Atas ialah kandungan terperinci Apakah pengetahuan asas dan konsep pokok binari di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!