二叉树遍历_JAVA_编程开发_程序员俱乐部

   最近在做哈弗曼压缩，然后就用到了哈夫曼树啊，自然会涉及到哈夫曼树的遍历。于是就找了一些比较棒的例子，给大家分享一下。

一、基本概念
每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。
性质：
1、非空hashu.html" target="_blank">二叉树的第n层上至多有2^(n-1)个元素。
2、深度为h的二叉树至多有2^h-1个结点。
满二叉树：所有终端都在同一层次，且非终端结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。
完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。
对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。

二、二叉树的遍历
遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

具体的代码示例：
class Node {
Node left;
Node right;
int data;
Character c;
String code = "";
}

// 定义打印哈夫曼树的方法 前序遍历
private void printCode_f(Node node) {
if (node != null) {
System.out.println(node.c + "[" + node.data + "]" + node.code);
if (node.left != null) {
printCode_f(node.left);
} else if (node.right != null) {
printCode_f(node.right);
}
}
}

// 定义打印哈夫曼树的方法 中序遍历
private void printCode_z(Node node) {
if (node != null) {
if (node.left != null) {
// System.out.println(node.left.c + "[" + node.left.data + "]"
// + node.left.code);
printCode_z(node.left);
}
System.out.println(node.c + "[" + node.data + "]" + node.code);
if (node.right != null) {
printCode_z(node.right);
// System.out.println(node.right.c + "[" + node.right.data + "]"
// + node.right.code);
}
}
}

// 定义打印哈夫曼树的方法 后序遍历
private void printCode_l(Node node) {
if (node != null) {
if(node.left != null){
printCode_l(node.left);
}else if(node.right!=null){
printCode_l(node.right);
}
System.out.println(node.c + "[" + node.data + "]" + node.code);
}
}


代码错误，希望指正。

• 
• 大小: 67.8 KB

• 查看图片附件