05E2-2 慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

与设计算法解决很多问题的过程一样

我们首先要做的未必是动手

而是通过眼睛深入的观察

进而发现其中蕴含的规律

我们来考察这样一个具有一定的规模

同时也具有相当一般性的实例

首先请确认我们这里

在下方所注明的这个序列

确实就是这棵树的中序遍历序列

不同节点之间相继被访问的次序

在上面这个图中我们用虚线来表示

比如在e被访问之后紧接其后的是f

以及再随后的g以及h

直到i和j 诸如此类

那么我们问题的起点是

对于这样一种中序遍历

首先第一个接受访问的是哪一个节点呢？

没错就是a

那么接下来的第二个问题是

为什么是a呢？

为此我们需要回到这个遍历算法的

基本策略也就是左中右次序

在任何局部比如说整个全树的根节点

在根节点i的左子树也就是子树d

被完全遍历之前

i是不会首先接受访问的

所以我们可以理解为当算法扫描到

子树i的时候它将会将控制权

转交给它的左孩子d

同样地当节点d被扫描到后

它也会随即将控制权转交给它的左孩子

再同理 c被扫描到后

也会进而将控制权转交给它的左孩子

也就是a

实际上我们可以认为a

也试图效仿这种做法

将控制权转交给它的左孩子

然而正如我们所看到的

很遗憾它没有左孩子

请注意没有左孩子其实也等效于

左孩子以及左后代已经完全被访问过了

换而言之此时这个局部子树的树根

节点a 的确是轮到该访问的时候了

而正因为此从全局来看

a将首先第一个被访问

回顾在此前各层节点逐层谦让的过程

我们可以理解为控制权最开始在树根i

它进而转让给它的左孩子d

d再继续转让给它的左孩子c

c再转让给它的左孩子a

而a无从转让所以才轮到它自己接受访问

看出什么规律来了吗？

没错

与先序遍历非常类似

整个中序遍历过程的序曲总是一样的

也就是从根节点开始

一直沿着左侧分支逐层向下

直到末端不能再向下的那个节点

注意我们这里再一次

遇到了左侧分支 left branch

这个规律在任何局部都是成立的

除了刚才我们所说的全局树根i

其实对于其它的也是如此

我们不妨来看当控制权

试图转交给这个h的时候

它也依然会类似的谦让

将控制权转交给它的左孩子

以及左孩子的左孩子

如果还能左孩子下去的话

还将一直下去

可惜在e这个位置这种谦让必须停止

所以这也是为什么在节点d访问之后

控制权进入它的右子树之后

实质被访问的恰恰是节点e

我们看到了什么呢？

没错又是一个左侧链 left branch

站在这样一个角度你可以很自然地解释

为什么这也是一个左侧链

以及这个长度为1的左侧链

以及这个左侧链

站在这个视角我们可以将

整个中序遍历分解为

在不同尺度下的

一系列的对左侧分支的逐步处理

好了到了对这种观察的规律

做一个抽象和总结的时候了

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--（a）计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-（xd）：LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

05E2-2 在线视频

05E2-2 课程教案、知识点、字幕

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

05E2-2 笔记与讨论

也许你还感兴趣的课程: