java树数据结构(二叉树)
树的基本概念
概念定义:
注：高度与深度的概念辨析
1. 对于节点来说：深度是从根节点往下，高度是从叶子节点向上。同一个节点的深度与高度有可能不同(根节点与叶子节点初始值为0为1都有定义，不同书籍的定义不同)
2. 对于整棵树来说:最深的叶结点的深度就是树的深度；树根的高度就是树的高度。这样树的高度和深度是相等的。
节点之间的关系：
对于任何非空二叉树, t, 如果 n0 是叶节点的数量, n2 是度数2的节点数, 则 n0=n2+1即：n0+n1+n2=2*n2+n1+1(根节点)
同样的队医三叉树来说，n0=2*n3+n2+1 即：n0+n1+n2+n2=3*m3+2*n2+n1+1(根节点)
以此类推：对于N叉树，n0=(n-1)*Xn+(n-2)*X(n-1)+...+X2+1
二叉树的特殊种类
满二叉树：除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.
给定高度k的满二叉树，具有2^(k+1)-1个节点
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
二叉树的实现
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Tree<Type> {
private TreeNode<Type> root;
public Tree() {
this.root=null;
}
public Tree(TreeNode<Type> node) {
this.root=node;
}
public boolean isEmpty() {
return this.root==null;
}
public Type getRoot() {
if(root==null) {
throw new NullPointerException("树为空");
}else {
return this.root.data;
}
}
public TreeNode<Type> leftChild(TreeNode<Type> node){
if(node==null) {
throw new NullPointerException("此节点不存在");
}else {
return node.lchild;
}
}
public TreeNode<Type> rightChild(TreeNode<Type> node){
if(node==null) {
throw new NullPointerException("此节点不存在");
}else {
return node.rchild;
}
}
public TreeNode<Type> getParnts(TreeNode<Type> node){
if(node==null) {
throw new NullPointerException("此节点不存在");
}else {
return parent(root,node);
}
}
public TreeNode<Type> parent(TreeNode<Type> node,TreeNode<Type> current){
if(node==null) {
return null;
}else {
if(node.lchild==current || node.rchild==current) {
return node;
}else {
TreeNode<Type> n=parent(node.lchild,current);
if(n!=null) {
return n;
}else {
return parent(node.rchild,current);
}
}
}
}
public TreeNode<Type> find(Type data){
return findNotNull(root,data);
}
public TreeNode<Type> findNotNull(TreeNode<Type> node,Type data){
if(node==null) {
return null;
}else {
if(data!=null) {
if(data.equals(node.data)) {
return node;
}else {
TreeNode<Type> n=findNotNull(node.lchild,data);
if(n!=null) {
return n;
}else {
return findNotNull(node.rchild,data);
}
}
}else {
if(node.data==null) {
return node;
}else {
TreeNode<Type> n=findNotNull(node.lchild,data);
if(n!=null) {
return n;
}else {
return findNotNull(node.rchild,data);
}
}
}
}
}
public int size() {//试一下第二种方法
return get_s(root);
}
public int get_s(TreeNode<Type> node) {
if(node==null) {
return 0;
}else {
return get_s(node.lchild)+get_s(node.rchild)+1;
}
}
public int height() {
return get_h(root);
}
public int get_h(TreeNode<Type> node) {
if(node==null) {
return -1;
}else {
return Math.max(get_h(node.lchild)+1,get_h(node.rchild)+1);
}
}
//前序递归遍历
public void pre_print() {
pre_print(root);
System.out.println();
}
public void pre_print(TreeNode<Type> node) {
if(node!=null) {
System.out.print(node.data+"-->");
pre_print(node.lchild);
pre_print(node.rchild);
}
}
//前序非递归遍历
public void preN_print() {
Stack<TreeNode<Type>> s=new Stack<TreeNode<Type>>();
TreeNode<Type> node=root;
while(node!=null || !s.isEmpty()) {
while(node!=null) {
System.out.print(node.data+"-->");
s.push(node);
node=node.lchild;
}
if(!s.isEmpty()) {
node=s.peek();
s.pop();
node=node.rchild;
}
}
System.out.println();
}
//中序遍历
//终须递归遍历
public void ind_print() {
ind_print(root);
System.out.println();
}
public void ind_print(TreeNode<Type> node) {
if(node!=null) {
ind_print(node.lchild);
System.out.print(node.data+"-->");
ind_print(node.rchild);
}
}
//中序非递归遍历
public void indN_print() {
Stack<TreeNode<Type>> s=new Stack<>();
TreeNode<Type> node=this.root;
while(node!=null || !s.isEmpty()) {
while(node!=null) {
s.push(node);
node=node.lchild;
}
if(!s.isEmpty()) {
node=s.peek();
s.pop();
System.out.print(node.data+"-->");
node=node.rchild;
}
}
System.out.println();
}
//后序遍历
//递归后序遍历
public void post_print() {
post_print(root);
System.out.println();
}
public void post_print(TreeNode<Type> node) {
if(node!=null) {
post_print(node.lchild);
post_print(node.rchild);
System.out.print(node.data+"-->");
}
}
//非递归后序遍历
public void postN_print() { //https://www.cnblogs.com/gaopeng527/p/5451176.html
Stack<TreeNode<Type>> s1=new Stack<>();
Stack<Integer> s2=new Stack<>();
TreeNode<Type> node=this.root;
while(node!=null || !s1.isEmpty()) {
while(node!=null) {
s1.push(node);
s2.push(0);
node=node.lchild;
}
while(!s2.isEmpty()&&s2.peek()==1) {
s2.pop();
System.out.print(s1.pop().data+"-->");
}
if(!s1.isEmpty()) {
s2.pop();
s2.push(1);
node=s1.peek();
node=node.rchild;
}
}
System.out.println();
}
//广度优先遍历
public void lev_print() {
Queue<TreeNode<Type>> q = new LinkedList<TreeNode<Type>>();
q.add(root);
while(!q.isEmpty()) {
TreeNode<Type> node=q.peek();
System.out.print(node.data+"-->");
q.remove();
if(node.lchild!=null) {
q.add(node.lchild);
}
if(node.rchild!=null) {
q.add(node.rchild);
}
}
System.out.println();
}
}
class TreeNode<Type>{
public Type data;
public TreeNode<Type> lchild;
public TreeNode<Type> rchild;
public TreeNode() {
this.data=null;
this.lchild=this.rchild=null;
}
public TreeNode(Type data,TreeNode<Type> lchild,TreeNode<Type> rchild){
this.data=data;
this.lchild=lchild;
this.rchild=rchild;
}
public TreeNode(Type data) {
this.data=data;
}
}
class Test{
public static void main(String args[]) {
TreeNode<Character> b1 = new TreeNode<>('a');
TreeNode<Character> b2 = new TreeNode<>('b');
TreeNode<Character> b3 = new TreeNode<>('c');
TreeNode<Character> b4 = new TreeNode<>('d');
TreeNode<Character> b5 = new TreeNode<>('e');
TreeNode<Character> b6 = new TreeNode<>('f');
TreeNode<Character> b7 = new TreeNode<>('g');
TreeNode<Character> b8 = new TreeNode<>('h');
b1.lchild = b2;
b1.rchild = b3;
b2.lchild = b4;
b2.rchild = b5;
b5.rchild = b6;
b3.rchild = b7;
b7.lchild = b8;
// a
// / \
// b c
// / \ \
// d e g
// \ /
// f h
Tree<Character> tree=new Tree<>(b1);
System.out.println("树为空？"+tree.isEmpty());
System.out.println("树共有"+tree.size()+"个节点");
System.out.println("树的高度为"+tree.height());
System.out.println("输的根节点元素为："+tree.getRoot());
System.out.println("元素"+b5.data+"的父节点为："+tree.getParnts(b5).data);
System.out.println("元素"+b5+"的内容为："+tree.find(b5.data).data);
System.out.println("前序遍历：");
tree.pre_print();
tree.preN_print();
System.out.println("中序遍历：");
tree.ind_print();
tree.indN_print();
System.out.println("后序遍历：");
tree.post_print();
tree.postN_print();
System.out.println("广度优先遍历：");
tree.lev_print();
}
}线索树(Threaded Tree)
在一棵只有n个结点的二叉树中，假设有n个结点，那么就有2n个指针域，因为二叉树只用到了其中的n-1个结点，所以只要利用剩下的n+1个节点，我们就能把中需遍历时所得到的中序二叉树保存下来，以便下次访问。
中序二叉树的指针域有两种类型：一是用于链接二叉树本身；二是用于链接中序遍历序列。这类型的指针，左指指向中序遍历时节点顺序的前驱，右指针指向中序遍历时的后继。为了区别这两种指针域类型，我们在树的结点中要加上两个标志lchild和rchild，分别标志左右指针域的类型。 其数据结构如下：
其中:
LTag = 0 lchild域指示节点的左孩子；LTag=1 lchild域指示节点的前驱。
RTag = 0 rchild域指示节点的左孩子；RTag=1 rchild域指示节点的前驱。
1. 前序线索树(依靠先序遍历来寻找前驱节点和后继节点)：
2.中序线索树(依靠中序遍历来寻找前驱节点和后继节点)
3.后序线索树(依靠后序遍历确定前驱节点和后继结点)
哈夫曼树
定义：
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近，哈夫曼树一定为二叉树
概念：
1. 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径
2. 结点的路径之和:到根节点的路径之和。为各个节点的路孔之和相加，并不是树的路径之和。
3. 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。
4. 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。
5. 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积，WPL= wi ´ Li
哈夫曼树的应用：
树与森林的转化
1. 先序遍历树林正好等同于按先序遍历对应的二叉树；后序遍历森林正好等同于中序对应的二叉树。
2. 在进行树与二叉树的转化的时候。二叉树的左节点为原树的第一个叶子节点。二叉树的右子节点为原树的第一个兄弟节点。在进行森林的准话的时候，多个度一次加到二叉树的右子节点中。
3. 转化实例
若有不足，请多多指教。
下一篇： 如何评价DCloud？