why 树#
- 顺序存储
顺序存储的特点是各个存储单位在逻辑和物理内存上都是相邻的，典型的就是代表就是数组,物理地址相邻因此我们可以通过下标很快的检索出一个元素。
我们想往数组中添加一个元素最快的方式就是往它的尾部添加。如果往头部添加元素的话效率就很低，因为需要将从第一个元素开始依次往后移动一位，这样就能空出第一位的元素，然后才能将我们指定的数据插入到第一个的位置上。
- 链式存储
链式存储的特点是：各个节点之间逻辑是相邻的，但是物理存储上不相邻，每一个节点都存放一个指针或者是引用用来指向它的前驱或者后继节点, 因此我们想插入或者删除一个元素时速度就会很块，只需要变动一下指针的指向就行。
但是对链表来说查找是比较慢的，因为对任意一个节点来说，它只知道自己的下一个节点或者是上一个节点在哪里。因此每次查找都需要从头结点开始遍历...
- 树
树型存储结构有很多种。比如什么二叉树、满二叉树、B树、B+树、红黑树等，对于树形结构来说，它会相对中和链式存储结构和顺序存储结构的优缺点 (其中二叉排序树最能直接的体现出树中和链式存储和线性存储的特性，下文有说)
树的概述#
如上图是一个二叉树，当然树还能有三叉，四叉等，对树来说它们有如下的诸多属性。
- 根节点: 最顶上的节点 即a
- 层: 根节点在第一层 BE在第二层
- 高度: 最大的层数
- 森林: 多个树的组合
- 权: 节点上的值 如根节点的权是 a
- 叶子节点: 下层上的节点是上一层的叶子节点
- 双亲节点: 上层的节点是下层的节点的双亲节点(单个节点又是爸又是妈)
- 路径: 找到C的路径是 a-b-c
- 度: 就是直接子节点的个数
普通二叉树#
- 什么是二叉树?
顾名思义就是度最大为2的树就是二叉树。而且对二叉树来说是严格区分左子树和右子树的。看上图，虽然两个树的根节点都是1，但是它们的左右子树不同，因此它们并不是相同的树。
- 什么是满二叉树?
像上图这样所有的叶子节点都在最后一层，除了最后一层之外其他层的节点都有两个子节点。
二叉树的全部节点计算公式是2^n-1 , n是层数
- 什么是完全二叉树?
像上图这样，所有的叶子点都在最后一层或者是倒数第二层，并且从左往右数是连续的。
java&二叉树#
- 封装二叉树节点
public class TreeNode { // 权 private int value; // 左节点 private TreeNode leftNode; // 右节点 private TreeNode rightNode; }
- 封装二叉树
public class BinaryTree { TreeNode root; public void setRoot(TreeNode root) { this.root = root; } public TreeNode getRoot() { return this.getRoot(); } }
遍历#
像这样一颗二叉树，通过不同的顺序遍历会得到不同的结果。
前中后的顺序说的是root节点的顺序，前序的话就是先遍历父节点，中序就是左父右 后续就是左右父。
- 前序遍历
public void frontShow() { System.out.println(this.value); if (leftNode != null) leftNode.frontShow(); if (rightNode != null) rightNode.frontShow(); }
- 中序遍历
public void middleShow() { if (leftNode != null) leftNode.middleShow(); System.out.println(value); if (rightNode != null) rightNode.middleShow(); }
- 后续遍历
public void backShow() { if (leftNode != null) leftNode.backShow(); if (rightNode != null) rightNode.backShow(); System.out.println(value); }
查找#
其实有了上面三种遍历的方式，查找自然存在三种，一边遍历一边查找。
public TreeNode frontSeach(int num) { TreeNode node = null; // 当前节点不为空,返回当前节点 if (num == this.value) { return this; } else { // 查找左节点 if (leftNode != null) { node = leftNode.frontSeach(num); } if (node != null) return node; // 查找右节点 if (rightNode != null) node = rightNode.frontSeach(num); } return node; }
删除节点#
删除节点也是，不考虑特别复杂的情况，删除节点就有两种情况：第一种要删除的节点就是根节点，那么让根节点=null就ok。第二种情况要删除的节点不是根节点，就处理它的左右节点，左右节点还不是需要删除的元素的话那么就得递归循环这个过程。
// 先判断是否是根节点,在调用如下方法 public void deleteNode(int i) { TreeNode parent = this; // 处理左树 if (parent.leftNode!=null&&parent.leftNode.value==i){ parent.leftNode=null; return; } // 处理左树 if (parent.rightNode!=null&&parent.rightNode.value==i){ parent.rightNode=null; return; } // 递归-重置父节点 parent=leftNode; if (parent!=null) parent.deleteNode(i); // 递归-重置父节点 parent=rightNode; if (parent!=null) parent.deleteNode(i); }
顺序存储二叉树#
文章一开始刚说了，顺序存储的数据结构的典型代表就是数组，如下：
[1,2,3,4,5,6,7]
什么是顺序存储的二叉树呢? 其实就是将上面的数组看成了一颗树，就像下图这样
数组转换成二叉树是有规律的，这个规律就体现在它们的下标的关联上，比如我们想找2节点的左子节点的下标就是 2*n -1 = 3 , 于是我们从数组中下标为3的位置取出4来
- 第n个元素的左子节点是 2n-1
- 第n个元素的右子节点是 2n-2
- 第n个元素的父节点是 (n-1)/2
- 遍历顺序存储的二叉树
public void frontShow(int start){ if (data==null||data.length==0){ return; } // 遍历当前节点 System.out.println(data[start]); // 遍历左树 if (2*start+1<data.length) frontShow(2*start+1); // 遍历右树 if (2*start+2<data.length) frontShow(2*start+2); }
