、后序非递归遍历算法9思路都写在注释里面了。10遍历结果为:验证遍历结果知,遍历成功。2.3遍历算法总结其实,对于二叉排序树来说,中序遍历是一个从小到大的序列。二叉树的本质是递归定义的二叉链表,对树的操作往往离不开递归,递归形式上看起来简单明了,调用起来却是层层嵌套,而且递归调用要保存很多信息,这些信息也应该是用栈来保存的,另外,递归调用会占用较多的CPU资源,效率不高。于是,我们考虑使用非递归的形式来对树进行操作,而非递归的算法却不太好理解,可能对于我来说不确定的因素太多了吧,要自己想还真想不出来。一开始,算法也看不太懂,特别是后序非递归比较难,本身对c语言,对指针就不是特别理解,于是只能跟着程序来调试,并参考别人写的,慢慢的才理解。个人觉得后序非递归算法用双栈法比较高大上,因为不仅充分运用数据结构的栈,还能和先序非递归进行对比,简直是经典算法。另外,做这几个算法的时候也遇到了许多困难,感觉对指针怕怕的,还好后来经过同学间的讨论,以及丰富的网上资源把困难摆平了。3、每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。3.1打印二叉排序树二叉排序树要用树的形状打印出来。打印二叉排序树的函数思路如下:由于printf();函数会独占一行,就是打印换行后,就开启了新的一行,回不去原来那一行去了。所以,要竖向打印一棵树,必须用层次遍历法,一层一层的打印,打印一层换一行。层次遍历法主要用到了队列,就是先让根节点入队列,然后让根节点出队列,若根节点有左、或右孩子,则让左、右孩子依次入队列。在基于层次遍历法的基础上,最主要的就是要控制好两点:(1)遍历到该元素时,该空多少个空格位再打印它。(2)什么时候打印换行。对于(1):由于第一个打印的根节点我们可以先确定它的位置,比如放在第一行,空了32个空格位的位置。那如果它有左右孩子,它的左右孩子该空多少格呢?我的答案是空
全文预览
