数据结构与算法__08--霍夫曼树二叉树遍历:1.写在节点类中,在上层调用;2.写在主函数中一次性整体完成

简介: 霍夫曼树二叉树遍历:1.写在节点类中,在上层调用;2.写在主函数中一次性整体完成

1 霍夫曼树整体的前序遍历

public static void preHufOrder(Node node) {
    if (node != null) { //每次都会先判断当前节点是否为空,造成重复判断,可以在调用该函数时进行判断的方法进行改善
        System.out.println(node);
        if (node.left != null) {
            preHufOrder(node.left);
        }
        if (node.right != null) {
            preHufOrder(node.right);
        }
    } else {
        System.out.println("二叉树为空,无法遍历");
    }
}

2 在节点类创建前序遍历方法,主函数中调用

//在节点类创建前序遍历方法,主函数中调用
 
//主函数中的方法
public static void preOrder(Node root) {
    if (root != null) {
        root.preOrder();
    } else {
        System.out.println("二叉树为空,无法遍历");
    }
}  
 
//节点类中的前序遍历
public void preOrder() {
    System.out.println(this);
    if (this.left != null) {
        this.left.preOrder();
    }
    if (this.right != null) {
        this.right.preOrder();
    }
}

3 完整代码

package edu.seu.demo11huffmantree;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class Demo01HuffmanTree {
    public static void main(String[] args) {
        int arr[] = {13, 7, 8, 3, 29, 6, 1};
        Node root = creatHuffmanTree(arr);
//        System.out.println(root);
        preHufOrder(root);
    }
 
    //在子节点前序遍历,主函数中调用
/*    public static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }  */
    //整体的前序遍历
    public static void preHufOrder(Node node) {
        if (node != null) { //每次都会先判断当前节点是否为空,造成重复判断,可以在调用该函数时进行判断的方法进行改善
            System.out.println(node);
            if (node.left != null) {
                preHufOrder(node.left);
            }
            if (node.right != null) {
                preHufOrder(node.right);
            }
        } else {
            System.out.println("二叉树为空,无法遍历");
        }
    }
 
    /**
     * @param arr 待转换的数组
     * @return 霍夫曼树的根节点
     */
    public static Node creatHuffmanTree(int[] arr) {
        ArrayList<Node> nodes = new ArrayList<>();//创建存取节点的集合
        for (int i : arr) {
            nodes.add(new Node(i));
        }
        while (nodes.size() > 1) {
            Collections.sort(nodes);//对集合升序排列
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            Node parent = new Node(leftNode.value + rightNode.value);//以两个最小节点之和创建新节点
            parent.left = leftNode;
            parent.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
 
        return nodes.get(0);
    }
}
 
class Node implements Comparable<Node> {
    int value;//节点权值
    Node left;//左节点
    Node right;//指向右节点
 
 
    //前序遍历
/*    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }*/
 
    public Node(int value) {
        this.value = value;
    }
 
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
 
    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
 
}
相关文章
|
3月前
|
机器学习/深度学习 算法 安全
深度长文I 深度合成服务类-算法备案该怎么做?
本文详解“深度合成服务类”算法及其备案要求,涵盖定义、类型、备案流程等内容,助你全面理解合规要点。
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
7月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
509 19
|
9月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
194 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
9月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
166 10
|
7天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
10天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
82 11
|
10天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)

热门文章

最新文章