前言
已经知道了数据结构中的线性结构，那有没有非线性结构呢？
当然有就像我们文件夹，一个文件夹中有有另一个文件夹，这就是的 非线性的结构，就是本篇所讲的 二叉树
树的概念
树是一种非线性结构，是由n个节点构成的并且具有层次的，因为这就像一颗倒立的树
1.有一个特殊的节点就是根结点，这个结点是没有前驱的，也就是它是第一层
2.后面的结点有且只有一个前驱，可以有0个或多个后继
3.子树之间不可以有连续否则不是树形结构
4.一棵树中如果有N个节点，就有N-1条边
1.结点的度：就是这个结点所含子树节点的个数，例如：这里的A有6个子结点，所以A的度为6
2.树的度：就是所有结点度中的最大值，上图中树的度为6
3.叶子结点或终端结点：就是结点的度为0的结点，上图中B C D H N O等等
4.双亲结点或⽗结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点，如上图：A是B的⽗结点
5.孩⼦结点或⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结，；如上图：B是A的⼦结点
6.根结点：⼀棵树中，没有双亲结点的结点；如上图：A
7.结点的层次：从根开始定义起，根为第1层，根的⼦结点为第2层，以此类推，上图中A是根结点，所以A是第一层
8.树的⾼度或深度：结点层次中的最大值，也就是该树最后一层是多少层；如上图：树的⾼度为4
9.⾮终端结点或分⽀结点：度不为0的结点；如上图：D、E、F、G…等节点为分⽀结点
10.兄弟结点：具有相同⽗结点的结点互称为兄弟结点；如上图：B、C是兄弟结点
11.堂兄弟结点：双亲在同⼀层的结点互为堂兄弟；如上图：H、I互为兄弟结点
12.结点的祖先：从根到该结点所经分⽀上的所有结点；如上图：A是所有结点的祖先
13.⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
14.森林：由m（m>=0）棵互不相交的树组成的集合称为森林
二叉树
树这种数据结构使用最多的是二叉树
二叉树：结点的有序集合，该集合为空，也可以是左子树和右子树组成的二叉树
二叉树根节点的度是<=2的,一个完整的二叉树就是由许多小的二叉树组成的
满二叉树和完全二叉树
两种特殊的二叉树：满二叉树和完全二叉树
满二叉树：每层节点数都是达到最大值就是满二叉树，就是如果由k行的话，就由2^k - 1个总节点
完全二叉树：就是除了最后一层没有满，上面几层是满足满二叉树的性质，但是最哟一层要按照从左向右进行编号，就是对深度为h，结点数为n个的二叉树进行编号后，各结点的编号与深度为h的满二叉树中相同位置结点上对应的编号均相同时，则这种二叉树为完全二叉树
如果没有按照从上到下，从左到右进行编号，不可以直接跳过进行编号，这样就不是完全二叉树了
二叉树的性质
1.若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)(i>0)个结点
2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的总结的最多是2^k - 1(k>=0)
3. 对任何⼀棵⼆叉树如果其叶结点个数为n0,度为2的⾮叶结点个数为n2,则有n0＝n2＋1
4. 具有n个结点的完全⼆叉树的深度k为上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点◦
若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦
6.完全二叉树中假设总共有N个节点，有n0个叶子节点，那二者关系呢
若N是偶数，则 n0 = N/2
若N是奇数，则 n0 = (N+1) / 2
1.若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)(i>0)个结点
2.若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的总结的最多是2^k - 1(k>=0)
3. 对任何⼀棵⼆叉树如果其叶结点个数为n0,度为2的⾮叶结点个数为n2,则有n0＝n2＋1
4.具有n个结点的完全⼆叉树的深度k为上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦
> 6.完全二叉树中假设总共有N个节点，有n0个叶子节点，那二者关系呢
> 若N是偶数，则 n0 = N/2
> 若N是奇数，则 n0 = (N+1) / 2
题目练习
1 某⼆叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该⼆叉树中的叶⼦结点数为（B ）
A 不存在这样的⼆叉树
B 200
C 198
D 199
性质3 叶子节点就是度为0的节点,上面已经知道一个公式就是在二叉树中 n0 = n2 + 1 = 200
2.⼀棵完全⼆叉树的节点数为531个，那么这棵树的⾼度为（B）
A 11
B 10
C 8
D 12
由性质4可知 节点总数N,高度为K , k = log(N+1) 底数为2
这里2^9 = 512 , 2的10次幂为1024，向上取整所以这里高度为10
3.在具有 2n 个结点的完全⼆叉树中，叶⼦结点个数为（ A）
A n
B n+1
C n-1
D n/2
4.⼀个具有767个节点的完全⼆叉树，其叶⼦节点个数为（B）
A 383
B 384
C 385
D 386
性质6当有N个节点时候如果，N为偶数 n0 = N / 2,如果为奇数的话 n = (N+1) / 2
所以这里第二题肯定为偶数个节点，所以叶子节点为 n
第三题是奇数个节点，所以叶子节点为 768 / 2 = 384
二叉树的遍历
前序遍历：根 -> 左子树 -> 右子树
中序遍历：左子树 -> 根 -> 右子树
后序遍历：左子树 -> 右子树 -> 根
层序遍历：就是从上到下，从左向右遍历
注意在遍历的时候，每个左子树和右子树分别可以看成一个完整的树按照规则进行遍历，因此要层层瓦解进行遍历
题目练习
1.某完全⼆叉树按层次输出（同⼀层从左到右）的序列为 ABCDEFGH 。该完全⼆叉树的前序序列为(A)
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
2.⼆叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则⼆叉树根结点为(A)
A: E B: F C: G D: H
这里知道先序遍历第一个遍历的是根，所以说根节点为E
3.设⼀课⼆叉树的中序遍历序列：badce，后序遍历序列：bdeca，则⼆叉树前序遍历序列为(D)
A: adbce B: decab C: debac D: abcde
4.某⼆叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出(同⼀层从左到右)的序列为(A)
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
加粗样式
题目练习
前序遍历
目的：将一棵二叉树，前序遍历放入链表中
思路：使用stack来完成，这里要进行循环，前序遍历是根，左子树，右子树这样的顺序，因此要先将root根放入链表中，在将左子树放入链表，最后是右子树，但要注意每一棵树的左子树和右子树又分别是一棵完整的树
当栈为空，或者cur == null结束循环
//非递归方法
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (!stack.isEmpty() || cur != null) {
//cur不为空，说明左子树没有遍历完
if(cur != null){
list.add(cur.val);//放入链表中
stack.push(cur);
cur = cur.left;//一直到左树为空
}else{
//开始右树
cur = stack.pop();
cur = cur.right;
}
}
return list;
}
}
因为左子树和右子树又可以看成一棵完整的二叉树，因此可以使用递归来写
//递归方法
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
return preorder(root, list);
}
public List<Integer> preorder(TreeNode root, List<Integer> list) {
if (root == null) {
return null;
}
//根-》左子树-》右子树
list.add(root.val);
preorder(root.left, list);
preorder(root.right, list);
return list;
}
}
中序遍历
目的：就是将一棵树中序遍历结果放入一个链表中
思路：和前序遍历思路一样，就是使用栈来操作，但是这里不同的是链表添加元素的时候，因为中序遍历是 左子树 -》根-》右子树
所以循环，如果cur != null，就一直将左节点入栈
为空的时候，说明左子树搞完了，这时候就要将这个节点添加的链表中
再开始右子树
//非递归
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur!=null||!stack.isEmpty()){
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
当然也可以使用递归来写
这里要先递归左子树，再将节点的值放入链表中，最后递归右子树
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
return inorder(root,list);
}
public List<Integer> inorder(TreeNode root,List<Integer> list){
if(root == null){
return null;
}
inorder(root.left,list);
list.add(root.val);
inorder(root.right,list);
return list;
}
}
后序遍历
目的：就是将二叉树后序遍历的结果放入一个链表中
思路：后序遍历：左子树-》右子树-》根
但是这里将其放入链表中与其不一样
cur：遍历整棵树
prev：记录上一个出栈元素
top：记录栈顶元素
因为这里使最后才放入根，因此再放入链表元素时候，这时候左子树已经遍历完了，当右子树为空，或者右子树已经入链表了，这时候就可以将这个根节点放入链表中了
top.right==null或者top.right == prev
//非递归
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;//指向上一个出栈元素
TreeNode top = null;//指向栈顶元素
while(cur!=null||!stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur = cur.left;
}
top = stack.peek();
//入链表
if(top.right == null || top.right == prev){
//出栈
stack.pop();
list.add(top.val);
prev = top;//记录出栈元素
}else{
cur = top.right;
}
}
return list;
}
}
//非递归
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
return postorder(root,list);
}
public List<Integer> postorder(TreeNode root,List<Integer> list){
if(root == null){
return null;
}
postorder(root.left,list);
postorder(root.right,list);
list.add(root.val);
return list;
}
}