Tree
1.二叉树的性质
二叉树第i层（i>=1）上最多有2^(k-1)个元素。
高度为k的儿茶素最多有2^k-1 个元素
2.二叉树的存储
分为顺序存储结构和链式存储
ps： 从1开始算的是 这里面。
二叉树的链接存储结构
3.二叉树的遍历
重点掌握。
- 前序遍历（前中后是对根结点来说的）
- 中序遍历
- 后序遍历
- 广度遍历(层次遍历，队列)
- s形遍历（第一列从左到右，第二列从右到左）
前中后遍历：
根据根结点的位置来说的。
层次遍历：
在进行层次遍历的时候，对一层节点访问完后，在按照他们的访问次序对各个节点的左右孩子做顺序便利。就完成了对下一层从左到右的访问。在进行层次遍历时，需设置一个队列。首先将根指针入队，然后从队列里面弹出来一个元素，每取出一个元素，执行两个操作，访问改元素所值得节点。如果左右节点不为空，加入队列。此过程循环执行，直到队列为空。表示层次遍历结束。
s遍历
层次遍历。第一层从左到右，第二层从右到左，可以通过两个queue实现。
package tree;
import java.util.LinkedList;
import java.util.Queue;
public class Treesearch {
static class Node{
String value;
Node leftNode;
Node rightNode;
public Node(String value,Node left,Node right){
this.value=value;
this.leftNode=left;
this.rightNode=right;
}
}
void doSth(Node root){
System.out.print(root.value+" ");
}
void preOrder(Node root){
if(root==null) return ;
doSth(root);
preOrder(root.leftNode);
preOrder(root.rightNode);
}
void inOrder(Node root){
if(root==null) return ;
inOrder(root.leftNode);
doSth(root);
inOrder(root.rightNode);
}
void postOrder(Node root){
if(root==null) return ;
postOrder(root.leftNode);
postOrder(root.rightNode);
doSth(root);
}
void breadthOrder(Node root){
Queue<Node> queue= new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
Node node=queue.poll();
doSth(node);
if(node.leftNode!=null)
queue.add(node.leftNode);
if(node.rightNode!=null)
queue.add(node.rightNode);
}
}
void pt(LinkedList<Node> queue,int t){
if(t%2==0){
for(int i=0;i<queue.size();i++){
System.out.print(queue.get(i).value+" ");
}
}else{
for(int i=queue.size()-1;i>=0;i--){
System.out.print(queue.get(i).value+" ");
}
}
}
void s_order(Node root){
LinkedList<Node> queue1= new LinkedList<>();
LinkedList<Node> queue2= new LinkedList<>();
queue1.add(root);
int i=0;
while(queue1.size()!=0){
pt(queue1, i);
i++;
while(!queue1.isEmpty()){
Node node=queue1.poll();
//doSth(node);//如果s打印。那么控制一下参数就好。
if(node.leftNode!=null)
queue2.add(node.leftNode);
if(node.rightNode!=null)
queue2.add(node.rightNode);
}
LinkedList<Node> tmp=queue1;
queue1=queue2;
queue2=tmp;
}
}
Node create(){
Node d=new Node("d", null, null);
Node e=new Node("e", null, null);
Node g=new Node("g", null, null);
Node b=new Node("b", d, e);
Node c=new Node("c", null, g);
Node a=new Node("a", b, c);
return a;
}
public static void main(String[] args) {
Treesearch s= new Treesearch();
Node root=s.create();
s.preOrder(root);
System.out.println();
s.inOrder(root);
System.out.println();
s.postOrder(root);
System.out.println();
s.breadthOrder(root);
System.out.println();
s.s_order(root);
}
}
4.线索二叉树
通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。
因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。
记ptr指向二叉链表中的一个结点，以下是建立线索的规则：
（1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱；
（2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继；
显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。
其中：
（1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱；
（2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继；
（3）因此对于上图的二叉链表图可以修改为下图的养子。
package tree;
public class ThreadTree {
static class TreeNode{
int value;
int ltag;
int rtag;
TreeNode left;
TreeNode right;
}
private TreeNode pre = null;
//1.建立一颗中序线索二叉树
void inThread(TreeNode root){
if(root ==null) return ;
inThread(root.left);
if(root.left==null){
root.ltag=1;
root.left=pre;
}
if(pre!=null && pre.right==null){
pre.right=root;
pre.rtag=1;
}
pre=root;
inThread(root.right);
}
//2.查找任意节点的前驱节点
TreeNode getPreNode(TreeNode node ){
if(node.ltag==1){
return node.left;
}else{
node=node.left;
while(node.rtag!=1){
node=node.right;
}
return node;
}
}
//3.查找任意节点的后续节点
TreeNode getLastNode(TreeNode node){
if(node.rtag==1){
return node.right;
}else{
node=node.right;
while(node.ltag!=1){
node=node.left;
}
return node;
}
}
//4.查找值为x的节点
TreeNode findNode(int x,TreeNode root){
TreeNode p=root;
if(p.value==x){
return p;
}
if(p==pre){
return null;
}
findNode(x, getLastNode(p));
return null;
}
//5. insertnode
void insert(int x){
}
}
5.树和二叉树的转换
本节主要介绍树和二叉树的转换，森林和二叉树的转换，树的遍历和存储。
树和二叉树的转换
森林转二叉树
6.哈夫曼树
