1 霍夫曼树整体的前序遍历 public static void preHufOrder(Node node) { if (node != null) { //每次都会先判断当前节点是否为空，造成重复判断，可以在调用该函数时进行判断的方法进行改善 System.o
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;
}
}
