一 : 判断二叉树是否是完全二叉树

题目：

  给出一个二叉树，判断是否是完全二叉树。(www.61k.com］

分析：我们都知道完全二叉树是指最后一层左边是满的，右边可能慢也不能不满，然后其余层都是满的，根据这个特性，利用层遍历，

如果我们当前遍历到了NULL结点即叶结点，那么后续如果还有非叶结点，就说明是非完全二叉树，所以利用队列，代码比较简单了。

View Code

bool is_completeTree(Node* r)
{
queue<Node*> q;
if(NULL != r)
{
q.push(r);
Node* cur = NULL;
bool flag = false;
while(!q.empty())
{
cur = q.front();
q.pop();
if(cur)
{
if(flag)
return false;
q.push(cur->left);
q.push(cur->right);
}
else
flag = true;
}
return true;
}
return true;
}

二 : 哈夫曼树--带权最优二叉树

最优二叉树概念

1．树的路径长度
　树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL)
　　结点的权：在一些应用中，赋予树中结点的1个有某种意义的实数。
　　结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
　　树的带权路径长度(Weighted Path Length ofTree)：定义为树中所有叶结点的带权路径长度之和，通常记为：

其中：

n表示叶子结点的数目
w_i和l_i分别表示叶结点k_i的权值和根到结点k_i之间的路径长度。
树的带权路径长度亦称为树的代价。

3．最优二叉树或哈夫曼树
　在权为w_l，w₂，…，w_n的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树［www.61k.com)或哈夫曼树。
【例】给定四个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：
(a)WPL=7*2+5*2+2*2+4*2=36
(b)WPL=7*3+5*3+2*1+4*2=46
(c)WPL=7*1+5*2+2*3+4*3=35
　　其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

注意：
①叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。
②最优二叉树中，权越大的叶子离根越近。
③最优二叉树的形态不唯一，WPL最小

JAVA算法实现：import java.util.*;
public class HuffmanTree{ //内部类Nodepublic static class Node<E>{E data;double weight;Node leftChild;Node rightChild;
public Node(E data, double weight) {this.data = data;this.weight = weight;}
public String toString() {return "Node[data=" + data + ", weight=" + weight + "]";}}
public static void main(String[] args) {List<Node> nodes = newArrayList<Node>();nodes.add(new Node("A", 40.0));nodes.add(new Node("B", 8.0));nodes.add(new Node("C", 10.0));nodes.add(new Node("D", 30.0));nodes.add(new Node("E", 10.0));nodes.add(new Node("F", 2.0));Node root = HuffmanTree.createTree(nodes);PrintTree(root);}
private static Node createTree(List<Node>nodes) {// 只要nodes数组中还有两个以上的节点while (nodes.size() > 1) {quickSort(nodes);//排序中找到// 获取权值最小的2个节点Node left = nodes.get(nodes.size() - 1);Node right = nodes.get(nodes.size() - 2);// 生成新节点，新节点的权值为2个子节点的权值之和Node parent = new Node(null, left.weight +right.weight);// 让新节点作为权值最小的2个节点的父节点parent.leftChild = left;parent.rightChild = right;// 删除权值最小的2个节点nodes.remove(nodes.size() -1);nodes.remove(nodes.size() -1);// 将新生成的父节点添加到集合中nodes.add(parent);}// 返回nodes集合中唯一的节点，也就是根节点return nodes.get(0);}
// 将指定数组的i和j索引处的元素交换private static voidswap(List<Node> nodes, int i, int j){Node tmp;tmp = nodes.get(i);nodes.set(i, nodes.get(j));nodes.set(j, tmp);}
// 实现快速排序算法，用于对节点进行排序。从大到小的排序private static voidsubSort(List<Node> nodes, int start,int end) {// 需要排序if (start < end) {// 以第1个元素作为分界值Node base = nodes.get(start);// i从左边搜索，搜索大于分界值的元素的索引int i = start;// j从右边开始搜索，搜索小于分界值的元素的索引int j = end + 1;while (true) {// 找到大于分界值的元素的索引，或i已经到了end处while (i < end&& nodes.get(++i).weight>= base.weight);// 找到小于分界值的元素的索引，或j已经到了start处while (j > start&& nodes.get(--j).weight<= base.weight);if (i < j) {swap(nodes, i, j);} else {break;}}swap(nodes, start, j);// 递归左子序列subSort(nodes, start, j - 1);// 递归右边子序列subSort(nodes, j + 1, end);}}
public static voidquickSort(List<Node> nodes) {subSort(nodes, 0, nodes.size() - 1);}
//相当于广度优先遍历，分别打印根节点，在打印左右孩子的，按层的public static void PrintTree(Nodenode) {Node left = null;Node right = null;if (node != null) {System.out.print(node.toString());left = node.leftChild;right = node.rightChild;System.out.println("(" + (left != null ?left.toString() : "")+ "," + (right != null ?right.toString() : "") + ")");} //递归打印if (left != null)PrintTree(left);if (right != null)PrintTree(right);}} 本文标题：哈夫曼树是完全二叉树-判断二叉树是否是完全二叉树
本文地址： http://www.61k.com/1149747.html