数据结构与算法__08--霍夫曼树二叉树遍历：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;
    }
 
}