数据结构学习成果二叉树部分分享：
此博客内容目录：
- 树
- 基本概念
- 基本实现
- 二叉树
- 基本概念
- 基本实现
- 特殊二叉树
- 二叉树的遍历
树是n（n>=0）个结点的有限集，当n=0时，称为空树。
图解：
1.结点A称为‘根’，一棵树中有且只有一个 根，即为该树的根节点。
2.树是一种递归的数据结构，每一个结点都可以形成以他为根节点的子树。
3.与结点A直接相连的结点B、C、D为后继结点，又称为结点A的孩子，结点A是他们的父亲。
4.结点B、C、D互为彼此的兄弟结点，自然结点F与结点H互为堂兄弟。
5.从根A到结点K的唯一路上的任意结点，称为结点K的祖先，例如结点B是结点K的祖先，自然结点K是结点B的子孙。
6.没有孩子的结点称为树叶
7.树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。
8.树的高度（或深度）是树中结点的最大层数。
9.树的宽度是具有最多结点数的层中包含的结点数。
10.两个结点之间所经过的结点序列构成路径，树中的路径是从上到下的，同一父亲的两个孩子之间不存在路径。
森林是m（m>=0）棵互不相交的树的集合。
基本实现class TreeNode{
Object element;
TreeNode parent;
List children;
public TreeNode(Object element){
this.element = element;
this.parent = new TreeNode();
this.children = new Linkedlist();
}
}
二叉树
基本概念
二叉树即为一棵每个结点都不能有多于两个孩子的特殊类型的树。
图像：
特性：
二叉树是有序树，即区分左子树和右子树，若左、右子树颠倒，则成为另一棵不同的二叉树。
class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
left = null;
right = null;
this.value = data;
}
}
特殊二叉树
1.满二叉树
树中的每层都含有最多的结点
图解：
代码：判断一棵二叉树是否为满二叉树
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println(isFull(root)); //true
}
public static class ReturnData{
public int height; //高度
public int nodes; //结点数
public ReturnData(int h,int n){
height = h;
nodes = n;
}
}
public static boolean isFull(TreeNode root){
if (root==null){
return true;
}
ReturnData data = process(root);
//return data.nodes == (1<< data.height)-1;
return data.nodes == Math.pow(2,data.height)-1;
}
public static ReturnData process(TreeNode root){
if (root==null){
return new ReturnData(0,0);
}
ReturnData leftData = process(root.left);
ReturnData rightData = process(root.right);
int height = Math.max(leftData.height,rightData.height) + 1;
int nodes = leftData.nodes + rightData.nodes +1 ;
return new ReturnData(height,nodes);
}
分析：满二叉树的高度与结点数存在函数关系：nodes = 2^height -1;
2.完全二叉树
高为h,结点数为n的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时被称为完全二叉树。
图像：
代码：
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
System.out.println(isCompleteTree(root)); //true
}
//判断是否为完全二叉树
public static boolean isCompleteTree(TreeNode root) {
if(root==null){
return true;
}
LinkedList queue = new LinkedList<>();
boolean leaf = false;
TreeNode Left = null;
TreeNode Right = null;
queue.add(root);
while(!queue.isEmpty()){
root = queue.poll();
Left = root.left;
Right = root.right;
if((leaf&&(Left!=null||Right!=null))||(Left==null&&Right!=null)){
return false;
}
if(Left!=null){
queue.add(Left);
}
if(Right!=null){
queue.add(Right);
}
if(Left==null||Right==null){
leaf = true;
}
}
return true;
}
分析：依次让每个结点进队列，找出第一个孩子结点不全的结点，若其有右孩子结点而无左孩子结点或其后仍有结点有孩子，则说明这不是一个完全二叉树。
3.平衡二叉树
树上任一结点的左子树和右子树的深度之差的绝对值不超过1。
图像：
代码：判断一棵二叉树是否为平衡二叉树
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.println(isAVL(root));
}
public static boolean isAVL(TreeNode root){
return process(root).isBalanced;
}
public static class ReturnType{
public boolean isBalanced;
public int height;
public ReturnType(boolean isB,int gao){
isBalanced = isB;
height = gao;
}
}
public static ReturnType process(TreeNode root){
if (root==null){
return new ReturnType(true,0);
}
ReturnType leftData = process(root.left);
ReturnType rightData = process(root.right);
int height = Math.max(leftData.height,rightData.height) + 1;
boolean isBalanced = leftData.isBalanced && rightData.isBalanced && Math.abs(leftData.height
-rightData.height)<2;
return new ReturnType(isBalanced,height);
}
分析：利用递归的方法判断每个结点的左子树和右子树分别是否为平衡二叉树，只要出现一个子树不满足则说明这不是一个平衡二叉树。
4.搜索二叉树
也称二叉排序树，左子树上所有结点的值均小于根节点的值，右子树上的所有结点的值均大于根节点的值，左子树和右子树又各是一棵搜索二叉树。
图解：
代码：判断一棵二叉树是否为搜索二叉树
public static void main(String[] args) {
TreeNode root= new TreeNode(9);
root.left = new TreeNode(5);
root.right = new TreeNode(13);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(7);
root.right.left = new TreeNode(11);
root.right.right = new TreeNode(15);
root.left.left.left = new TreeNode(1);
root.left.left.right= new TreeNode(3);
root.left.right.left = new TreeNode(6);
root.left.right.right = new TreeNode(8);
root.right.left.left = new TreeNode(10);
root.right.left.right = new TreeNode(12);
System.out.println(isValidBST(head)); //true
}
//判断搜索二叉树
public static boolean isValidBST(TreeNode root) {
long pre = Long.MIN_VALUE;
if(root==null){
return true;
}
//访问左子树
if(!isValidBST(root.left)){
return false;
}
//访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足搜索二叉树，返回 false；否则继续遍历
if(root.value<=pre){
return false;
}
pre = root.value;
//访问右子树
return isValidBST(root.right);
}
分析：二叉树中序遍历的值呈递增的趋势即可说明为搜索二叉树，关于中序遍历后面会讨论。
二叉树的遍历先给定一个二叉树供讨论：
二叉树的递归序：
public static void BinaryRecur(TreeNode root){
if(root==null){
return;
}
System.out.println(root.value+"");
BinaryRecur(root.left);
System.out.println(root.value+"");
BinaryRecur(root.right);
System.out.println(root.value+"");
}
结果：1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1
分析：每次递归都会有一次返回，先从1->2->4,又4为树叶无孩子结点，则会返回null->4->null->4,即为4->4。
继续返回至2->5,如4一样null->5->null->5,即为2->5->5->5;
然后从5返回2再返回1，进而进入右子树进行递归，像左边一样
将打印语句放置每次递归返回的地方得到递归序：
1->2->4->4->4->2->5->5->5->2->1->3->6->6->6->3->7->7->7->3->1
每个结点都被返回三次。
先序遍历：
访问顺序：
1.先访问根节点
2.左子树进行先序遍历
3.右子树进行先序遍历
第一步先访问根结点；第二步先序遍历左子树，这时你可以把左子树单独当做一棵树再执行上述的三个步骤，访问根结点，如果还有左子树，再访问左子树的根结点；第三步先序遍历右子树，跟第二步思想一样先是访问根节点，有左子树先访问左子树，然后右子树，直到树被遍历完。
代码实现：
//先序遍历(递归)
public static void preOrderRecur(TreeNode root){
if (root==null){
return;
}
System.out.print(root.value+"");
preOrderRecur(root.left);
preOrderRecur(root.right);
}
//先序遍历(非递归)
public static void preOrderRecur02(TreeNode root){
if (root!=null){
Stack stack = new Stack<>();
stack.add(root);
while(!stack.isEmpty()){
root = stack.pop();
System.out.print(root.value+"");
if (root.right!=null){
stack.push(root.right);
}
if (root.left!=null){
stack.push(root.left);
}
}
}
}
结果：1->2->4->5->3->6->7
分析：
递归方法与递归序的联系：第一次返回时打印
中序遍历：
访问顺序：
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
第一步中序遍历左子树，这时你可以把左子树单独当做一棵树再执行上述的三个步骤，如果还有左子树，先访问左子树，如果还有左子树…直到左子树的左孩子为空，第二步先访问根结点；第三步中序遍历右子树，跟第一步思想一样有左子树先访问左子树，然后根结点，最后右子树，直到树被遍历完。
代码实现：
//中序遍历(递归)
public static void inOrderRecur(TreeNode root){
if (root==null){
return;
}
inOrderRecur(root.left);
System.out.print(root.value+"");
inOrderRecur(root.right);
}
//中序遍历(非递归)
public static void inOrderRecur02(TreeNode root){
if (root!=null){
Stack stack = new Stack<>();
while (!stack.isEmpty()||root!=null){
if (root!=null){
stack.push(root);
root = root.left;
}else {
root = stack.pop();
System.out.println(root.value+"");
root = root.right;
}
}
}
}
结果：4->2->5->1->6->3->7
分析：
递归结果与递归序的联系：第二次返回的时候打印
或者用一种简单易行的方式：
后序遍历：
访问顺序：
1.后续遍历左子树
2.后序遍历右子树
3.访问根节点
第一步后序遍历左子树，这时你可以把左子树单独当做一棵树再执行上述的三个步骤，如果还有左子树，先访问左子树，如果还有左子树…直到左子树的左孩子或者右孩子为空，第二步后序遍历右子树，跟第一步思想一样有左子树先访问左子树，然后右子树，最后根结点；第三步先访问根结点，直到树被遍历完。
代码实现：
//后序遍历(递归)
public static void posOrderRecur(TreeNode root){
if (root==null){
return;
}
posOrderRecur(root.left);
posOrderRecur(root.right);
System.out.print(root.value+"");
}
//后序遍历(非递归)
public static void posOrderRecur02(TreeNode root){
if (root!=null){
Stack stack1 = new Stack<>();
Stack stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
root = stack1.pop();
stack2.push(root);
if (root.left != null) {
stack1.push(root.left);
}
if (root.right != null) {
stack1.push(root.right);
}
}
while (!stack2.isEmpty()){
System.out.println(stack2.pop().value+"");
}
}
}
结果：4->5->2->6->7->3->1
分析：
递归结果与递归序的联系：第三次返回时打印
