首页 > 其他分享 >五、树和二叉树

五、树和二叉树

时间：2024-09-11 22:49:29浏览次数：3  
标签：结点 right bn BinaryNode left null 二叉树

文章目录

一、树的引入

在这里插入图片描述

二、树的术语

在这里插入图片描述

三、二叉树

3.1 二叉树的概念

在这里插入图片描述

在这里插入图片描述

3.2 二叉树的遍历

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class BinaryTreeDemo<T> {
    private BinaryNode<T> root;

    public BinaryTreeDemo(BinaryNode<T> root) {
        this.root = root;
    }

    public static void main(String[] args) {
        BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);
        BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);
        BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);
        BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);
        BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);
        node1.left = node2;
        node1.right = node3;
        node3.left = node5;
        node3.right = node4;

        BinaryTreeDemo<String> stringBinaryTreeDemo = new BinaryTreeDemo<String>(node1);

        System.out.println("先序遍历");
        stringBinaryTreeDemo.preOrder(); // 先序遍历
        System.out.println();
        System.out.println("中序遍历");
        stringBinaryTreeDemo.midOrder(); // 中序遍历
        System.out.println();
        System.out.println("后序遍历");
        stringBinaryTreeDemo.afterOrder(); // 后序遍历

    }

    // 先序遍历
    public void preOrder() {
        if (root == null) {
            System.out.println("二叉树为空无法判定");
            return;
        }
        preOrder(root);
    }

    private void preOrder(BinaryNode<T> bn) {
        System.out.println(bn.data);
        if (bn.left != null) {
            preOrder(bn.left);
        }
        if (bn.right != null) {
            preOrder(bn.right);
        }
    }

    // 中序遍历
    public void midOrder() {
        if (root == null) {
            System.out.println("二叉树为空无法判定");
            return;
        }
        midOrder(root);
    }

    private void midOrder(BinaryNode<T> bn) {
        if (bn.left != null) {
            midOrder(bn.left);
        }
        System.out.println(bn.data);
        if (bn.right != null) {
            midOrder(bn.right);
        }
    }

    // 后序遍历
    public void afterOrder() {
        if (root == null) {
            System.out.println("二叉树为空无法判定");
            return;
        }
        afterOrder(root);
    }

    private void afterOrder(BinaryNode<T> bn) {
        if (bn.left != null) {
            afterOrder(bn.left);
        }
        if (bn.right != null) {
            afterOrder(bn.right);
        }
        System.out.println(bn.data);
    }

}

class BinaryNode<T> {
    T data;
    BinaryNode<T> left;
    BinaryNode<T> right;

    public BinaryNode(T data, BinaryNode<T> left, BinaryNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

3.3 二叉树-查找指定结点

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class BinaryTreeSearch<T> {
    BinaryNode<T> root;

    public static void main(String[] args) {
        BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);
        BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);
        BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);
        BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);
        BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);
        node1.left = node2;
        node1.right = node3;
        node3.left = node5;
        node3.right = node4;

        BinaryTreeSearch<String> stringBinaryTreeSearch = new BinaryTreeSearch<>(node1);
        System.out.println(stringBinaryTreeSearch.preSearch("1")); // 前序查找
        System.out.println(stringBinaryTreeSearch.midSearch("林冲")); // 中序查找
        System.out.println(stringBinaryTreeSearch.afterSearch("林冲")); // 后序查找

    }

    public BinaryTreeSearch(BinaryNode<T> root) {
        this.root = root;
    }

    public BinaryNode<T> preSearch(T d) {
        if (root == null) {
            return null;
        }
        return preSearch(root, d);
    }

    private BinaryNode<T> preSearch(BinaryNode<T> bn, T d) {
        if (bn.data.equals(d)) {
            return bn;
        }
        BinaryNode<T> resNode;
        if (bn.left != null) {
            // 左递归前序查找，找到结点，则返回，否则继续判断
            if ((resNode = preSearch(bn.left, d)) != null) return resNode;
        }
        if (bn.right != null) {
            if ((resNode = preSearch(bn.right, d)) != null) return resNode;
        }
        return null;
    }

    public BinaryNode<T> midSearch(T d) {
        if (root == null) {
            return null;
        }
        return midSearch(root, d);
    }

    private BinaryNode<T> midSearch(BinaryNode<T> bn, T d) {
        BinaryNode<T> resNode;
        if (bn.left != null) {
            // 左递归前序查找，找到结点，则返回，否则继续判断
            if ((resNode = midSearch(bn.left, d)) != null) return resNode;
        }
        if (bn.data.equals(d)) {
            return bn;
        }
        if (bn.right != null) {
            if ((resNode = midSearch(bn.right, d)) != null) return resNode;
        }
        return null;
    }


    public BinaryNode<T> afterSearch(T d) {
        if (root == null) {
            return null;
        }
        return afterSearch(root, d);
    }

    private BinaryNode<T> afterSearch(BinaryNode<T> bn, T d) {
        BinaryNode<T> resNode;
        if (bn.left != null) {
            // 左递归前序查找，找到结点，则返回，否则继续判断
            if ((resNode = midSearch(bn.left, d)) != null) return resNode;
        }
        if (bn.right != null) {
            if ((resNode = midSearch(bn.right, d)) != null) return resNode;
        }
        if (bn.data.equals(d)) {
            return bn;
        }
        return null;
    }

}

