【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码（一）

5.4.1 方式

• 四种方式可以建立二叉树

1. 由先根和中根遍历序列建二叉树
   
2. 由后根和中根遍历序列建二叉树
   
3. 由标明空子树的先根遍历建立二叉树
   
4. 由完全二叉树的顺序存储结构建立二叉链式存储结构
   

5.4.2 由先根和中根遍历序列建二叉树

1）先根和中根原理

• 总结：

• 通过先序遍历获得根结点（第一个结点）。
  
• 通过根结点在中序遍历确定左子树和右子树。
  

2）实例分析

3）练习

• 练习1：

已经二叉树，先序序列为abcdefg，中序序列为cbdaegf，重建二叉树？

练习2：

已经二叉树，前序遍历序列为{1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}，后序遍历序列是？

练习3：

已知一棵树二叉树的先根遍历和中根遍历的序列分别为：A B D G H C E F I和G D H B A E C I F，请画出此二叉树，并写出它的后根遍的序列？

4）算法

/** 例如：new BiTree("ABDEGCFH","DBGEAFHC",0,0,8);* @param preOrder 先序遍历序列* @param inOrder  中序遍历序列* @param preIndex 在preOrder中开始位置* @param inIndex  在inOrder中开始位置* @param count 结点数*/publicBiTree(StringpreOrder,StringinOrder,intpreIndex,intinIndex,intcount) {
if(count>0) {
//1 通过先序获得根结点charr=preOrder.charAt(preIndex);
//2 中序中，根结点的位置inti=0 ;
for(; i<count ; i++) {
if(r==inOrder.charAt(i+inIndex)) {
break;
            }
        }
//3 通过中序，截取左子树和右子树root=newBiTreeNode(r);
root.lchild=newBiTree(preOrder,inOrder,preIndex+1, inIndex, i).root;
root.rchild=newBiTree(preOrder,inOrder,preIndex+1+i,inIndex+i+1, count-i-1).root;
    }
}

5.4.3 由后根和中根遍历序列建二叉树

1）后根和中根原理

总结：

• 通过后序遍历获得根结点（最后一个结点）。
  
• 通过根结点在中序遍历确定左子树和右子树。
  

2）练习

• 练习1：

已知二叉树，中根遍历序列为：9,3,15,20,7、后根遍历序列为：9,15,7,20,3，重建二叉树？

练习2：

已知二叉树，中根遍历序列为：6,3,4,1,5,8,2,7、后根遍历序列为：3,6,1,8,5,7,2,4，前根遍历序列？

练习3：

已知一棵树二叉树的后根遍历和中根遍历的序列分别为：A C D B G I H F E和A B C D E F G H I，请画出该二叉树，并写出它的先根遍历的序列

5.4.4 由标明空子树的先根遍历建立二叉树

1）概述

• 仅使用先根遍历序列无法唯一确定一颗二叉树，例如：“AB”，B可以是左孩子，也可以是右孩子。
  
• 在先根遍历序列中加入==空树==信息，从而确定结点与双亲、孩子与兄弟间的关系，从而唯一确定一颗二叉树。
  
• 空树：以字符“#”表示
  
• 根节点A：以字符串“A##”表示
  
• 下图树，以字符串“AB#C##D##”表示
  

2）算法

• 建立二叉链表算法分析：

• 若读取的字符是“#”，则建立空树；否则
  

1. 建立根节点
   
2. 递归建立左子树的二叉链表
   

1. 递归建立右子树的二叉
   

• 算法
  

privateintindex=0;          //用于记录preStr的索引值publicBiTree(StringpreStr) {
charc=preStr.charAt(index++);
if(c!='#') {
root=newBiTreeNode(c);
root.lchild=newBiTree(preStr).root;
root.rchild=newBiTree(preStr).root;
    } else {
root=null;
    }
}