1.二叉树：n个具有相同类型的数据元素的有限集合；左子树-根-右子树；有序。
2.二叉树的度：最大的节点度数
3.满二叉树：所有分支节点均存在左子树和右子树，且所有叶子节点均在同一层上
4.完全二叉树：存在的节点与满二叉树的节点编号相同，叶子节点只存在最后一层及倒数第二层
5.非空二叉树的i层最多有 2【i-1】个节点
6.深度为k的二叉树至多有2【k】-1个节点
7.给出完全二叉树的节点数则完全二叉树的深度可以确定
8二叉树的顺序存储结构：
完全二叉树可以存放在n个连续存储单元中（子节点与父节点之间的关系用下标进行表现）
/**Java中
* treemap，treemap类是使用红黑树实现的，红黑树是一个自平衡的二叉搜索树
* 自己实现可以采用顺序表或是链表结构进行树的存储
*/
public class HelloWorld{
public static void main(String[] args){
mytree_array mytree = new mytree_array(4);
mytree.print();
mytree.setNode(1,1,20);
mytree.print();
mytree.setNode(2,1,12);
mytree.setNode(2,2,13);
mytree.print();
mytree.setNode(3,2,14);
mytree.setNode(3,3,15);
mytree.print();
mytree.setNode(4,4,16);
mytree.print();
}
}
class mytree_array{
//如果输入直接是完全二叉树的表现形式就失去意义了，这个地方应该从头构建树
private int[] tree ;
public mytree_array(int deep){
//深度为k的二叉树至多节点数为2的k次方-1
//数组第一个节点不存，方便计算
this.tree = new int[(int)(Math.pow(2,deep))];
}
//按照层数和个数来插入节点
public int setNode(int cengshu,int geshu,int data){
//计算应该放置该节点的坐标
int index = (int)(Math.pow(2,cengshu-1))-1+geshu;
// System.out.print(index);
//判断是否该位置已经有节点
if (this.tree[index]!=0){
System.out.print("already token");
return -1;
}
//判断是否为根节点（根节点无父节点）
if (index == 1){
this.tree[index] = data;
return 1;
}
int father;
//判断是左孩子还是右孩子，根据坐标的奇偶
if (index%2 == 0){
father = index/2;
}else {
father = (index-1)/2;
}
//判断是否存在父节点
if (this.tree[father] == 0){
System.out.print("no father node");
return -1;
}else {
this.tree[index] = data;
return 1;
}
}
public void print(){
System.out.println(Arrays.toString(this.tree));
}
}
普通二叉树->补充为完全二叉树->按完全二叉树的方法进行存储（空间浪费较大）
9.二叉树的链表存储结构：
二叉链表：数据域，左孩子指针域，右孩子指针域
三叉链表：parent域，leftchild，rightchild
//之后的遍历应该是用不到查找parent的，在这里就实现二叉链表，三叉链表就是多加一个parent域
class mytree_Linkedlist{
private Node head;
class Node{
int data;
Node leftchild;
Node rightchild;
public Node(int num){
this.data = num;
this.leftchild = null;
this.rightchild = null;
}
}
public mytree_Linkedlist(){
this.head = null;
}
public void addNode(Node parent,int isleft,Node addnode){ //输入是头结点且当且树为空 if (parent == null){ if (this.head == null){ this.head = addnode; }else { System.out.print("already have root"); } }else { //输入的是一般节点 if ((isleft == 1) && (parent.leftchild == null)){ parent.leftchild = addnode; }else { if (parent.rightchild == null){ parent.rightchild = addnode; }else { System.out.print("already have rightchild"); } } } }//链表打印二叉树则涉及到遍历算法，后续实现}
10.二叉树的遍历：
递归遍历：栈实现，顺序唯一
先序遍历：根->左子树->右子树
中序遍历：左子树->根 ->右子树
后序遍历：右子树 -> 根 ->左子树
层次遍历：从上到下逐层遍历，用队列操作，根入队->访问该节点->若有左孩子则入队->若有右孩子则入队
package java_practice;
import java.util.AbstractQueue;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**Java中
* treemap，treemap类是使用红黑树实现的，红黑树是一个自平衡的二叉搜索树
* 自己实现可以采用顺序表或是链表结构进行树的存储
*/
class Helloworld
{
public static void main(String[] args)
{
mytree_Linkedlist mytree = new mytree_Linkedlist();
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(6);
mytree.addNode(null,1,n1);
mytree.addNode(n1,1,n2);
mytree.addNode(n1,0,n3);
mytree.addNode(n2,0,n4);
mytree.addNode(n3,1,n5);
mytree.addNode(n3,0,n6);
mytree.preOrder(mytree.getRoot());
System.out.print("\n");
mytree.InOrder(mytree.getRoot());
System.out.print("\n");
mytree.PostOrder(mytree.getRoot());
System.out.print("\n");
mytree.LevelOrder();
}
}
class Node{
int data;
Node leftchild;
Node rightchild;
public Node(int num){
this.data = num;
this.leftchild = null;
this.rightchild = null;
}
}
class mytree_Linkedlist{
private Node head;
public mytree_Linkedlist(){
this.head = null;
}
public void addNode(Node parent,int isleft,Node addnode){
//输入是头结点且当且树为空
if (parent == null){
if (this.head == null){
this.head = addnode;
}else {
System.out.print("already have root");
}
}else {
//输入的是一般节点
if ((isleft == 1) && (parent.leftchild == null)){
parent.leftchild = addnode;
}else {
if (parent.rightchild == null){
parent.rightchild = addnode;
}else {
System.out.print("already have rightchild");
}
}
}
}
public Node getRoot(){
return this.head;
}
//链表打印二叉树
//先序
public void preOrder(Node temp){
if (temp != null){
System.out.print(temp.data);
preOrder(temp.leftchild);
preOrder(temp.rightchild);
}
}
public void InOrder(Node temp){
if (temp != null){
InOrder(temp.leftchild);
System.out.print(temp.data);
InOrder(temp.rightchild);
}
}
public void PostOrder(Node temp){
if (temp != null){
PostOrder(temp.leftchild);
PostOrder(temp.rightchild);
System.out.print(temp.data);
}
}
//层次遍历，用队列思想，队列用java提供的LinkedList来做
public void LevelOrder() {
LinkedList<Node> que = new LinkedList<Node>();
que.addLast(this.head);
if(this.head == null){
return;
}
//当队列不空时
while (que.size()!=0){
Node now = que.removeFirst();
System.out.print(now.data);
if (now.leftchild != null){
que.addLast(now.leftchild);
}
if (now.rightchild != null){
que.addLast(now.rightchild);
}
}
}
}
//中序，从左子树返回时遇到节点就访问
public void printbystack_2(){
Stack<Node> st = new Stack<Node>();
Node temp = this.head;
while ((temp!=null) || (!st.empty())){
while (temp!=null){
st.push(temp);
temp = temp.leftchild;
}
if (!st.empty()){
Node e = st.pop();
System.out.print(e.data);
temp = e.rightchild;
}
}
}
//先序，在深入时遇到节点就访问
public void printbystack_1(){
Stack<Node> st = new Stack<Node>();
Node temp = this.head;
while ((temp!=null) || (!st.empty())){
while (temp!=null){
System.out.print(temp.data);
st.push(temp);
temp = temp.leftchild;
}
if (!st.empty()){
Node e = st.pop();
temp = e.rightchild;
}
}
}
//后序遍历需要多用空间进行记录，从右子树返回时遇到节点就访问
public static void printbystack_3(Node t) {
Stack<Node> s = new Stack<Node>();
Stack<Integer> s2 = new Stack<Integer>();
Integer i = new Integer(1);
while (t != null || !s.empty()) {
while (t != null) {
s.push(t);
s2.push(new Integer(0));
t = t.leftchild;
}
while (!s.empty() && s2.peek().equals(i)) {
s2.pop();
System.out.print(s.pop().data);
}
if (!s.empty()) {
s2.pop();
s2.push(new Integer(1));
t = s.peek();
t = t.rightchild;
}
}
}
*二叉树的先序及中序，或是后序及中序可以唯一确定一棵二叉树；
先序+中序按照书上伪代码实现的。居然真的能直接运行。
public void reConstructBinaryTreeCore(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd,Node tree) {
//创建当前节点
tree = new Node(pre[preStart]);
int m = inStart;
//在中序中定位根
while (in[m] != pre[preStart]){
m++;
}
//递归建立左子树
if (m == inStart){
tree.leftchild = null;
}else {
reConstructBinaryTreeCore(pre,in,preStart+1,preStart+m-inStart,inStart,m-1,tree.leftchild);
}
//递归建立右子树
if (m == inEnd){
tree.rightchild = null;
}else {
reConstructBinaryTreeCore(pre,in,preStart+m-inStart+1,preEnd,m+1,inEnd,tree.rightchild);
}
}
int[] a = {1,2,4,3,5,6};
int[] b = {2,4,1,5,3,6};
mytree.reConstructBinaryTreeCore(a, b, 0, 5, 0, 5, mytree.getRoot());
//输入分别是前序，中序，起始角标，个数，起始角标，个数，当前用于存储的节点；
中序加后序的过程是类似的，应该也可以用这个递归的思路进行。重点在于递归时脚标的确定。
public void reConstructBinaryTreeCore(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd,Node tree) {
tree = new Node(pre[preEnd]);
int m = inStart;
//在中序中定位根
while (in[m] != pre[preEnd]){
m++;
}
//递归建立左子树
if (m == inStart){
tree.leftchild = null;
}else {
reConstructBinaryTreeCore(pre,in,preStart,preStart+m-inStart-1,inStart,m-1,tree.leftchild);
}
//递归建立右子树
if (m == inEnd){
tree.rightchild = null;
}else {
reConstructBinaryTreeCore(pre,in,preStart+m-inStart,preEnd-1,m+1,inEnd,tree.rightchild);
}
}
11.二叉树的叶子统计：递归
public int getleefnum(Node temp){
if (temp == null){
return 0;
}
if (temp.leftchild == null & temp.rightchild == null){
return 1;
}
return getleefnum(temp.leftchild)+getleefnum(temp.rightchild);
}
二叉树的深度计算： 递归
public int getdeep(Node temp){
if (temp == null){
return 0;
}
if (temp.leftchild == null & temp.rightchild == null){
return 1;
}
int deep_1 = getdeep(temp.leftchild);
int deep_2 = getdeep(temp.rightchild);
return deep_1>deep_2?1+deep_1:1+deep_2;
}
12.线索二叉树：将二叉树以某种次序遍历使其成为线索二叉树
lchild Ltag data Rtag rchild
前驱节点：（中序为例）直接指向或是以该节点的左孩子为根节点的子树的最右最下节点
后驱节点：（中序为例）直接指向或是以该节点的右孩子为根节点的子树的最左最下节点
线索化过程：检查节点的左右指针域是否为空，若为空则修改为其前驱或后继节点的指针，可以先得到遍历顺序再进行检查和修改
13.二叉排序树：左子树节点的值小于根节点，右子树节点的值大于根节点，且均为二叉排序树
class orderTree extends Tree{
//二叉排序树的中序遍历序列应为有序序列，在这个地方对其进行了判断（手动）
ArrayList<Integer> li = new ArrayList<Integer>();
boolean index = true;
public void checkanswer(){
checkorder(this.getRoot());
System.out.print(this.index);
}
public void checkorder(Node st){
if (st!=null) {
checkorder(st.leftchild);
if (this.li.size() != 0) {
int temp = this.li.get(this.li.size() - 1);
int now = st.data;
System.out.println(temp + ":" + now);
if (temp > now) {
this.index = false;
}
this.li.add(now);
} else {
this.li.add(st.data);
}
checkorder(st.rightchild);
}
}
}
查找：与根比较。若小于则转向左子树，若大于则转向右子树
public Node getbydata(int data){
if (this.index == false){
System.out.print("not a order tree");
return null;
}
if (this.head == null){
System.out.print("null tree");
return null;
}
return compare(this.head,data);
}
public Node compare(Node compre,int data){
if (compre == null || compre.data == data){
return compre;
}
if (compre.data>data){
return compare(compre.leftchild,data);
}
else{
return compare(compre.rightchild,data);
}
}
插入：访问一个节点，若大于它，则查看其是否有右孩子，没有则新节点作为右孩子，若有则继续和其右节点比较。其余思路类似。采用记录最后访问的一个节点的思路较复杂。
public void insert(int data){
Node inse = new Node(data);
if (this.head == null){
this.head = inse;
}
Node temp = this.head;
while (temp!=null){
if (temp.data > data){
if (temp.leftchild == null){
temp.leftchild = inse;
return;
}else {
temp = temp.leftchild;
}
}
else if (temp.data<data){
if (temp.rightchild == null){
temp.rightchild = inse;
return;
}else {
temp = temp.rightchild;
}
}
else {
System.out.print("already exit");
return;
}
}
}
删除：若为叶子节点，直接删除；若单分支，删除，分支挂在父节点上；双分支，按中序遍历保持有序，中序中的前驱代替该节点，删除该前驱。
public void delete(int data){
Node need = getbydata(data);
if (need == null){
System.out.print("no such node");
return;
}
//叶子节点情况
if (need.leftchild == null & need.rightchild == null){
Node father = findfater(data);
if (father!=null){
if (father.leftchild != null && father.leftchild.data == data){
father.leftchild = null;
}else {
father.rightchild = null;
}
}else {
//此节点无父节点
this.head = null;
}
return;
}
//单分支结构
else if (need.leftchild == null){
Node father = findfater(data);
if (father!=null){
if (father.leftchild != null && father.leftchild.data == data){
father.leftchild = need.rightchild;
}else {
father.rightchild = need.rightchild;
}
}else {
//此节点无父节点
this.head = need.rightchild;
}
return;
}
else if (need.rightchild == null){
Node father = findfater(data);
if (father!=null){
if (father.rightchild != null && father.rightchild.data == data){
father.rightchild = need.leftchild;
}else {
father.leftchild = need.leftchild;
}
}else {
//此节点无父节点
this.head = need.leftchild;
}
return;
}
//左右节点均在，在节点的左分支延右指针向下找，直到右指针为空
else {
Node temp = need.leftchild;
while (temp.rightchild!=null){
temp = temp.rightchild;
}
//删除temp节点
Node father_temp = findfater(temp.data);
if (father_temp.rightchild!=null && father_temp.rightchild.data == temp.data){
if (temp.leftchild!=null){
father_temp.rightchild = temp.leftchild;
}else {
father_temp.rightchild = null;
}
}else {
if (temp.leftchild!=null){
father_temp.leftchild = temp.leftchild;
}else {
father_temp.leftchild = null;
}
}
//替换该节点
Node copy = new Node(temp.data);
copy.leftchild = need.leftchild;
copy.rightchild = need.rightchild;
Node father = findfater(data);
if (father!=null){
if (father.rightchild != null && father.rightchild.data == data){
father.rightchild = copy;
}else {
father.leftchild = copy;
}
}else {
//此节点无父节点
this.head = copy;
}
return;
}
}
public Node findfater(int data){
Node temp = this.head;
while (temp!=null){
if (temp.data == data){
return null;
}
else if (temp.data<data){
if (temp.rightchild!=null){
if (temp.rightchild.data == data){
return temp;
}else {
temp = temp.rightchild;
}
}else {
return null;
}
}
else {
if (temp.leftchild!=null){
if (temp.leftchild.data == data){
return temp;
}else {
temp = temp.leftchild;
}
}else {
return null;
}
}
}
return null;
}
14.平衡二叉树：每个节点的左右子树深度之差不超过1的二叉排序树
调整策略见 P101
15.Huffman tree（最优二叉树）：带权路径长度最小
构造算法：选最小的两个，求和再比较再选最小的两个
/**
* for the test
*
* @auther:dan
* @version:1.0
* @date:2017.11.16
*/
package java_practice;
import org.omg.PortableInterceptor.INACTIVE;
import test_package.Tree;
import java.util.*;
/**Java中
* treemap，treemap类是使用红黑树实现的，红黑树是一个自平衡的二叉搜索树
* 自己实现可以采用顺序表或是链表结构进行树的存储
*/
public class HelloWorld {
public static void main(String[] args) {
Node t1 = new Node(7,"a");
Node t2 = new Node(5,"b");
Node t3 = new Node(3,"c");
Node t4 = new Node(4,"d");
List<Node> st = new ArrayList<Node>();
st.add(t1);
st.add(t2);
st.add(t3);
st.add(t4);
huffmanTree tre = new huffmanTree();
Node root = tre.create(st);
System.out.print(tre.toString(root));
List<Integer> hh= tre.getcode("d");
System.out.print(hh);
//
Node output = tre.decode(hh);
System.out.print(output);
}
}
class Node implements Comparable{
String data;
int weight;
Node leftchild;
Node rightchild;
Node parent;
Node(int weight,String data){
this.weight = weight;
this.data = data;
}
@Override
public int compareTo(Object o) {
Node other = (Node)o;
if (this.weight>other.weight){
return -1;
}
else if (this.weight<other.weight){
return 1;
}else{
return 0;
}
}
public String toString(){
return this.data;
// return String.valueOf(this.weight);
}
}
class huffmanTree{
Node head = null;
public Node create(List<Node> nodes){
while (nodes.size()>1){
//排序
Collections.sort(nodes);
//最小的两个组成叶子，生成新节点
Node left = nodes.get(nodes.size()-1);
Node right = nodes.get(nodes.size()-2);
Node partent = new Node(left.weight+right.weight,"----");
partent.leftchild = left;
partent.rightchild = right;
left.parent = partent;
right.parent = partent;
//构造新序列
nodes.remove(left);
nodes.remove(right);
nodes.add(partent);
}
this.head = nodes.get(0);
return nodes.get(0);
}
//按层次打印haffman树
public static List<Node> toString(Node root){
List<Node> nodes = new ArrayList<Node>();
Queue<Node> que = new ArrayDeque<Node>();
if (root!=null){
//插入末尾
que.offer(root);
}
while (que.isEmpty() == false){
//获取但不移除
nodes.add(que.peek());
Node temp = que.poll();
// nodes.add(temp);
if (temp.leftchild!=null){
que.offer(temp.leftchild);
}
if (temp.rightchild!=null){
que.offer(temp.rightchild);
}
}
return nodes;
}
//编码
public List getcode(String data){
List<Node> li = toString(this.head);
Node st = null;
for(Node temp :li){
if (temp.data == data){
st = temp;
}
}
if (st == null){
return null;
}
ArrayList<Integer> re = new ArrayList<Integer>();
Node temp = st.parent;
while (temp!=null){
if (st.parent.leftchild == st){
re.add(1);
}else {
re.add(0);
}
temp = temp.parent;
}
Collections.reverse(re);
return re;
}
//解码
public Node decode(List<Integer> input){
Node temp = this.head;
for (int e:input){
if (e == 1){
temp = temp.leftchild;
}else {
temp = temp.rightchild;
}
}
return temp;
}
}
16.树的存储结构
双亲孩子表示法：数组+链表
兄弟表示法：二叉链表 firstchild ,nextsibiling 记录第一个孩子节点及下一个兄弟节点
17.树转化为二叉树：对一棵树可以找到一棵二叉树与之对应，二叉树转换回来->树/森林
兄弟节点相连->保留与最左孩子的连线，其余删除（兄弟表示法）
18.树的遍历：先根遍历，后根遍历，层次遍历
19.B树：文件系统的重要管理方式，多路平衡查找树
介绍：https://www.cnblogs.com/George1994/p/7008732.html
B+树：
内部节点中，关键字的个数与其子树的个数相同，不像B树种，子树的个数总比关键字个数多1个 所有指向文件的关键字及其指针都在叶子节点中，不像B树，有的指向文件的关键字是在内部节点中。换句话说，B+树中，内部节点仅仅起到索引的作用， 在搜索过程中，如果查询和内部节点的关键字一致，那么搜索过程不停止，而是继续向下搜索这个分支
优点：
B+树的磁盘读写代价更低 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。 B+树的查询效率更加稳定 由于内部结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。 B+树更有利于对数据库的扫描 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描，所以对于数据库中频繁使用的range query，B+树有着更高的性能。
20.堆：ki<=k2i,ki<=k2i+1，完全二叉树中所有非终端节点均不大于或小于左右孩子的值。大顶堆则根是最大的一个节点。
堆排序算法：输出堆顶，剩余元素再次形成一个堆。nlog2[n]。
小顶堆筛选：去掉堆顶，把最后一个元素放在堆顶，进行交换。
堆建立：从最后一个非叶子节点开始到根重复筛选过程。
/**
* for the test
*
* @auther:dan
* @version:1.0
* @date:2017.11.16
*/
package java_practice;
import org.omg.PortableInterceptor.INACTIVE;
import test_package.Tree;
import java.util.*;
/**Java中
* treemap，treemap类是使用红黑树实现的，红黑树是一个自平衡的二叉搜索树
* 自己实现可以采用顺序表或是链表结构进行树的存储
*/
public class HelloWorld {
public static void main(String[] args) {
//顺序表存储的树
int[] data = { 15, 13, 1, 5, 20, 12, 8, 9, 11 };
// 测试建堆
heap he = new heap();
// he.creat(data, data.length - 1);
// System.out.println(Arrays.toString(data));
he.heapsort(data);
System.out.print(Arrays.toString(data));
}
}
class heap{
//i是要替换的位置，n是数组最后一位，只是一个节点的调整过程
public static void fixDown(int[] data, int i, int n) {
int num = data[i];
//左儿子，因为没有头结点
int son = i * 2 + 1;
while (son <= n) {
//如果有右儿子且右儿子更小，切换到右儿子
if (son + 1 <= n && data[son + 1] < data[son])
son++;
//如果当前节点小于儿子，结束
if (num < data[son])
break;
//和儿子交换
data[i] = data[son];
i = son;
son = i * 2 + 1;
}
data[i] = num;
}
public static void creat(int[] data, int n) {
//从一半的元素开始调整，一直调整到根
for (int i = (n - 1) / 2; i >= 0; i--)
fixDown(data, i, n);
}
//第n个数向上调整的过程
public static void fixUp(int[] data, int n) {
int num = data[n];
int father = (n - 1) / 2;
// data[father] > num是进入循环的基本条件,father减到0就不会减少了
// 当n等于0时，father=0；进入死循环，所以当n==0时，需要跳出循环
while (data[father] > num && n != 0) {
data[n] = data[father];
n = father;
father = (n - 1) / 2;
}
data[n] = num;
}
// 删除,n表示堆的最后一个元素的索引
public static void delete(int[] data, int n) {
data[0] = data[n];
data[n] = -1;
fixDown(data, 0, n - 1);
}
// 增加,i表示要增加的数字，n表示增加位置的索引，是堆的最后一个元素
public static void insert(int[] data, int num, int n) {
data[n] = num;
fixUp(data, n);
}
//堆排序
public void heapsort(int[] data){
creat(data,data.length-1);
for (int i = data.length-1;i>=1;i--){
int temp = data[0];
data[0] = data[i];
data[i] = temp;
fixDown(data,0,i-1);
}
}
}