3.3 二叉树-删除结点

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class BinaryRemove<T> {
    BinaryNode<T> root;

    public static void main(String[] args) {
        BinaryNode<String> node1 = new BinaryNode<>("宋江", null, null);
        BinaryNode<String> node2 = new BinaryNode<>("吴用", null, null);
        BinaryNode<String> node3 = new BinaryNode<>("卢俊", null, null);
        BinaryNode<String> node4 = new BinaryNode<>("林冲", null, null);
        BinaryNode<String> node5 = new BinaryNode<>("关胜", null, null);
        node1.left = node2;
        node1.right = node3;
        node3.left = node5;
        node3.right = node4;

        BinaryRemove<String> stringBinaryRemove = new BinaryRemove<String>(node1);
        System.out.println(stringBinaryRemove.delete("关胜"));
    }

    public BinaryRemove(BinaryNode<T> root) {
        this.root = root;
    }

    public boolean delete(T d) {
        if (root == null) {
            return false;
        }
        if (root.data.equals(d)) {
            root = null;
            return true;
        }
        return delete(root, d);
    }

    private boolean delete(BinaryNode<T> bn, T d) {

        // 已经是叶子结点，因此没有对应的数据
        if (bn.left == null && bn.right == null) {
            return false;
        }

        // 左子树的根节点是要删除的元素
        if (bn.left != null && bn.left.data.equals(d)) {
//            bn.left = null;
            if (bn.left.left == null && bn.left.right == null) {
                bn.left = null; // 叶子结点直接删除
            } else if (bn.left.left == null) {
                bn.left = bn.left.right; // 右边有则加入右边
            } else {
                bn.left = bn.left.left; // 左边有或两边都有则加入左边
            }
            return true;
        }

        // 右子树的根节点是要删除的元素
        if (bn.right != null && bn.right.data.equals(d)) {
//            bn.right = null;
            if (bn.right.left == null && bn.right.right == null) {
                bn.right = null; // 叶子结点直接删除
            } else if (bn.right.left == null) {
                bn.right = bn.right.right; // 右边有则加入右边
            } else {
                bn.right = bn.right.left; // 左边有或两边都有则加入左边
            }
            return true;
        }
        // 左递归删除
        if (bn.left != null) {
            if (delete(bn.left, d)) {
                return true;
            }
        }

        // 右递归删除
        if (bn.right != null) {
            // 若左递归没有删除结点，则右递归结果作为最终的
            return delete(bn.right, d);
        }
        // 没有当前结点的删除，因为当前结点在上一层递归中已作出判断
        return false;
    }

}

