二叉树
就是度不超过2的树（每个结点最多只有两个子结点）。如图
满二叉树
当二叉树的每一个层的结点树都达到最大值，则这个二叉树就是满二叉树。
完全二叉树
叶结点只能出现在最下层和次下层，且最下面一层的结点都集中在该层最左边的若干位置的二叉树。就是说你结点尽量往左边靠，先把左边位置填满。
斜二叉树
分为左斜树（所有的结点都只有左子树的二叉树）和右斜树（所有的结点都只有右子树的二叉树）。
（1）二叉树的第i层中至多有2^i-1个结点（i>=1）
（2）深度为k的二叉树至多有2^k-1个结点（k>=1）
（3）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
（4）具有n个结点的完全二叉树的深度为不大于log2^n的最大整数再加1。
（5）如果对一棵有n个结点的完全二叉树（其深度为不大于log2^n的最大整数再加1）的结点按层序编号，对任意结点i（1<=i<=n）有：
如果i=1，那么结点i是二叉树的根，无双亲；如果i>1,那么其双亲是结点不大于i/2的最大整数如果2i>n,那么结点i无左孩子（结点i为叶结点）；否则其左孩子是结点2i如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1 4、 二叉树的存储结构 4.1 顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，如双亲与孩子的关系，兄弟关系等
下面是完全二叉树的顺序存储
对于一般的二叉树尽管层序编号不能反映逻辑关系但是可以将其按完全二叉树编号，不过，将不存在的结点设置为“^”。如下
但当k深度的右斜树出现时，顺序存储会对存储空间造成很大浪费，所以一般这种顺序存储结构只用于完全二叉树
二叉树的每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域（lchild左指针指向左子树，rchild有有指针指向右子数），这样的链表叫做二叉链表。如图
查找树原理就是利用键值对中的键的大小来排好结点的顺序，方便查找树中的某个结点
方法原理分析（一）put方法：创建树或添加新结点的实现
1、如果当前树中没有任何一个结点，则直接把新结点当做根结点使用
2、如果当前树不为空，则从根结点开始：
（1）如果新结点的key小于当前结点的key，则继续找当前结点的左子结点
（2）如果新结点的key大于当前结点的key，则继续找当前结点的右子结点
（3）如果新结点的key等于当前结点的key，则树中返回当前结点的value
（二）get方法：获取对应的结点的key或者value
从根结点开始，
1、如果要查找的结点的key小于当前结点的key，则继续找当前结点的左子结点
2、如果要查询的结点的key大于当前结点的key，则继续找当前结点的右子结点
3、如果要查询的结点的key等于当前结点的key，则树中返回当前结点的value
（三）delete方法：删除指定结点
1、找到要删除的结点
2、找到被删除结点右子树中的最小结点minNode
3、被删除结点的父结点指向被删除结点右子树中的最小结点
public class BinaryTree,Value> { private Node root; private int Num; private class Node{ public Key key; //存储键 public Value value; //存储值 public Node left; //记录左节点 public Node right; //记录右结点 public Node(Key key, Value value, Node left, Node right) { this.key = key; this.value = value; this.left = left; this.right = right; } } //----------------------------------------------------------------- //获取树中元素个数 public int size(){ return Num; } //----------------------------------------------------------------- //向树中添加元素key-value public void put(Key key, Value value){ root = put(root, key, value); } //----------------------------------------------------------------- //向指定的树x中添加key-value，并返回添加元素后的新的树 public Node put(Node x, Key key, Value value){ //当x子树为空时 if(x==null){ Num++; return new Node(key,value,null,null); } //当x子树不为空 //比较x结点的键和key的大小 int cmp = key.compareTo(x.key); if(cmp>0){ //如果key大于x结点的键，则继续找x结点的左子树 x.right = put(x.right, key, value); }else if(cmp<0){ //如果key小于x结点的键，则继续找x结点的右子树 x.left = put(x.left,key,value); }else{ //如果key等于x结点的键，则替换x结点的值为value x.value = value; } return x; } //----------------------------------------------------------------- //查询树中指定key对应的value public Value get(Key key){ return get(root,key); } //----------------------------------------------------------------- //从指定的树x中查找key对应的值 public Value get(Node x, Key key){ //x树为null if(x==null){ return null; } //x树不为null //比较x结点的键和key的大小 int cmp = key.compareTo(x.key); if(cmp>0){ //如果key大于x结点的键，则继续找x结点的右子树 return get(x.right,key); }else if(cmp<0){ //如果key小于x结点的键，则继续找x结点的左子树 return get(x.left,key); }else{ //如果key等于x结点的键，则替换x结点的value值 return x.value; } } //----------------------------------------------------------------- //删除树中key对应的value public void delete(Key key){ delete(root,key); } //----------------------------------------------------------------- //删除指定树x中的key对应的value，并返回删除后的新树 public Node delete(Node x, Key key){ //当树为空时 if(x==null){ return null; } //当树不为空 int cmp = key.compareTo(x.key); //先找到要删除的结点 if(cmp>0){ //如果key大于x结点的键，那么继续找x结点的右子树 x.right = delete(x.right,key); }else if(cmp<0){ //如果key小于x结点的键，那么继续找x结点的左子树 x.left = delete(x.left,key); }else{ //如果key等于x结点的键，则找到了要删除的结点，完成删除操作 //先找到x的右子树中最小的结点，之后用它来连接树 //元素个数减1 Num--; //如果树x的右结点为空，则返回x的左结点 if(x.right == null){ return x.left; } //如果树x的结左点为空，则返回x的右结点 if(x.left == null){ return x.right; } //当上面两个if都不成立，则循环找到x树的右子树中的最小值 Node minNode = x.right; while(minNode.left!=null){ minNode = minNode.left; } //删除右子树中最小的结点 Node n = x.right; while(n.left != null){ if(n.left.left == null){ n.left = null; }else{ n = n.left; } } //让x结点的左子树成为minNode左子树 minNode.left = x.left; //让x结点的右子树称为minNode右子树 minNode.right = x.right; //让x结点的父结点指向minNode x = minNode; } return x; } //----------------------------------------------------------------- //查找树中最小的键 public Key min(){ return min(root).key; } //在指定树x中找到最小键所在的结点 public Node min(Node x){ //判断x是否还有左结点，有，继续找，没有，则当前结点为最小结点 if(x.left!=null){ return min(x.left); }else{ return x; } } //----------------------------------------------------------------- //查找树中最大的键 public Key max(){ return max(root).key; } //在指定树x中找到最小键所在的结点 public Node max(Node x){ //判断x是否还有右结点，有，继续找，没有，则当前结点为最大结点 if(x.right != null){ return max(x.right); }else{ return x; } } }
测试代码
public class BinaryTreeTest {
public static void main(String[] args) {
//创建二叉查找树对象
BinaryTree tree = new BinaryTree<>();
tree.put(8,"张三");
tree.put(9,"李四");
tree.put(3,"王五");
tree.put(10,"赵六");
System.out.println(tree.size());
//测试获取
System.out.println("键2对应的元素时：" + tree.get(9));
//测试删除
tree.delete(9);
System.out.println("删除键3对应的元素：" + tree.get(9));
System.out.println("删除后的元素个数：" + tree.size());
System.out.println("键" + + tree.min() + "对应的值为" + tree.get(tree.min()));
}
}
结果：
6、二叉树的遍历 概述4
键2对应的元素时：李四
删除键3对应的元素：null
删除后的元素个数：3
键3对应的值为王五
问题描述：
树的遍历不像数组，集合的遍历一样，树状结构和线性结构是不同的，没有办法从头开始一次向后遍历，所以需要一些特殊的搜索路径来进行遍历，常用的基础遍历方式（深度优先思想）有前序遍历，中序遍历，后序遍历。。。(这里的前中后可以理解成根结点访问的位置和顺序，例如先访问根结点叫前序，中间访问根结点叫中序，最后访问根结点叫做后序），高级遍历方式（广度优先思想）有层序遍历。
如图：
前序遍历：EBADCGFH
中序遍历：ABCDEFGH
后序遍历：ACDBFHGE
层序遍历：EBGADFHC
特点
先访问根节点，再访问左子树，最后访问右子树
实现步骤
（1）把当前结点的key放入到队列中
（2）找到当前结点的左子树，如果不为空，递归遍历左子树
（3）找到当前结点的右子树，如果不为空，递归遍历右子树
代码如下
//前序遍历
//获取整个树中所有的键
public linkedQueue preErgodic(){
linkedQueue keys = new linkedQueue();
preErgodic(root,keys);
return keys;
}
//获取指定树x中的所有键，并放到keys队列中
private void preErgodic(Node x, linkedQueue keys ){
if(x==null){
return ;
}
//将x结点的key放入到keys中
keys.Enqueue(x.key);
//递归遍历x结点的左子树
if(x.left != null){
preErgodic(x.left,keys);
}
//递归遍历x结点的右子树
if(x.right != null){
preErgodic(x.right,keys);
}
}
中序遍历
特点
先访问左子树，再访问根节点，最后访问右子树
实现步骤
（1）找到当前结点的左子树，如果不为空，递归遍历左子树
（2）把当前结点的key放入到队列中
（3）找到当前结点的右子树，如果不为空，递归遍历右子树
代码如下
//中序遍历
//获取整个树中所有的键
public linkedQueue midErgodic(){
linkedQueue keys = new linkedQueue<>();
midErgodic(root,keys);
return keys;
}
//把指定树x中的所有键放入到队列keys中
public void midErgodic(Node x, linkedQueue keys){
if(x == null){
return ;
}
//先递归将左子树中的键放入到队列keys中
if(x.left != null){
midErgodic(x.left, keys);
}
//再递归将x结点的key放入到keys中
keys.Enqueue(x.key);
//递归将右子树中的键放入到队列keys中
if(x.right != null){
midErgodic(x.right, keys);
}
}
后序遍历
特点
先访问左子树，再访问右子树，最后访问根节点
实现步骤
（1）找到当前结点的左子树，如果不为空，递归遍历左子树
（2）找到当前结点的右子树，如果不为空，递归遍历右子树
（3）把当前结点的key放入到队列中
代码如下
//后序遍历
//获取整个树中的所有键
public linkedQueue afterErgodic(){
linkedQueue keys = new linkedQueue<>();
afterErgodic(root,keys);
return keys;
}
//获取树x中的所有键并将它们放入到keys队列中
public void afterErgodic(Node x, linkedQueue keys){
if(x == null){
return ;
}
//先递归将左子树中的key放入到队列keys中
if(x.left != null){
afterErgodic(x.left, keys);
}
//再递归将右子树中的key放入到keys中
if(x.right != null){
afterErgodic(x.right, keys);
}
//递归将x结点的key放入到队列keys中
keys.Enqueue(x.key);
}
层序遍历
特点
按照树的从上到下，从左到右的顺序遍历,用到的是广度优先思想
步骤
1、创建队列存储每一层的结点
2、使用循环从队列中弹出一个结点
（1）获取当前结点的key
（2）如果当前结点的左结点不为空，则把左结点放入到队列中
（3）如果当前结点的右结点不为空，则把右结点放入到队列中
代码如下
//层序遍历
public linkedQueue layerErgodic(){
//定义两个队列，分别用来存储树中的键和结点
linkedQueue keys = new linkedQueue<>();
linkedQueue nodes = new linkedQueue<>();
//默认：往队列中放入根结点
nodes.Enqueue(root);
while(!nodes.isEmpty()){
//从队列中弹出一个结点，将key放入到keys中
Node n = nodes.Dequeue();
keys.Enqueue(n.key);
//判断当前结点还有没有左结点，有则放入nodes中
if(n.left != null){
nodes.Enqueue(n.left);
}
//判断当前结点还有没有右结点，有则放入nodes中
if(n.right != null){
nodes.Enqueue(n.right);
}
}
return keys;
}
这四种遍历的测试代码及结果如下
public static void main(String[] args) {
BinaryTree sbt = new BinaryTree<>();
sbt.put("E","5");
sbt.put("B","2");
sbt.put("G","7");
sbt.put("A","1");
sbt.put("D","4");
sbt.put("F","6");
sbt.put("H","8");
sbt.put("C","3");
linkedQueue keys1 = sbt.preErgodic();
//前序遍历
System.out.println("前序遍历---------");
for(String key : keys1){
String value = sbt.get(key);
System.out.println(key + "----" + value);
}
//中序遍历
System.out.println("中序遍历---------");
linkedQueue keys2 = sbt.midErgodic();
for(String key : keys2){
String value = sbt.get(key);
System.out.println(key + "----" + value);
}
//后序遍历
System.out.println("后序遍历--------");
linkedQueue keys3 = sbt.afterErgodic();
for(String key : keys3){
String value = sbt.get(key);
System.out.println(key + "----" + value);
}
//层序遍历
System.out.println("层序遍历-------");
linkedQueue keys4 = sbt.layerErgodic();
for(String key : keys4){
String value = sbt.get(key);
System.out.println(key + "----" + value);
}
}
7、相关问题 最大深度问题前序遍历---------
E----5
B----2
A----1
D----4
C----3
G----7
F----6
H----8
中序遍历---------
A----1
B----2
C----3
D----4
E----5
F----6
G----7
H----8
后序遍历--------
A----1
C----3
D----4
B----2
F----6
H----8
G----7
E----5
层序遍历-------
E----5
B----2
G----7
A----1
D----4
F----6
H----8
C----3
问题描述
给定一棵树，计算树的最大深度（树的根结点到最远叶结点的最长路径上的结点数）
实现步骤
1、如果根结点为空，则最大深度为0
2、计算左子树的最大深度
3、计算右子树的最大深度
4、当前树的最大深度=左子树的最大深度和右子树的最大深度中的最大者加1
代码如下
//计算整个树的最大深度
public int maxDepth(){
return maxDepth(root);
}
//计算指定树x的最大深度
public int maxDepth(Node x){
if(x == null){
return 0;
}
int max = 0;
int maxL = 0;
int maxR = 0;
//计算x结点左子树的最大深度
if(x.left != null){
maxL = maxDepth(x.left);
}
//计算x结点右子树的最大深度
if(x.right != null){
maxR = maxDepth(x.right);
}
//比较左右子树，取其中的最大者再加1
max = maxL>maxR?maxL+1:maxR+1;
return max;
}
