双向链表，二叉树，哈弗曼树的构建

 **************************************************双向链表********************************************

我们已经写过单链表了，为了更好的实现增删操作，我们可以构建想想链表

既然是双向链表，肯定是父节点能够找到子节点，子节点能够找到父节点。

既然是链表，那它的物理位置可以不相邻，如果相邻那就是数组了。

在双向链表中，节点除含有数据域外，还有两个链域，一个存储直接子地点地址，一般

被称为右链域，一个存储直接父节点地址，一般称为左链域。

                    数据1                     数据2                   数据3

 

下面，我来谈谈双向链表的构建：

首先肯定要有节点类：

 class LinkNode{

  //节点类里面要包含一些属性和方法

 private Object obj ;   // 数据对象

 private  LinkNode child ; //节点的右链域

 private  LinkNode parent ; //节点的左链域

 public LinkNode(Object obj) ;  //传递数据，进行构造

 public void setObj(); //修改数据

 public Object getObj();//得到数据

 public void setChild(LinkNode child); //设置右链域孩子节点

 public LinkNode getChild(); //得到右链域孩子节点

 public void setParent(LinkNode parent); //设置左链域父节点

 public LinkNode getParent() //;得到左链域父节点

 }

因为要实现一个链表，肯定要数据来测试，所以在这里我写了一个学生

类来用来测验：

class Student{

private String name ; //名字
private int score ; //学分

public void setName(String name); //设置名字
public String getName() ;//得到名字

public void setScore(int score);//设置学分
public int getScore() ;//得到学分
}

下面来实现链表类：

//在这里我参照了学长的Hash表存储

class LinkList{

  LinkNode front =  null ;

  LinkNode last = null ;

  Student[] stu = new Student[5];

 public void add(Student s) ; //往链表中添加元素

 public int hashKey(Student stu); //得到关键值

 public void isPut() ; //冲突的处理

 public int  getLength() ;//得到链表的长度

 public LinkNode getLinkNode(int index);   //根据索引取出节点
 public void deleteLinkNode(int index) ;  //根据指定位置删除节点

 public  void deleteHash(int index) ; //删除某个对象在Hash数组上的储存
 public void printList(LinkNode root); //遍历链表

}

 
 

//程序功能基本已经实现

************************************************二叉树****************************************

什么是树？

树是由一个或多个结点组成的有限集合，其中：

⒈必有一个特定的称为根(ROOT)的结点；

⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

2.树的深度——组成该树各结点的最大层次，如上图，其深度为3；

3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；

4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树

二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——(a)；

  

(2)只有一个根结点的二叉树——(b)；

(3)只有左子树——(c)；

(4)只有右子树——(d)；

(5)完全二叉树——(e)

下面是二叉树的实现：

首先，我们同样要有节点类:

class TreeNode{
  //定义数据域
 private Object obj ;
  //指向左孩子
 private TreeNode lChild ;
  //指向右孩子
 private TreeNode rChild ;
  //传入要构造的数据
 public TreeNode(Object obj) ;

  //修改数据域
 public void setObj(Object obj) ;

  //得到数据
 public Object getObj() ;

 //设置左孩子
 public void setLChild(TreeNode lChild);

  //得到左孩子
public TreeNode getLChild();

 //设置右孩子
 public void setRChild(TreeNode rChild) ;

  //得到右孩子
public TreeNode getRChild();    
}

其次要有实现类，这里我参考了其他同学用到的栈存储

public class TreeTest{

private static TreeNode root ;

private static Stack sk = new Stack(); //实例化栈

 public static void main(String args[])  ;//主函数

 public void buildTree() ;   //建立二叉树
 public void midOrder(TreeNode root) ;  //中序遍历二叉树

  public void posOrder(TreeNode root); //后序遍历二叉树，得到逆波兰式，同时用栈计算出值

 }

 

下面是实现一个栈

class Stack{
//往栈中添加一个元素
  void add(int e) ;
//删除一个元素
  int delete();
//判断栈是否为空
 boolean isEmpty();
//求得栈的长度
 int lengthGet() ;
//清空栈
 void initStack();
}

这方面做得不是很好，下次我找到更好的方法我在来改进。

******************************************************哈夫曼树********************************************

1.哈弗曼二叉树的特点
 1.左子树必须要小于右子树。
 2.先要对数据进行排序。
  排序的两种方式：
   1.统计每一个字符出现的次数，创建Node节点，根据节点中的次数进行排序（排序的方法需要你自己编写），去创建哈弗满二叉树。
   2.统计每一个字符出现的次数，创建Node节点，存入到PriorityQueue中，去创建哈弗满二叉树。
 3.开始遍历哈弗曼二叉树，得到每一个叶子节点至根节点的编码。
 4.得到码表。

下面来构造哈夫曼树：

同样，首先要有节点类：

 class TreeNode{
 private Object obj ;//数据
 private int weight ; //权值
 private TreeNode parent = null; //父节点
 private TreeNode LChild = null; //左孩子
 private TreeNode RChild = null; //右孩子
 private String pos  ; //该节点的位置，左边1，右边0
 //创造叶子节点
public TreeNode(Object obj,int weight) ;

 //创造非叶子节点
public TreeNode(int weight) ;

public Object getObj() ;

public int getWeight() ;

public TreeNode getParent() ;

public void setParent(TreeNode parent);

public TreeNode getLeft() ;

public void setLChild(TreeNode lChild) ;

public TreeNode getLChild() ;

public TreeNode getRChild() ;

public void setRChild(TreeNode rChild) ;

public String getPos() ;

public void setPos(int pos) ;

}

下面实现哈夫曼树：

class HFMTree{
  private TreeNode[] leaf=null ; //叶子数组
  private int length=0 ; //叶子数组的长度
  private int size = 0 ;
  private TreeNode root=null ; //初始化Node
  String sum = "" ;
//添加叶子节点
public void addLeafNode(Object obj,int weight ) ;

//构造函数，传递叶子数
public HFMTree(int size) ;

//给节点排序
public TreeNode[] SortTreeNode(TreeNode[] nodes) ;

 //叶子数组减少
public TreeNode[] DeleteTreeNode(TreeNode[] nodes,int num ) ;

 //构造哈夫曼树,从下往上建，建好就只剩根节点
 public TreeNode createHFMTree() ;

//输出哈夫曼树
 public void printHFMTree(TreeNode root,String str) ;

//打包
public void test() ; 

}
public class HFMTreeDemo{
 public static void main(String args[])
 {
  HFMTree test = new HFMTree(5);
  test.addLeafNode("E",1) ;
  test.addLeafNode("M",2) ;
  test.addLeafNode("C",3) ;
  test.addLeafNode("A",3) ;
  test.addLeafNode("D",4) ;
  test.test();
  
 }
 }