二叉树的java实现
public class BinaryDemo {
public TreeNode root;
public BinaryDemo(TreeNode root)
{
this.root=root;
}
public class TreeNode{
int key;
String data;
TreeNode leftNode;
TreeNode rightNode;
boolean visited=false;
}
public int height(TreeNode subTree)
{
if(subTree==null)
return 0;
int i=height(subTree.leftNode);
int j=height(subTree.rightNode);
return (i<j)?j+1:i+1;
}
public int size(TreeNode subTree)
{
if(subTree==null)
return 0;
return size(subTree.leftNode)+size(subTree.rightNode)+1;
}
public TreeNode getLeft(TreeNode element)
{
return element.leftNode;
}
public TreeNode getRight(TreeNode element)
{
return element.rightNode;
}
public TreeNode getPare(TreeNode subTree){
return (root==null||root==subTree)?null:getPare(root,subTree);
}
private TreeNode getPare(TreeNode subTree,TreeNode element)
{
if(subTree==null)
return null;
if(subTree.leftNode==element||subTree.rightNode==element)
return subTree;
if(getPare(subTree.leftNode,element).leftNode==element||getPare(subTree.leftNode,element).leftNode==element)
return getPare(subTree.leftNode,element);
else
return getPare(subTree.rightNode,element);
}
public void visited(TreeNode element)
{
element.visited=true;
System.out.println("Node"+element.key+":"+element.data);
}
public void destory(TreeNode subTree)
{
if(subTree!=null){
destory(subTree.leftNode);
destory(subTree.rightNode);
subTree=null;
}
}
public void preOrder(TreeNode subTree)
{
visited(subTree);
preOrder(subTree.leftNode);
preOrder(subTree.rightNode);
}
public void midOrder(TreeNode subTree)
{
midOrder(subTree.leftNode);
visited(subTree);
midOrder(subTree.rightNode);
}
public void lateOrder(TreeNode subTree){
lateOrder(subTree);
lateOrder(subTree);
visited(subTree);
}
}
线索二叉树：
按照某种方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列，在该序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点；
在有N个节点的二叉树中需要利用N+1个空指针添加线索，这是因为在N个节点的二叉树 中，每个节点有2个指针，所以一共有2N个指针，除了根节点以外，每一个节点都有一个指针从它的父节点指向它，所以一共使用了N-1个指针，所以剩下 2N-(N-1)也就是N+1个空指针；
若能利用这些空指针域来存放指向该节点的直接前驱或是直接后继的指针，则可由此信息直接找到在该遍历次序下的前驱结点或后继结点，从而比递归遍历提高了遍历速度，节省了建立系统栈所使用的存储空间；
这些被重新利用起来的空指针就被称为线索（Thread），加上了这些线索的二叉树就是线索二叉树；如图：
根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种；
记node指向二叉链表中的一个结点，以下是建立线索的规则：
（1）如果node的左指针域为空，则存放指向某种遍历序列中该结点的前驱结点，这个结点称为node的前驱；
（2）如果node的右指针域为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为node的后继；
public class Node
{
private int data;
private Node left;
private boolean leftIsThread; // 左孩子是否为线索
private Node right;
private boolean rightIsThread; // 右孩子是否为线索
public Node(int data)
{
this.data = data;
this.left = null;
this.leftIsThread = false;
this.right = null;
this.rightIsThread = false;
}
public int getData()
{
return data;
}
public void setData(int data)
{
this.data = data;
}
public Node getLeft()
{
return left;
}
public void setLeft(Node left)
{
this.left = left;
}
public boolean isLeftIsThread()
{
return leftIsThread;
}
public void setLeftIsThread(boolean leftIsThread)
{
this.leftIsThread = leftIsThread;
}
public Node getRight()
{
return right;
}
public void setRight(Node right)
{
this.right = right;
}
public boolean isRightIsThread()
{
return rightIsThread;
}
public void setRightIsThread(boolean rightIsThread)
{
this.rightIsThread = rightIsThread;
}
@Override
public boolean equals(Object obj)
{
if (obj instanceof Node)
{
Node temp = (Node) obj;
if (temp.getData() == this.data)
{
return true;
}
}
return false;
}
@Override
public int hashCode()
{
return super.hashCode() + this.data;
}
}
package tree.thread;
public class ThreadTree
{
private Node root; // 根节点
private int size; // 大小
private Node pre = null; // 线索化的时候保存前驱
public ThreadTree()
{
this.root = null;
this.size = 0;
this.pre = null;
}
public ThreadTree(int[] data)
{
this.pre = null;
this.size = data.length;
this.root = createTree(data, 1); // 创建二叉树
}
/**
* 创建二叉树
*
*/
public Node createTree(int[] data, int index)
{
if (index > data.length)
{
return null;
}
Node node = new Node(data[index - 1]);
Node left = createTree(data, 2 * index);
Node right = createTree(data, 2 * index + 1);
node.setLeft(left);
node.setRight(right);
return node;
}
/**
* 将以root为根节点的二叉树线索化
*
*/
public void inThread(Node root)
{
if (root != null)
{
inThread(root.getLeft()); // 线索化左孩子
if (null == root.getLeft()) // 左孩子为空
{
root.setLeftIsThread(true); // 将左孩子设置为线索
root.setLeft(pre);
}
if (pre != null && null == pre.getRight()) // 右孩子为空
{
pre.setRightIsThread(true);
pre.setRight(root);
}
pre = root;
inThread(root.getRight()); // 线索化右孩子
}
}
/**
* 中序遍历线索二叉树
*
*/
public void inThreadList(Node root)
{
if (root != null)
{
while (root != null && !root.isLeftIsThread()) // 如果左孩子不是线索
{
root = root.getLeft();
}
do
{
System.out.print(root.getData() + ",");
if (root.isRightIsThread()) // 如果右孩子是线索
{
root = root.getRight();
}
else // 有右孩子
{
root = root.getRight();
while (root != null && !root.isLeftIsThread())
{
root = root.getLeft();
}
}
} while (root != null);
}
}
/**
* 前序遍历递归算法
*
*/
public void preList(Node root)
{
if (root != null)
{
System.out.print(root.getData() + ",");
preList(root.getLeft());
preList(root.getRight());
}
}
/**
* 中序遍历
*
*/
public void inList(Node root)
{
if (root != null)
{
inList(root.getLeft());
System.out.print(root.getData() + ",");
inList(root.getRight());
}
}
public Node getRoot()
{
return root;
}
public void setRoot(Node root)
{
this.root = root;
}
public int getSize()
{
return size;
}
public void setSize(int size)
{
this.size = size;
}
}
/** 非递归实现前序遍历 */
protected static void iterativePreorder(Node p) {
Stack<Node> stack = new Stack<Node>();
if (p != null) {
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.getRight() != null)
stack.push(p.getRight());
if (p.getLeft() != null) //为什么p.getLeft() 在后，getRight()在前应为while 循环第一句就是pop visit所以要把left放上，先访问。之中方法是即压即访问法。
stack.push(p.getLeft());
}
}
}
/** 非递归实现中序遍历 */ //思路与上面iterativePreorder 一致。
protected static void iterativeInorder(Node p) {
Stack<Node> stack = new Stack<Node>();
while (p != null) {
while (p != null) {
if (p.getRight() != null)
stack.push(p.getRight());// 当前节点右子入栈
stack.push(p);// 当前节点入栈
p = p.getLeft();
}
p = stack.pop();
while (!stack.empty() && p.getRight() == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty())
p = stack.pop();
else
p = null;
}
}
/*******************************************************************************************/
/*******************************************************************************************/
/** 非递归实现前序遍历2 */
protected static void iterativePreorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {//压入所有的左节点，压入前访问它。左节点压入完后pop访问右节点。像这样算法时思考规律性的东西在哪。不管哪个节点都要压所节点判断右节点。
visit(node);
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {//
node = stack.pop();
node = node.getRight();
}
}
}
/** 非递归实现中序遍历2 */
protected static void iterativeInorder2(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
node = stack.pop();
visit(node); //与iterativePreorder2比较只有这句话的位置不一样，弹出时再访问。
node = node.getRight();
}
}
}
/*******************************************************************************************/
/** 非递归实现后序遍历 */
protected static void iterativePostorder(Node p) {
Node q = p;
Stack<Node> stack = new Stack<Node>();
while (p != null) {
// 左子树入栈
for (; p.getLeft() != null; p = p.getLeft())
stack.push(p);
// 当前节点无右子或右子已经输出
while (p != null && (p.getRight() == null || p.getRight() == q)) {
visit(p);
q = p;// 记录上一个已输出节点
if (stack.empty())
return;
p = stack.pop();
}
// 处理右子
stack.push(p);
p = p.getRight();
}
}
/** 非递归实现后序遍历 双栈法 */
protected static void iterativePostorder2(Node p) {//理解左子树 右子树 根递归性质，把它运用到循环当中去。
Stack<Node> lstack = new Stack<Node>();//左子树栈
Stack<Node> rstack = new Stack<Node>();//右子树栈
Node node = p, right;
do {
while (node != null) {
right = node.getRight();
lstack.push(node);
rstack.push(right);
node = node.getLeft();
}
node = lstack.pop();
right = rstack.pop();
if (right == null) {
visit(node);
} else {
lstack.push(node);
rstack.push(null);
}
node = right;
} while (lstack.size() > 0 || rstack.size() > 0);
}
/** 非递归实现后序遍历 单栈法*/
protected static void iterativePostorder3(Node p) {
Stack<Node> stack = new Stack<Node>();
Node node = p, prev = p;
while (node != null || stack.size() > 0) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
if (stack.size() > 0) {
Node temp = stack.peek().getRight();
if (temp == null || temp == prev) {
node = stack.pop();
visit(node);
prev = node;
node = null;
} else {
node = temp;
}
}
}
}
/** 非递归实现后序遍历4 双栈法*/
protected static void iterativePostorder4(Node p) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> temp = new Stack<Node>();
Node node = p;
while (node != null || stack.size() > 0) {
while (node != null) {
temp.push(node);
stack.push(node);
node = node.getRight();
}
if (stack.size() > 0) {
node = stack.pop();
node = node.getLeft();
}
}
while (temp.size() > 0) {//把插入序列都插入到了temp。
node = temp.pop();
visit(node);
}
}
哈夫曼树
在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)
树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如
JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，
是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点
的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度
为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)
，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径
长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
哈夫曼编码步骤：
一、 对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步，直到集合F中只有一棵二叉树为止。
简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：
虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：
再依次建立哈夫曼树，如下图：
其中各个权值替换对应的字符即为下图：
所以各字符对应的编码为：A->11,B->10,C->00,D->011,E->010
霍夫曼编码是一种前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合
因为它每一个编码都是由根节点到子节点，所以没有任何一个节点的编码是另一个节点编码的前缀，因此称为前缀编码。