树和二叉树

树与图的区别：

1.树在本质上其实就是不包含回路的连通无向图；

2.关于树的一些特点：
（1）.任意两个结点有且只有唯一的一条路径连接；
（2）.n个结点，那么刚好n-1条边；
（3）.在一棵树中加一条边将会构成一个回路；
3.根：一棵树有且只有一个根结点，比如上图中的数值为1的点就是根结点；
子结点：上图中除了1其余都是子结点，没有父结点的结点是根结点（祖先）；
叶结点：没有子结点的结点就是叶结点，如上图的3.4.5
其余既不是根结点又不是叶结点的叫做内部结点，如上图的2；
最后每个结点是有深度的，比如3号节点的深度（从根结点到这一层的层数）是2；

二叉树

1.定义：每个结点最多有两个儿子，分别是左儿子、右儿子；递归定义：二叉树要么为空，要么由根结点、左子树、右子树组成；二叉树又分为满二叉树和完全二叉树；
2.满二叉树：每个内部结点都有两个儿子，也就是所有的叶结点都有相同的深度；

3.满二叉树深度与结点的关系：假如深度为n，那么结点2^{n-1;第n层上，结点为2}(n-1);
4.完全二叉树：除了最右边位置上有一个或者几个叶结点缺少外，其余都是丰满的

（1）.对于完全二叉树：我们可以用一个一维数组来存储它，从根结点开始

（2）.如果给父结点编号为k，那么他的左儿子就是2k,右儿子2k+1；
（3）.如果一棵二叉树有N个结点，那么这个完全二叉树的高度为log2N（2）为底；
完全二叉树的最典型应用就是——堆；

堆排序

import java.util.Scanner;

public class D堆排序 {
	static Scanner in=new Scanner(System.in);
	static int n;static int num=in.nextInt();
	static int []h=new int [num+1];
	public static void swap(int x,int y)
	{
		int t;
		t=h[x];
		h[x]=h[y];
		h[y]=t;
		return;
	}
	public static void siftdown(int i)
	{
		int t,flag=0;
		while(i*2<=n&&flag==0)
		{
			if(h[i]>h[i*2])
			{
				t=i*2;
			}
			else
				t=i;
			if(i*2+1<=n)
			{
				if(h[t]>h[i*2+1])
						t=i*2+1;
			}
			if(t!=i)
			{
				swap(t,i);
				//i=t;
			}
			else
				flag=1;
		}
		return;
	}
	public static void creat()
	{
		int i;
		for(i=n/2;i>=1;i--)
		{
			//从最后一个非叶结点到第一个结点依次进行向下调整
			siftdown(i);
		}
		return;
	}
	public static int deletemax() {
		int t;
		t=h[1];
		h[1]=h[n];
		n--;
		siftdown(1);
		return t;
		
		
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int i=0;
		for(i=1;i<=num;i++)
		{
			h[i]=in.nextInt();
		}
		n=num;
		creat();//建堆
		for(i=1;i<=num;i++)
		{
			System.out.print(deletemax()+" ");
		}
	}

}

1.创建堆（最小堆）

public static void creat()
	{
		int i;
		for(i=n/2;i>=1;i--)
		{
			//从最后一个非叶结点到第一个结点依次进行向下调整
			siftdown(i);
		}
		return;
	}

为什么是从n/2开始呢？因为所有的叶结点都没有儿子，自然而然叶结点都符合最小堆的特点，所以这里就不再需要考虑叶结点，直接从最后一个非叶结点开始起进行调整，一直到第一个结点。

2.在创建堆的过程中，对所有的子树进行调整，当所有的子树满足条件时，整棵树就一定满足了条件。

3.采用删除最大元素的方式来输出

public static int deletemax() {
		int t;
		t=h[1];
		h[1]=h[n];
		n--;
		siftdown(1);
		return t;	
	}

将堆顶的元素返回输出，然后将最大的元素放到堆顶再进行调整，n--，直到为空。