二叉树附demo，前序遍历、后序遍历、层序遍历、删除一个二叉树的节点，前驱后继节点等概念啊和原理
基本概念
- 没有任何节点的树叫做空树
- 节点的度：子树的个数称为度
- 树的度：所有节点度中最大的值，即为树的度
- 叶子节点：度为0的节点
- 节点深度：从根节点到当前节点的唯一路径上的节点总数
- 节点的高度：从当前节点到最远叶子节点的路径上的节点总数
- 树的深度：所有节点深度中的最大值
- 树的高度：所有节点高度的最大值。
- 树的深度等于树的高度
- 有序树：树中任意节点的子节点之间有顺序关系
二叉树（Binary Tree）
- 每个节点的度最大为2
- 左子树和右子树是有顺序的
- 及时某节点只有一颗子树，也要区分左右子树
- 二叉树是有序树
- 非空二叉树的第i层，最多有2^(i-1)个节点（i>=1）
- 高度为h的二叉树，最多有(2^h)-1个节点(h>=1)
- 对于一个非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2,则 n0=n2+1;
真二叉树
- 所有节点的度要么为0要么为2
满二叉树
- 所有节点的度，要么为0，要么为2，切所有叶子节点都在最后一层。
- 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
- 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
- 如果二叉树的高度为 h，那么第i层的节点数量为 2^i-1 个节点
- 如果二叉树的高度为 h，叶子节点数量为 2^(h - 1) 个。
- 高度为h的满二叉树，有(2^h)-1个节点(h>=1)
完全二叉树
- 叶子节点只会出现在最后两层，切最后一层的叶子节点都靠左对齐
- 完全二叉树从根节点到倒数第二层为满二叉树
- 度为1的节点只有左子树
- 度为1的节点，要么是一个，要么是0个
- 同样节点的二叉树，完全二叉树的高度是最小的
- 假设完全二叉树的高度为h，那么他至少有2(h-1)个节点，最多有2(h)-1
- 总结点数量为n,那么 2^(h-1)<= n < 2^h
- 一颗有n个节点的完全二叉树，从上到下，从左到右对节点从1开始进行编号，对任意节点，如果i=1，那么他是根节点，如果i>1,他的父节点为floor(i/2),向下取整。
- 如果2i<=n,他的左节点编号为2i,如果2i>n,他没有左子节点
- 如果2i+1<=n,他的右节点编号为2i+1，如果2i+1>n,他没有右节点
- 假设总结点数为n,那么叶子节点，n0=(n+1)/2,向下取整，n0=(n+1)>>1
二叉搜索树
- 任意一个节点的值都大于其左子树所有的值
- 任意一个节点的值，都小于他右子树所有的值
- 没有索引的概念
二叉树遍历
前序遍历
根节点，前序遍历左子树，前序遍历右子树，根左右,根节点在前面
中序遍历
先中序遍历左子树，根节点，然后中序遍历右子树。左根右,顺序从小到大排列，因为先访问左，在访问根，在访问右，根节点在中间
如果右根左，那么就是降序。
后序遍历
先后续遍历左子树，然后右子树，最后根节点，左右根，根节点在后面
层序遍历
从上到下，从左到右遍历
重构还原二叉树
- 前序遍历结果 + 中序
- 后序 + 中序
以上组合能够还原一颗二叉树
- 如果只给前序+后序，如果他是一颗真二叉树，那么结果唯一，否则不唯一
因为比如我们的二叉树没有右子树，或者没有左子树，那么我们前序遍历的顺序为 根 左右，那么除了根节点后面要么是左子树，要么是右子树，后序遍历为，左右根，最后一个为根节点，前面是左右所以前面的左右或者后面的左右，只剩下一棵树，要么左要么右，我们是没办法确定是左子树还是右子树,因为左右混在一下，一旦有一个为空，就没法判断了。
因为限定了真二叉树的这个条件，真二叉树，要么度为0，要么度为2，所以，一个节点的左右节点，要么同时存在，要么同时不存在。
根 左 右
左 右 根
从前序遍历，我们可以确定左子树的根节点，然后拿到这个根节点，去后续遍历里面，就可以找到左子树的根节点，从而就知道右子树从哪里开始，只要能将左右划分出来，知道哪些是左子树，哪些是右子树，就可以了。
前驱结点
前驱结点：中序遍历时候的前一个节点。
二叉搜索树，前驱结点，是他的左子树的最大的那个节点，也就是一定在最右边，一直往右找，如果不是二叉搜索树，那也使用，因为他的前驱结点，是中序遍历的前一个节点，中序遍历的左根右，也是最后遍历右节点，所以，如果这个节点的左子树存在，那么就找这个左子树沿着右子树找到最后一个就行了。
pre = node.left.right.right.right.right... 一直到 null
如果node的left为空，那么他的额前驱结点为，一直往上找父节点，直到当前节点为父节点的右子树，就停止。那么这个父节点就为前驱结点，循环往上找，知道当前node为node.parent的right就停止,那么这个node就为我们要找的，如果一直晚上找，突然发现父节点为空了，那么这个节点就没有前驱结点。
如果这个节点没有左子树也没有父节点，那么这个节点没有前驱结点
后继节点
后继节点刚好和上面的前驱结点相反，将前驱结点的左改为右，右改为左就行
删除二叉树的节点
- 如果度为0，直接删除
- 如果度为1，如果 node 的 left 存在，那么 node.parent.left = node.left,node.left.parent = node.parent。如果 node 的right存在，node.parent.right = node.right,no.right.parent = node.parent.
- 如果度为2，先用前驱或者后继节点覆盖原来节点的值，然后删除相应的前驱或者后继节点，因为如果度为2，删除这个节点，就相当于删除了中间的节点，相当于删除了中间值，因为左边的值比这个值小，右边的值比这个值大，所以如果想找个值替代，要么是前驱结点，左子树最大的那个值，或者是后继节点，右子树最小的那个值，这样放到中间就可以了。并且我们的前驱或者后继节点，他的度只能为1或者0，比如前驱结点，他的度不可能为2，因为是一直向右查找，如果度为2，那么必定还能继续查找，所以他的度只能为1只有左子树或者只能为0，如果是后继节点也一个道理，只不过相反。
