二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    right: {
      val: "F"
    }
  }
};

1.先序遍历

遍历的顺序是： 根节点 -> 左子树 ->右子树

图片
图片

1
2
3
4
5
6
7
8
9
10
11
12
function preorder(root) {
    // 递归边界，root 为空
    if(!root) return ;
    
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val);  
    // 递归遍历左子树 
    preorder(root.left);  
    // 递归遍历右子树  
    preorder(root.right);
}

解析

1.调用 preorder(root)，这里 root 就是 A，它非空，所以进入递归式，输出 A 值。接着优先遍历左子树，preorder(root.left) 此时为 preorder(B)；

  1. 进入 preorder(B)的逻辑： 入参为结点 B，非空，进入递归式，输出 B 值。接着优先遍历 B 的左子树，preorder(root.left) 此时为 preorder(D)；
  1. 进入 preorder(D)的逻辑： 入参为结点 D，非空，进入递归式，输出 D 值。接着优先遍历 D 的左子树，preorder(root.left) 此时为 preorder(null);
  1. 进入preorder(null)，发现抵达了递归边界，直接 return 掉。紧接着是 preorder(D)的逻辑往下走，走到了 preorder(root.right);
  1. 再次进入preorder(null)，发现抵达了递归边界，直接 return 掉，回到preorder(D)里。接着 preorder(D)的逻辑往下走，发现 preorder(D) 已经执行完了。于是返回，回到preorder(B)里，接着preorder(B)往下走，进入 preorder(root.right)，也就是 preorder(E),E 不为空，进入递归式，输出 E 值。接着优先遍历 E 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回 preorder(E)；继续preorder(E)执行下去，是preorder(root.right)，这里 E 的 right 同样是 null，故直接返回。如此一来，preorder(E)就执行完了，回到preorder(B)里去；发现preorder(B)也执行完了，于是回到preorder(A)里去，执行preorder(A)中的 preorder(root.right)。
  1. root 是A，root.right 就是C 了，进入preorder(C)的逻辑, C 不为空，进入递归式，输出 C 值。接着优先遍历 C 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回。继续preorder(C)执行下去，是preorder(root.right)，这里 C 的 right是 F;
  1. 进入preorder(F)的逻辑，F 不为空，进入递归式，输出 F 值。接着优先遍历 F 的左子树，preorder(root.left) 此时为 preorder(null)，触碰递归边界，直接返回 preorder(F)；继续preorder(F)执行下去，是preorder(root.right)，这里 F 的 right 同样是 null，故直接返回preorder(F)。此时preorder(F)已经执行完了，返回preorder(C)；发现preorder(C)也执行完了，就回到 preorder(A)；发现preorder(A)作为递归入口，它的逻辑也已经执行完了，于是我们的递归活动就正式画上了句号。到此为止，6个结点也已全部按照先序遍历顺序输出;
1
2
3
4
5
6
当前遍历的结点值是： A
当前遍历的结点值是： B
当前遍历的结点值是： D
当前遍历的结点值是： E
当前遍历的结点值是： C
当前遍历的结点值是： F

2.中序遍历

左子树 -> 根节点 -> 右子树

图片
图片

1
2
3
4
5
6
7
8
9
10
11
12

function inorder(root) {
    // 递归边界，root 为空
    if(!root) return;
    // 递归遍历左子树 
    inorder(root.left);  
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val);  
    // 递归遍历右子树  
    inorder(root.right);
}

按照中序遍历出来，同一颗二叉树，结点内容输出结果如下：

1
2
3
4
5
6
当前遍历的结点值是： D
当前遍历的结点值是： B
当前遍历的结点值是： E
当前遍历的结点值是： A
当前遍历的结点值是： C
当前遍历的结点值是： F

3.后序遍历

遍历的顺序是：左子树 -> 右子树 -> 根节点

图片
图片

1
2
3
4
5
6
7
8
9
10
11
function postorder(root) {
    // 递归边界，root 为空
    if(!root) return;
    // 递归遍历左子树 
    postorder(root.left);  
    // 递归遍历右子树  
    postorder(root.right);
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val); 
}

遍历结果：

1
2
3
4
5
6
7
8

当前遍历的结点值是： D
当前遍历的结点值是： E
当前遍历的结点值是： B
当前遍历的结点值是： F
当前遍历的结点值是： C
当前遍历的结点值是： A

政治发展的动力
政治发展动力的来源是人类对人类社会发展的不懈追求；
人是政治生活的主体，也是政治发展的推动力量，更是政治发展的服务对象；
政治发展的动力来源是阶级关系和阶级结构不断变化的推动；
政治发展的动力来源是政治结构自我完善，自我发展的要求；
政治发展的动力来源是人类社会的相互沟通，学习的影响；