3.4 顺序存储二叉树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class ArrBinaryTree {
    int[] arr;

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        new ArrBinaryTree(arr).preSearch();
    }

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preSearch() {
        preSearch(0);
    }

    private void preSearch(int index) {
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，不能遍历");
            return;
        }
        if (index > arr.length - 1) {
            return;
        }
        System.out.println(arr[index]);
        // 遍历左子树
        preSearch(2 * index + 1);
        // 遍历右子树
        preSearch(2 * index + 2);
    }
}

在这里插入图片描述

3.5 线索化二叉树

  • n个结点对应有n+1个空指针域（左指针域与右指针域工2n个）
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

3.5.1 线索化二叉树应用案例

  • 处理核心是得到存在空指针的域的结点，设置当前结点的左指针向前驱结点；设置当前结点的前驱结点的右指针指向自己
    在这里插入图片描述
package com.gyh.tree;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class ThreadedBinaryTreeDemo<T> {

    public static void main(String[] args) {
        ThreadBinaryNode<Integer> node1 = new ThreadBinaryNode<Integer>(1, null, null);
        ThreadBinaryNode<Integer> node2 = new ThreadBinaryNode<Integer>(3, null, null);
        ThreadBinaryNode<Integer> node3 = new ThreadBinaryNode<Integer>(6, null, null);
        ThreadBinaryNode<Integer> node4 = new ThreadBinaryNode<Integer>(8, null, null);
        ThreadBinaryNode<Integer> node5 = new ThreadBinaryNode<Integer>(10, null, null);
        ThreadBinaryNode<Integer> node6 = new ThreadBinaryNode<Integer>(14, null, null);
        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;

        ThreadedBinaryTreeDemo<Integer> binaryTreeDemo = new ThreadedBinaryTreeDemo<>(node1);
        binaryTreeDemo.threadNodes();
        // 测试叶子结点的左右指针指向
        System.out.println("left:" + node5.leftType + " " + node5.left.data);
        System.out.println("left:" + node5.leftType + " " + node5.right.data);
    }

    ThreadBinaryNode<T> root;
    // pre 当前结点对象的前驱结点
    ThreadBinaryNode<T> pre = null;

    public ThreadedBinaryTreeDemo(ThreadBinaryNode<T> root) {
        this.root = root;
    }

    public void threadNodes() {
        if (root == null) {
            return;
        }
        threadNodes(root);
    }

    /**
     * 编写对二叉树进行中序线索化的方法
     *
     * @param cur 当前结点对象
     */
    private void threadNodes(ThreadBinaryNode<T> cur) {
        // 当前结点为空
        if (cur == null) {
            return;
        }

        // 线索化左子树
        threadNodes(cur.left);

        // 线索化当前结点
        // 先处理当前结点的前驱结点
        if (cur.left == null) {
            // 指向前驱结点
            cur.left = pre;
            // 设置左子树表示为前驱结点
            cur.leftType = 1;
        }

        // 处理右指针
        // 是让后继结点处理前驱结点的空指针域（即若前驱结点的右指针域为null，则让其指向当前结点）
        if (pre != null && pre.right == null) {
            // 让前驱结点的右指针指向当前结点
            pre.right = cur;
            // 设置右子树表示为后继结点
            pre.rightType = 1;
        }
        // 每处理一个结点后，让当前结点是下一个结点的前驱结点
        pre = cur;


        // 线索化右子树
        threadNodes(cur.right);


    }

}

class ThreadBinaryNode<T> {
    T data;
    int leftType; // 为0表示指向的是左子树，如果1则表示前驱
    ThreadBinaryNode<T> left;

    int rightType; // 为0表示指向的是右子树，如果1则表示后继
    ThreadBinaryNode<T> right;


