二叉树附demo，前序遍历、后序遍历、层序遍历、删除一个二叉树的节点，前驱后继节点等概念啊和原理

demo

基本概念

1. 没有任何节点的树叫做空树
2. 节点的度：子树的个数称为度
3. 树的度：所有节点度中最大的值，即为树的度
4. 叶子节点：度为0的节点
5. 节点深度：从根节点到当前节点的唯一路径上的节点总数
6. 节点的高度：从当前节点到最远叶子节点的路径上的节点总数
7. 树的深度：所有节点深度中的最大值
8. 树的高度：所有节点高度的最大值。
9. 树的深度等于树的高度
10. 有序树：树中任意节点的子节点之间有顺序关系

二叉树（Binary Tree）

1. 每个节点的度最大为2
2. 左子树和右子树是有顺序的
3. 及时某节点只有一颗子树，也要区分左右子树
4. 二叉树是有序树
5. 非空二叉树的第i层，最多有2^(i-1)个节点（i>=1）
6. 高度为h的二叉树，最多有(2^h)-1个节点(h>=1)
7. 对于一个非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2,则 n0=n2+1;

真二叉树

1. 所有节点的度要么为0要么为2

满二叉树

1. 所有节点的度，要么为0，要么为2，切所有叶子节点都在最后一层。
2. 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总节点数量最多
3. 满二叉树一定是真二叉树，真二叉树不一定是满二叉树
4. 如果二叉树的高度为 h，那么第i层的节点数量为 2^i-1 个节点
5. 如果二叉树的高度为 h，叶子节点数量为 2^(h - 1) 个。
6. 高度为h的满二叉树，有(2^h)-1个节点(h>=1)

完全二叉树

1. 叶子节点只会出现在最后两层，切最后一层的叶子节点都靠左对齐
2. 完全二叉树从根节点到倒数第二层为满二叉树
3. 度为1的节点只有左子树
4. 度为1的节点，要么是一个，要么是0个
5. 同样节点的二叉树，完全二叉树的高度是最小的
6. 假设完全二叉树的高度为h，那么他至少有2^{(h-1)个节点，最多有2}(h)-1
7. 总结点数量为n,那么 2^(h-1)<= n < 2^h
8. 一颗有n个节点的完全二叉树，从上到下，从左到右对节点从1开始进行编号，对任意节点，如果i=1，那么他是根节点，如果i>1,他的父节点为floor(i/2),向下取整。
9. 如果2i<=n,他的左节点编号为2i,如果2i>n,他没有左子节点
10. 如果2i+1<=n,他的右节点编号为2i+1，如果2i+1>n,他没有右节点
11. 假设总结点数为n,那么叶子节点，n0=(n+1)/2,向下取整，n0=(n+1)>>1

二叉搜索树

1. 任意一个节点的值都大于其左子树所有的值
2. 任意一个节点的值，都小于他右子树所有的值
3. 没有索引的概念

二叉树遍历

前序遍历

根节点，前序遍历左子树，前序遍历右子树，根左右,根节点在前面

中序遍历

先中序遍历左子树，根节点，然后中序遍历右子树。左根右,顺序从小到大排列，因为先访问左，在访问根，在访问右，根节点在中间

如果右根左，那么就是降序。

后序遍历

先后续遍历左子树，然后右子树，最后根节点，左右根，根节点在后面

层序遍历

从上到下，从左到右遍历

重构还原二叉树

1. 前序遍历结果 + 中序
2. 后序 + 中序

以上组合能够还原一颗二叉树

3. 如果只给前序+后序，如果他是一颗真二叉树，那么结果唯一，否则不唯一

因为比如我们的二叉树没有右子树，或者没有左子树，那么我们前序遍历的顺序为 根 左右，那么除了根节点后面要么是左子树，要么是右子树，后序遍历为，左右根，最后一个为根节点，前面是左右所以前面的左右或者后面的左右，只剩下一棵树，要么左要么右，我们是没办法确定是左子树还是右子树,因为左右混在一下，一旦有一个为空，就没法判断了。

因为限定了真二叉树的这个条件，真二叉树，要么度为0，要么度为2，所以，一个节点的左右节点，要么同时存在，要么同时不存在。

根 左 右

左 右 根

从前序遍历，我们可以确定左子树的根节点，然后拿到这个根节点，去后续遍历里面，就可以找到左子树的根节点，从而就知道右子树从哪里开始，只要能将左右划分出来，知道哪些是左子树，哪些是右子树，就可以了。

前驱结点

前驱结点：中序遍历时候的前一个节点。

二叉搜索树，前驱结点，是他的左子树的最大的那个节点，也就是一定在最右边，一直往右找，如果不是二叉搜索树，那也使用，因为他的前驱结点，是中序遍历的前一个节点，中序遍历的左根右，也是最后遍历右节点，所以，如果这个节点的左子树存在，那么就找这个左子树沿着右子树找到最后一个就行了。

pre = node.left.right.right.right.right... 一直到 null

如果node的left为空，那么他的额前驱结点为，一直往上找父节点，直到当前节点为父节点的右子树，就停止。那么这个父节点就为前驱结点，循环往上找，知道当前node为node.parent的right就停止,那么这个node就为我们要找的，如果一直晚上找，突然发现父节点为空了，那么这个节点就没有前驱结点。

如果这个节点没有左子树也没有父节点，那么这个节点没有前驱结点

后继节点

后继节点刚好和上面的前驱结点相反，将前驱结点的左改为右，右改为左就行

删除二叉树的节点

1. 如果度为0，直接删除
2. 如果度为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.
3. 如果度为2，先用前驱或者后继节点覆盖原来节点的值，然后删除相应的前驱或者后继节点，因为如果度为2，删除这个节点，就相当于删除了中间的节点，相当于删除了中间值，因为左边的值比这个值小，右边的值比这个值大，所以如果想找个值替代，要么是前驱结点，左子树最大的那个值，或者是后继节点，右子树最小的那个值，这样放到中间就可以了。并且我们的前驱或者后继节点，他的度只能为1或者0，比如前驱结点，他的度不可能为2，因为是一直向右查找，如果度为2，那么必定还能继续查找，所以他的度只能为1只有左子树或者只能为0，如果是后继节点也一个道理，只不过相反。