一、数组、链表、树的比较
数组存储方式扥解析：
优点：通过下标方式访问元素，速度快，对于有序数组还可以使用二分查找提高检索速度
缺点：如果要检索具体某个值，或者插入值会整体移动，效率低。
链式存储方式分析：
优点：在一定程度上度数组存储方式有优化，比如插入一个数值时，只需要将插入点接入到链表中即可，删除效率也是同样效果好。
缺点：在进行检索时，效率低，检索某个值时，需要从链表头一直做检索。
树存储方式分析：
能提高数据存储，读取效率，比如二叉树既可以保证数据检索速度，同时也可以保证数据插入，删除，修改的速度
二、二叉树
1、概述
二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能见得转换为二叉树，二叉树的存储结构及其算法都比较简单。二叉树的特点是每个节点最多只能有两个子树，且有左右之分
?常用术语：结点、根结点、父结点、子结点、叶子结点（没有子结点的结点）、结点的权（结点值）、路径（从root结点找到目标结点的线路）、层、子树、树的高度（最大层数）、森林（多颗子树成森林）
右边的权值大于父结点，左边权值小于父结点
?满二叉树：如果该二叉树的所有叶子结点都在最后一层，并且结点总数是2^n-1，n是层数
?完全二叉树：二叉树的所有叶子结点都在最后一层或者倒数第二层，而且最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续。
2.二叉树的应用案例
①可以使用前序，中序，后序对下面的二叉树进行遍历（无参情况下）
1、
前序遍历：先输出父结点，在遍历左子树和右子树
2、
中序遍历：先遍历左子树，在遍历父结点，再遍历右子树
3、
后序遍历：先遍历左子树，再遍历右子树，最后遍历父结点
还有就是根据编号进行前序中序后序查询
Node
package com.mei.tree;
public class Node {
private int no;
private String name;
private Node left;
private Node right;
public Node(int no, String name) {
this.no = no;
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", left=" + left +
", right=" + right +
'}';
}
/*
* 定义前序遍历
* */
public void preSelect(){
//先出福结点
System.out.println(this);
if(this.left!=null){
this.left.preSelect();
}
if(this.right!=null){
this.right.preSelect();
}
}
/*
* 中序遍历结点*/
public void infixSelect(){
//左节点 父结点 右结点
if (this.left!=null){
this.left.infixSelect();
}
System.out.println(this);
if (this.right!=null){
this.right.infixSelect();
}
}
//后序遍历
public void postSelect(){
//左右父
if (this.left!=null){
this.left.infixSelect();
}
if (this.right!=null){
this.right.infixSelect();
}
System.out.println(this);
}
//根据编号查询
/*
* 前序遍历查找
*/
public Node preSearch(int no){
/*
* 判断是否是当前结点
*/
if (this.no == no){
return this;
}
/*
* 判断当前结点的左子结点是否为空，如果不是空，则递归前序查找
如果左递归前序查找，找到结点，则返回
*/
Node lNode = null;
if (this.left !=null){
lNode = this.left.preSearch(no);
}
if (lNode !=null){
return lNode;
}
/*
* 左递归前序查找，找到结点，则返回否则继续判断
*
* 当前的结点的右子结点是否为空，如果不空，则继续像右递归前序查找
*/
if (this.right !=null){
lNode = this.right.preSearch(no);
}
return lNode;
}
/*
* 中序遍历查找
*/
public Node infixSearch(int no){
/*
* 判断当前结点左子结点是否为空，如果不为空，则递归中序查找
*/
Node node = null;
if (this.left !=null){
node = this.left.infixSearch(no);
}
if (node !=null){
return node;
}
if (this.no == no){
return this;
}
if (this.right !=null){
node = this.right.infixSearch(no);
}
return node;
}
/*
* 后序遍历查找
*/
public Node postSearch(int no){
Node node = null;
if (this.left !=null){
node = this.left.postSearch(no);
}
if (node !=null){
return node;
}
/*
* 如果左边子树没有找到，则向右边子树递归进行后序遍历查找
*/
if (this.right !=null){
node = this.right.postSearch(no);
}
if (node !=null){
return node;
}
/*
* 如果左右子树都没有找到，那么判断当前结点是否是呢
*/
if (this.no==no){
return this;
}
return node;
}
}
BinaryTree
package com.mei.tree;
public class BinaryTree {
private Node root;
public void setRoot(Node root) {
this.root = root;
}
public void preSelect(){
if (this.root !=null){this.root.preSelect();
}else {
System.out.println("二叉树为空，无法遍历");
}
}
public void infixSelect(){
if (this.root !=null){
this.root.infixSelect();
}else {
System.out.println("二叉树为空，无法遍历");
}
}
public void postSelect(){
if (this.root !=null){
this.root.postSelect();
}else {
System.out.println("二叉树为空，无法遍历");
}
}
/*
* 前序
*/
public Node preNode(int no){
if (root !=null){
return root.preSearch(no);
}else {
return null;
}
}
/*
* 中序
*/
public Node infixNode(int no){
if (root !=null){
return root.infixSearch(no);
}else {
return null;
}
}
/* 后序
*/
public Node postNode(int no){
if (root !=null){
return root.postSearch(no);
}else {
return null;
}
}
}
②删除结点
Node
/*删除结点两种情况
1、删除的结点是叶子结点
2、删除的结点是子树。非叶子结点
* */
public void delNode(int no){
/*
* 注意：
*
1、二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除，而不能去判断当前这个结点是不是需要删除结点
* 2、如果当前结点左子结点不为空，并且左子结点就是需要删除的结点，则将this.left = null,返回即可
* 3、如果当前结点右子结点不为空，并且右子结点就是需要删除的结点，就将this.right = null,返回即可
* 4、如果2,3步没有执行，那么需要向左子树进行递归删除
* 5、如果第4步也没有删除结点，则向右子树进行递归删除
*/
if (this.left!=null&&this.left.no==no){
this.left=null;
return;
}
if(this.right!=null&&this.right.no==no){
this.right=null;
return;
}
/*
* 向左子树进行递归删除*/
if (this.left!=null){
this.left.delNode(no);
}
/*
* 向右子树进行递归删除
* */
if(this.right!=null){
this.right.delNode(no);
}
}BinaryTree
/*
* 删除结点 */
public void delNode(int no){
if (root !=null){
if (root.getNo()==no){
root = null;
}else {
root.delNode(no);
}
}else {
System.out.println("树为空，不能操作删除");
}
}3.二叉排序树
二叉排序树又称二叉查找树，也称二叉搜索树，查询效率比链表结构要高。如果有相同的值，可以将该节点放在左子结点和右子结点。同一数据对应的二叉排序树不唯一。但经过终须遍历得到的关键码序列都是一个递增序列。
二叉排序树的创建和遍历
package com.mei.binarysort;
public class Node {
public int value;
public Node left;
public Node right;
public Node (int value){
this.value=value;
}
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
/*public Node search(int value){
if (value == this.value){
return this;
}
else if (value< this.value){//如果小于当前结点，则向左子树递归查询
//如果左子树结点为空
if (this.left == null){
return null;
}return this.left.search(value);
}
else
{//如果大于当前结点，则向左子树递归查询
if (this.right == null){
return null;
}return this.right.search(value);
}
}*/
public void add(Node node){
if (node == null){
return;
}
//判断传入的节点值与当前节点值关系
if (node.value< this.value){
if (this.left == null){
this.left = node;
} else
{//向当前节点左子树递归
this.left.add(node);
}
} else {//添加的结点值大于当前结点值
if (this.right == null){
this.right = node;
} else {this . right .add(node);
}
}
}
}