Skip to content

Latest commit

 

History

History
46 lines (20 loc) · 1.67 KB

11.3 树的遍历.md

File metadata and controls

46 lines (20 loc) · 1.67 KB

11.3 树的遍历

通用地址信息

这玩意很简单,就是可以采用下面的形式标记树中每个点的位置:

image-20210217165153703

就是类似上面这样的图一样。

前序遍历,后续遍历,后序遍历

参考B站视频

中缀,前缀和后缀记法

首先就是用二叉树来表示所需要进行的计算,比如式子:(x+y)*2+(x-4)/3可以用二叉树来表示:

image-20210217162419208

中缀记法

然后我们只需要对其进行中序遍历,就可以获得原来的式子了,但是为了跟原来的式子一致,我们还需要括号。

然后用这种方式获得的式子就是中缀记法。

前缀记法 / 波兰记法

在上面我们对上面的树采用中序遍历,这里改成前序遍历。这样得到的式子就是前缀记法。

根据这个式子进行计算时,我们必须要从右到左,如果遇到一个代表计算符号的字符,就计算该字符接下来的两个字符。比如当遇到/-x43时,从右到左,遇到-时,就计算x-4

后缀记法 / 逆波兰记法

模仿上面的前缀记法,就是采用前序遍历。

然后根据这个式子计算时,采用从左到右,如果遇到一个代表计算符号的字符,就采用该符号计算该字符的前2个字符,比如遇到xy+2+*时,从左到右,当遇到+时,就计算x+y