408第一季 - 数据结构 - 树与二叉树II

二叉树的先中后序遍历

理解

 那主播，请问你有没有更快的遍历方式呢

有的，兄弟有的

以中序遍历为例啊

找左边有没有东西，左边没东西那它就自由了，就按上面的图举例子

A左边有东西，是B，B左边没东西，记下B

但B右边有东西，是C，C左边有没有东西，有东西，是E，E左边没东西了，记下BE

继续，C左边这下是真没东西了记下BEC

继续，C右边没东西就回溯到A了，这时A左边已经没东西了，记下BECA

但A右边有东西，是D，D左边有东西，是F，F左边没东西，记下BECAF

但F右边有东西，还不能回去，是H，H左边没东西，记下BECAFH

后面不说了，熟练就行 BECAFHDIGK

然后以 后序遍历为例

看看左边和右边有没有东西

A左边有东西啊，是B，B左边没东西但右边有东西啊，是C，C左边有东西，是E

终于，E左边没东西，右边也是，所以，记下E

回到C，左边的东西结束了，右边又没东西，记下EC

回到B，左边本来就没东西，右边的东西结束了，接下ECB

回到A，左边的东西结束了，右边还有很多呢，右边的东西是D，D左边有东西是F

F左边没东西，右边有H，H左边和右边都没东西，所以记下ECBH

后面不多说了，ECBHFIKGDA

再看看 最后的先序遍历啊

先根再看看左边右边有没有东西

先根！记下A，然后左边有东西，是B，记下AB，然后左边没东西，右边有东西，是C，记下ABC

C的左边有东西，是E，记下ABCE，然后E的左边和右边结束，回到C的左边处理完了，右边没东西结束,回到B也一样

回到A，左边处理完了，处理右边，懒的说了

ABCEDFHGIK，先序应该是最简单的

做题

1

给我用我的方法想出来 

b

2

也是啊，不会就反复抄写，熟稔于心，倒背如流

a 

由遍历序列构造二叉树

 

 做题

1

 

d 

2

 

a

3

 

b

4

前序和后序不能唯一确定二叉树

用选项里的中序构造，发现C有问题

它是3421，所以选c

小问题！

什么时候先序和后序是相反的

先序是根左右，后序是左右根

删个左就是 先序是根右，后序是右根

删个右就是 先序是根左，后序是左根

所以一层只有一个，随便画，就是相反的

那有多少种画法呢

4层的画，就只有2*4=8种

5

 

左删掉，都只剩根右了，那他们就是相同的，所以只要右子树

线索二叉树

理解

这里的空链域会有 2n - （n - 1) = n+1个，这里n-1是边的个数

然后就可以发现太浪费了，很不爽

线索二叉树也是分先中后序的

这里就写中序遍历的线索二叉树

然后这里，比如6这里,左边是2，右边是4

就这样连上去就行了

然后这样就行了，但还是有空的，哎

做题

1

d左边缺东西，所以是NULL

d

2

debxac

d

3

画个图bro 

    a

Y      X

a