    public ThreadBinaryNode(T data, ThreadBinaryNode<T> left, ThreadBinaryNode<T> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public ThreadBinaryNode(T data, int leftType, ThreadBinaryNode<T> left, int rightType, ThreadBinaryNode<T> right) {
        this.data = data;
        this.leftType = leftType;
        this.left = left;
        this.rightType = rightType;
        this.right = right;
    }
}

3.5.2 遍历线索化二叉树

在这里插入图片描述

在这里插入图片描述

public void threadedShow() {
        // 循环找到 leftType == 1的结点，第一个找到就是8结点
        // 结点随着遍历而变化，因为当leftType==1时，说明该节点是按照线索化
        // 处理后的有效结点
        ThreadBinaryNode<T> node = root;
        while (node != null) {
            while (node.leftType == 0) {
                node = node.left;
            }

            System.out.println(node.data);

            // 如果当前结点的右指针指向的是后继节点，就一直输出
            while (node.rightType == 1) {
                // 获取到当前结点的后继节点
                node = node.right;
                System.out.println(node.data);
            }
            // 替换这个遍历的结点
            node = node.right;

        }

3.6 二叉树的应用

3.6.1 堆排序（见 2022.4.5 三、排序算法.md）

3.6.2 赫夫曼树

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

import com.gyh.sort.QuickSort2;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class HuffmanTree {

    public static void main(String[] args) {
        int arr[] = {13, 7, 8, 3, 29, 6, 1};
        Node node = new HuffmanTree().toTree(arr);
        System.out.println(new HuffmanTree().wpl(node, 0));

        // 先序遍历结果
        new HuffmanTree().preOrder(node);
    }

    public void preOrder(Node n) {
        if (n == null) {
            return;
        }
        System.out.println(n.value);
        preOrder(n.left);
        preOrder(n.right);
    }

    /**
     * 计算带权路径长度
     *
     * @param node 根结点
     * @param path 当前结点的路径长度
     * @return
     */
    public int wpl(Node node, int path) {
        if (node == null) {
            return 0;
        } 
        if (node.left == null && node.right == null) {
            return node.value * path; // 叶子结点的带权路径
        }
        return wpl(node.left, path + 1) + wpl(node.right, path + 1);
    }

    public Node toTree(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return null;
        }

//        // 从小到大排序
//        new QuickSort2().sort(nums, true);
        // 从小到大排序并转换为结点
        List<Node> nodes = Arrays.stream(nums)
                .mapToObj(Node::new)
                .collect(Collectors.toList());

        // 作几轮
        while (nodes.size() > 1) {
            // 从小到大排序
            nodes.sort(Comparator.comparingInt(x -> x.value));

            Node node1 = nodes.get(0);
            Node node2 = nodes.get(1);
            Node node = new Node(node1.value + node2.value, node1, node2);

            // 将计算后的结点加入剩余的元素集合中
            nodes.remove(0);
            nodes.remove(0);
            nodes.add(node);
        }

        return nodes.get(0);

    }

}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

3.6.3 赫夫曼编码

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

package com.gyh.tree;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author Gao YongHao
 * @version 1.0
 */
public class HuffmanEncode {
    public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        // 分别统计每个字符的频度
        String[] contentStr = content.split("");
        Map<String, Long> statistic = Stream.of(contentStr)
                .collect(Collectors.groupingBy(m -> m, Collectors.counting()));

        HuffmanEncode huffmanEncode = new HuffmanEncode();
        CodeNode root = huffmanEncode.createHuffmanTree(statistic);
        huffmanEncode.getCode(root);
    }

    public void getCode(CodeNode node) {
        getCode(node, "");
    }

    // 获取每个字符的霍夫曼编码（叶子结点作显示）
    private void getCode(CodeNode node, String prefix) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            System.out.println(node.data + "---->" + prefix);
            return;
        }

        getCode(node.left, prefix + "0");
        getCode(node.right, prefix + "1");
    }

    public CodeNode createHuffmanTree(Map<String, Long> statistic) {
        // 创建结点list
        List<CodeNode> nodes = statistic.entrySet().stream()
                .map(s -> new CodeNode(s.getKey(), s.getValue().intValue()))
                .collect(Collectors.toList());

        while (nodes.size() > 1) {
            // 从小到大排序
            nodes.sort(Comparator.comparingInt(x -> x.weight));
            CodeNode left = nodes.get(0);
            CodeNode right = nodes.get(1);
            CodeNode codeNode = new CodeNode(null, left.weight + right.weight, left, right);
            // 将新结点加入到集合中
            nodes.remove(0);
            nodes.remove(0);
            nodes.add(codeNode);
        }
        return nodes.get(0);

    }
}

class CodeNode {
    String data; // 存放数据本身
    int weight; // 权值，表示数据频度
    CodeNode left;
    CodeNode right;

    public CodeNode(String data, int weight, CodeNode left, CodeNode right) {
        this.data = data;
        this.weight = weight;
        this.left = left;
        this.right = right;
    }

    public CodeNode(String data, int weight) {
        this.data = data;
        this.weight = weight;
    }
}

3.6.4 二叉排序树（见：四、查找算法）

标签：结点,right,bn,BinaryNode,left,null,二叉树
From： https://blog.csdn.net/weixin_44063529/article/details/142136708

相关文章

  • leetcode刷题day13|二叉树Part01（递归遍历、迭代遍历、统一迭代、层序遍历）
    递归遍历思路：使用递归的方式比较简单。1、递归函数的传参：因为最后输出一个数组，所以需要传入根节点和一个容器，本来想写数组，但发现长度不能确定，所以选择list。2、终止条件：当访问的节点为空时，return3、递归函数的逻辑：先访问一个节点，递归访问其他节点144.二叉树的前序遍历......
  • leetcode刷题day14|二叉树Part02（以递归方法为主：226.翻转二叉树、101. 对称二叉树、104
    226.翻转二叉树思路：利用先序遍历递归翻转1、终止条件：节点为空，return2、参数：root3、递归函数逻辑：处理中间节点，交换；递归左孩子，递归右孩子代码如下：classSolution{publicTreeNodeinvertTree(TreeNoderoot){if(root==null)returnroot;swapC......
  • Day13 二叉树part03| LeetCode 110.平衡二叉树，二叉树的所有路径，左叶子之和，完全二叉树
    110.平衡二叉树110.平衡二叉树定义：左右子树的高度差的绝对值不超过1深度：从上到下查——>前序遍历（中左右）高度：从下到上查——>后序遍历（左右中）classSolution{publicbooleanisBalanced(TreeNoderoot){if(getHeight(root)==-1)......
  • NC 序列化二叉树
    系列文章目录文章目录系列文章目录前言前言前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。描述请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字......
  • 二叉树（上）
    目录树型结构概念二叉树概念二叉树的存储 二叉树基本操作基本变量二叉树的遍历完整代码树型结构概念树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 树......
  • 【洛谷 P5076】【深基16.例7】普通二叉树（简化版）题解（多重集合+lower_bound+upper_bound
    【深基16.例7】普通二叉树（简化版）题目描述您需要写一种数据结构，来维护一些数（都是以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数不超过：查询数的排名（排名定义为比当前数小的数的个数。若有多个相同的数，应输出最小的排名）。查询排名为的数。求的前驱（......
  • 力扣热题100 - 二叉树：将有序数组转换为二叉搜索树
    题目描述：题号：108给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。解题思路：思路一：中序构建二叉树选择根节点：首先，选择数组的中间元素作为根节点。这样做可以确保生成的二叉搜索树尽可能平衡。递归构建子树：将数组分......
  • 【代码随想录Day13】二叉树Part01
    理论基础文章讲解：代码随想录二叉树节点的定义：publicclassTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(){}TreeNode(intval){this.val=val;}TreeNode(intval,TreeNodeleft,TreeNoderight){this.val......
  • 【Python】排序算法及二叉树讲解(冒泡 选择 插入 二分查找 二叉树的广度优先和三种深
    排序算法​所谓排序，使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作​排序算法，就是如何使得记录按照要求排列的方法​排序算法在很多领域是非常重要​在大量数据的处理方面：一个优秀的算法可以节省大量的资源。​在各个领域中考虑到数据的......
  • 代码随想录算法 - 二叉树
    题目1226.翻转二叉树给你一棵二叉树的根节点root，翻转这棵二叉树，并返回其根节点。示例1：输入：root=[4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]示例2：输入：root=[2,1,3]输出：[2,3,1]示例3：输入：root=[]输出：[]提示：树中节点数目范围在[0,100]内-100<=Node.val......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99