5，树
1，树的概念
树(tree)是n(n>=0)个结点的有限集合T,若n=0时称为空树，否则：
(1)有且只有一个特殊的称为树的根(root)结点；
(2)若n>1，其余的结点被分为m(m>0)个互不相欠的子集T1,T2,T3,...,Tm,其中每个子集本身又是一棵树，称其为根的子树(subtree)。
下面介绍与树相关的基本术语。
结点：树的元素，含有数据域和多重指针域。
结点的度：某一结点所拥有的子树个数。
树的度：在一棵树中最大的结点度数是树的度。
叶子：树的端结点，其度为零。
孩子：结点子树的根。
双亲：孩子结点的前驱结点。
结点层次：从根算起结点在层中的位置，root层次为1。
深度：树中结点所具有的最大层次。
有序树：树中结点同层间从左至右有次序地排序，不能互换。
森林(forest)：是m（m>=0）棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。
2，二叉树的概念
二叉树：
（1）每个结点最多只有两颗子树，即二叉树结点的度只能为0，1，2.
（2）子树有左右顺序之分，不能颠倒。
根据二叉树的定义，可以知道二叉树共有5种基本的形态。
3，满二叉树
在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树称为满二叉树。
或者深度为h且含有2^h-1个结点的二叉树为满二叉树。
4，完全二叉树
对满二叉树进行编号，编号从1开始，从上到下，从左到右进行，如上图所示。具有n个结点，深度为k的二叉树，当且仅当其所有的结点对应于深度为k的满二叉树中编号由1至n的那些结点时，称为完全二叉树。显然，满二叉树也是完全二叉树。
上述图中，编号6的F结点虚线的位置，此时整棵树就不是完全二叉树。如果把 6的F 结点去掉，或者，6的F 结点 为 C父节点的左子树，也为完全二叉树。
5，平衡二叉树(AVL树)
一个平衡二叉树是空树，或者是具有下列性质的二叉树，即它任一个结点的左右子树都是平衡的，且左右子树的深度之差的绝对值小于等于1。
6，二叉树的性质
（1）二叉树的第i层上至多有2i-1个结点。
（2）深度为h的二叉树中至多有2h-1个结点。
（3）任意一棵二叉树有关系 N0=N2+1成立。N0是叶子数，N2是度为2的结点数。
（4）n个结点的完全二叉树深度为[log(2)n]+1。
（5）若对一棵有n个结点的完全二叉树（深度为[log(2)n+1]）的结点按层（从第1层到第[log(2)n+1层]）序自左至右进行编号，则对于编号为i(1<=i<=n)的结点，满足以下3点。
1，若i=1，则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是i/2。
2，如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。
3，如果2i+1>n，则结点i无右孩子；否则，其右孩子结点编号是2i+1。
7，二叉树的存储结构
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。
（1）顺序存储结构
二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号。缺点是有可能对存储空间造成极大地浪费，在最坏地情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
（2）链式存储结构
由于顺序存储的空间利用率较低，因此二叉树一般都采用链式存储结构，用链表结点来存储二叉树中的每个结点。
二叉链表的结点：
typedef struct BTNode{
ElemType data;
Struct BTNode *Lchild,*Rchild;
} BTNode;
三叉链表的结点：
typedef struct BTNode{
ElemType data;
Struct BTNode *Lchild,*Rchild;
}BTNode;
java构建结点
public class Node{
private int data;
private Node leftNode;
private Node rightNode;
public Node(int data,Node leftNode,Node rightNode){
this.data=data;
this.leftNode=leftNode;
this.rightNode=rightNode;
}
public int getData() {
return data;
}
public void setData(intdata) {
this.data=data;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode=leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode=rightNode;
}
}
递归代码
public class BinaryTree{
/**
* 二叉树的先序中序后序排序
*/
public Node init() {//注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
Node H=new Node(4,null,null);
Node G=new Node(2,null,null);
Node F=new Node(7,null,J);
Node E=new Node(5,H,null);
Node D=new Node(1,null,G);
Node B=new Node(3,D,E);
Node A=new Node(6,B,C);
return A;//返回根节点
}
public void printNode(Node node){
System.out.print(node.getData());
}
//先序遍历
//中序遍历
//后序遍历
}
8，遍历二叉树
遍历（traversal）时指沿着某条搜索路线，依次对树种每个结点均做依次且仅做依次访问
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左，右子树这三个基本部分组称。因此，在任一个给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身（N）；
（2）遍历该结点的左子树（L）；
（3）遍历该结点的右子树（R）；
以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。
前三种次序于后三种次序对称，故只讨论先左后右的前三种次序，分别命名如下
NLR：前序遍历（preorder traversal，又称先序遍历）--- 访问结点的操作发生在遍历其左右子树之前。
LNR：中序遍历（lnorder traversal）--- 访问结点的操作发生在遍历其左右子树之中（间）。
LRN：后序遍历（postorder traversal）--- 访问结点的操作发生在遍历其左右子树之后。
对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者i当以和使用堆栈来实现的。
（1）先序遍历二叉树
1，递归算法
算法的递归定义是：
若二叉树为空，则遍历结束；否则
（1）访问根节点；
（2）先序遍历左子树（递归调用本算法）；
（3）先序遍历右子树（递归调用本算法）。
先序遍历的递归算法：
public void theFirstTraversal(Node root) {//先序遍历
printNode(root);//先访问父结点
if(root.getLeftNode()!=null) {//使用递归进行遍历左孩子
theFirstTraversal(root.getLeftNode());
}
if(root.getRightNode()!=null) {//递归遍历右孩子
theFirstTraversal(root.getRightNode());
}
}
2，非递归算法(不容易理解，尤其是后序)
设T是指向二叉树根结点的指针变量，非递归算法如下。
若二叉树为空，则返回；否则，另p=T。
（1）访问p所指向的结点；
（2）q=p->Rchild，若q不为空，则q进栈。
（3）p=p->Lchild，若p不为空，转（1），否则转(4);
（4）退栈到p；转（1），直到栈空为止；
public void theFirstTraversal_Stack(Node root) { //先序遍历
Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || stack.size() > 0) { //将所有左孩子压栈
if (node != null) { //压栈之前先访问
printNode(node);
stack.push(node);
node = node.getLeftNode();
} else {
node = stack.pop();
node = node.getRightNode();
}
}
}
（2）中序遍历二叉树
若二叉树为空，则遍历结束；否则
（1）中序遍历左子树（递归调用本算法）；
（2）访问根结点；
（3）中序遍历右子树（递归调用本算法）。
中序的递归算法：
public void theInOrderTraversal(Node root) { //中序遍历
if (root.getLeftNode() != null) {
theInOrderTraversal(root.getLeftNode());
}
printNode(root); //访问父结点
if (root.getRightNode() != null) {
theInOrderTraversal(root.getRightNode());
}
}
中序的非递归算法：
public void theInOrderTraversal_Stack(Node root) { //中序遍历
Stack<Node> stack = new Stack<Node>();
Node node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node); //直接压栈
node = node.getLeftNode();
} else {
node = stack.pop(); //出栈并访问
printNode(node);
node = node.getRightNode();
}
}
}
（3）后序遍历二叉树
若二叉树为空，则遍历结束；否则
（1）中序遍历左子树（递归调用本算法）；
（3）中序遍历右子树（递归调用本算法）；
（2）访问根结点。
后序遍历的递归算法：
public void thePostOrderTraversal(Node root) { //后序遍历
if (root.getLeftNode() != null) {
thePostOrderTraversal(root.getLeftNode());
}
if(root.getRightNode() != null) {
thePostOrderTraversal(root.getRightNode());
}
printNode(root);
}
后序遍历的非递归算法
public void thePostOrderTraversal_Stack(Node root) { //后序遍历
Stack<Node> stack = new Stack<Node>();
Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后序遍历的结果
Node node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
output.push(node);
stack.push(node);
node = node.getRightNode();
} else {
node = stack.pop();
node = node.getLeftNode();
}
}
System.out.println(output.size());
while (output.size() > 0) {
printNode(output.pop());
}
}
遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O（n）。
分别进行三种遍历的结果为：
先序遍历上图所示的二叉树是，得到的先序序列为：A B D C E F 。
中序遍历上图所示的二叉树是，得到的中序序列为：D B A E C F 。
后序遍历上图所示的二叉树是，得到的后序序列为：D B E F C A 。
（4）层次遍历
如图所示，二叉树的层次遍历，即按照箭头所指方向，按照1，2，3，4的层次顺序，对二叉树中的各个结点进行访问。
要进行层次遍历，需要借助一个队列。先将二叉树根结点入队，然后出队，访问出队结点，若它有左子树，则将左子树根结点入队；若它有右子树，则将右子树根结点入队。然后出队，访问出队结点。。。。。。如此反复，直至队列为空。
import java.util.LinkedList;
public class tree {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data){
this.value=data;
}
}
public void levelIterator(Node root)
{
if(root == null)
{
return ;
}
LinkedList queue = new LinkedList();
Node current = null;
queue.offer(root);//将根节点入队
while(!queue.isEmpty())
{
current = queue.poll();//出队队头元素并访问
System.out.print(current.value +"-->");
if(current.left != null)//如果当前节点的左节点不为空入队
{
queue.offer(current.left);
}
if(current.right != null)//如果当前节点的右节点不为空，把右节点入队
{
queue.offer(current.right);
}
}
}
}
9，线索二叉树
（1）线索二叉树的基本概念
遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。
传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。前面提到，在含n个结点的二叉树中，有n+1个空指针。这是因为每个叶结点有2个空指针，每个度为1的结点有1个空指针，空指针总数为2n0+n1，又n0=n2+1，所以空指针总数为n0+n1+n2+1=n+1。由此设想能否利用这些空指针来存放指向其前驱或后继的指针？这样就可以像遍历单链表那样方便地遍历二叉树。引入线索二叉树正是为了加快查找结点前驱和后
继的速度。
规定:若无左子树，令1chi1d指向其前驱结点;若无右子树，令rchi1d指向其后继结点
如图5.10所示，还需增加两个标志域标识指针域是指向左（右）孩子还是指向前驱（后继）。
其中，标志域的含义如下：
线索二叉树的存储结构描述如下：
class Node {
String data; //数据域
Node left; //左指针域
Node right; //右指针域
byte leftType; //左指针域类型 0：指向子节点、1：前驱或后继线索
byte rightType; //右指针域类型 0：指向子节点、1：前驱或后继线索
}
以这种结点结构构成的二叉链表作为二叉树的存储结构，称为线索链表，其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。
（2）中序线索二叉树的构造
二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息，只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。
以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检査p的左指针是否为空，若为空就将它指向pre;检查pre的右指针是否为空，若为空就将它指向p，如图511所示
为了方便，可以在二叉树的线索链表上也添加一个头结点，令其Lchild域的指针指向二叉树的根结点，其Rchild域的指针指向中序遍历时访问的最后一个结点;令二叉树中序序列中的第一个结点的Lchild域指针和最后一个结点的Rchi1d域指针均指向头结点。这好比为二又树建立了一个双向线索链表，方便从前往后或从后往前对线索二叉树进行遍历，如图5.12所示。
（3）中序线索二叉树的遍历
/**
* @Title: 线索二叉树相关操作
*/
public class ThreadBinaryTree {
private Node preNode; //线索化时记录前一个节点
//节点存储结构
static class Node {
String data; //数据域
Node left; //左指针域
Node right; //右指针域
boolean isLeftThread = false; //左指针域类型 false：指向子节点、true：前驱或后继线索
boolean isRightThread = false; //右指针域类型 false：指向子节点、true：前驱或后继线索
Node(String data) {
this.data = data;
}
}
/**
* 通过数组构造一个二叉树（完全二叉树）
* @param array
* @param index
* @return
*/
static Node createBinaryTree(String[] array, int index) {
Node node = null;
if(index < array.length) {
node = new Node(array[index]);
node.left = createBinaryTree(array, index * 2 + 1);
node.right = createBinaryTree(array, index * 2 + 2);
}
return node;
}
/**
* 中序线索化二叉树
* @param node 节点
*/
void inThreadOrder(Node node) {
if(node == null) {
return;
}
//处理左子树
inThreadOrder(node.left);
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
//处理右子树
inThreadOrder(node.right);
}
/**
* 中序遍历线索二叉树，按照后继方式遍历（思路：找到最左子节点开始）
* @param node
*/
void inThreadList(Node node) {
//1、找中序遍历方式开始的节点
while(node != null && !node.isLeftThread) {
node = node.left;
}
while(node != null) {
System.out.print(node.data + ", ");
//如果右指针是线索
if(node.isRightThread) {
node = node.right;
} else { //如果右指针不是线索，找到右子树开始的节点
node = node.right;
while(node != null && !node.isLeftThread) {
node = node.left;
}
}
}
}
/**
* 中序遍历线索二叉树，按照前驱方式遍历（思路：找到最右子节点开始倒序遍历）
* @param node
*/
void inPreThreadList(Node node) {
//1、找最后一个节点
while(node.right != null && !node.isRightThread) {
node = node.right;
}
while(node != null) {
System.out.print(node.data + ", ");
//如果左指针是线索
if(node.isLeftThread) {
node = node.left;
} else { //如果左指针不是线索，找到左子树开始的节点
node = node.left;
while(node.right != null && !node.isRightThread) {
node = node.right;
}
}
}
}
/**
* 前序线索化二叉树
* @param node
*/
void preThreadOrder(Node node) {
if(node == null) {
return;
}
//左指针为空,将左指针指向前驱节点
if(node.left == null) {
node.left = preNode;
node.isLeftThread = true;
}
//前一个节点的后继节点指向当前节点
if(preNode != null && preNode.right == null) {
preNode.right = node;
preNode.isRightThread = true;
}
preNode = node;
//处理左子树
if(!node.isLeftThread) {
preThreadOrder(node.left);
}
//处理右子树
if(!node.isRightThread) {
preThreadOrder(node.right);
}
}
/**
* 前序遍历线索二叉树（按照后继线索遍历）
* @param node
*/
void preThreadList(Node node) {
while(node != null) {
while(!node.isLeftThread) {
System.out.print(node.data + ", ");
node = node.left;
}
System.out.print(node.data + ", ");
node = node.right;
}
}
public static void main(String[] args) {
String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};
Node root = createBinaryTree(array, 0);
ThreadBinaryTree tree = new ThreadBinaryTree();
tree.inThreadOrder(root);
System.out.println("中序按后继节点遍历线索二叉树结果：");
tree.inThreadList(root);
System.out.println("\n中序按后继节点遍历线索二叉树结果：");
tree.inPreThreadList(root);
Node root2 = createBinaryTree(array, 0);
ThreadBinaryTree tree2 = new ThreadBinaryTree();
tree2.preThreadOrder(root2);
tree2.preNode = null;
System.out.println("\n前序按后继节点遍历线索二叉树结果：");
tree.preThreadList(root2);
}
10，森林，二叉树，树的转换
11，二叉排序树（查找）
12，二叉平衡树（查找）
11，赫夫曼树
