[已解决]求助如何将二叉树递规改用循环来实现最简单的代码

zxczxc5484

前面发了个帖子，但基础太差，入栈我直接用数组来替代的，测试代码只能实现一层，没能达到递规的效果；能不能用数组代替出入栈？谢谢大佬们，谢谢师兄师姐们，请尽量为小师弟写得详细些或者动动小手指为小师弟写一下，以供参考研究思路！！！

原代码易语言：
.子程序 二叉树遍历
.参数 首地址, 整数型
.参数 结束标志, 整数型
.参数 次数, 整数型
.参数 对象数组, 整数型, 参考 数组
.参数 进程句柄, 整数型
.局部变量 L, 整数型
.局部变量 R, 整数型
.局部变量 x, 整数型

.如果真 (首地址 ≤ 0)
    返回 ()
.如果真结束
.如果真 (次数 ＞ 100)
    返回 ()
.如果真结束
次数 ＝ 次数 ＋ 1
x ＝ 内存_读整数型 (进程句柄, 首地址 ＋ 16)
加入成员 (对象数组, x)
L ＝ 内存_读整数型 (进程句柄, 首地址)
R ＝ 内存_读整数型 (进程句柄, 首地址 ＋ 8)
.如果真 (L ≠ 结束标志)
    二叉树遍历 (L, 结束标志, 次数, 对象数组, 进程句柄)
.如果真结束
.如果真 (R ≠ 结束标志)
    二叉树遍历 (R, 结束标志, 次数, 对象数组, 进程句柄)
.如果真结束

改的代码其它编程工具写的：
功能 循环实现二叉树(首地址, 结束标志, 次数, &对象数组, 下标)
    变量 栈位 = 0, 当前节点, 对象, 左子节点, 右子节点, 新建数组 = 数组()
    新建数组[栈位] = 首地址
    循环(栈位 < 次数)
        当前节点 = 新建数组[栈位]
        //                如果(当前节点 <= 0)
        //                    继续
        //                结束
        对象 = 内存读整数(十进制转十六进制(当前节点 + 16), 下标)
        数组追加元素(对象数组, 对象)
        左子节点 = 内存读整数(十进制转十六进制(当前节点), 下标)
        右子节点 = 内存读整数(十进制转十六进制(当前节点 + 8), 下标)
        调试输出("L = " & 左子节点)
        调试输出("R = " & 右子节点)
        如果(左子节点 <= 0 && 右子节点 <= 0)
            调试输出("完成")
            返回
        结束
        如果(左子节点 != 结束标志)
            栈位++
            新建数组[栈位] = 左子节点
        否则如果(右子节点 != 结束标志)
            栈位++
            新建数组[栈位] = 右子节点
        否则
            调试输出("完成")
            返回
        结束
    结束
结束

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-5-11 17:50:41

zxczxc5484 发表于 2023-5-11 17:58
先谢谢，还得研究下

可以记得给我最佳答案

跳转到最佳答案楼层

sfqxx

zxczxc5484 发表于 2023-5-11 17:58
先谢谢，还得研究下

可以记得给我最佳答案

isdkz

可以使用队列来代替递归实现二叉树的遍历。

具体实现步骤如下：

1. 新建一个队列，将根节点入队。

2. 循环遍历队列，直到队列为空。

3. 在循环中，依次取出队头元素，将其左右子节点入队。

4. 对每个取出的节点进行相应操作，如输出节点值或将节点值存入数组中。

代码示例：

1. def traverse(root):
2.     if not root:
3.         return
4.     queue = []
5.     queue.append(root)
6.     while queue:
7.         node = queue.pop(0)
8.         # 对节点进行操作，如输出节点值
9.         print(node.val)
10.         if node.left:
11.             queue.append(node.left)
12.         if node.right:
13.             queue.append(node.right)

复制代码

其中，root为二叉树的根节点，node为当前取出的节点，node.val为节点的值。如果要将节点值存入数组中，可以使用列表代替队列，并将节点值追加到列表中。

sfqxx

这段代码是一个非递归实现的二叉树遍历算法，其中用到了数组来模拟栈结构。但是，这段代码也有一些问题，在语法和逻辑上都需要进行修改和优化。下面是改进后的Python版本的代码：

1. 
   
2. def traverse_tree(addr, end_flag, max_size, obj_list):
   
3.     stack = [addr]  # 初始状态下向栈中添加根节点
   
4.     count = 0  # 已遍历节点数量
   
5.     while stack:
   
6.         current_node = stack.pop()
   
7.         if current_node <= 0:  # 如果当前节点为无效节点，则继续遍历下一个节点
   
8.             continue
   
9.         obj = read_mem_as_integer(hex(current_node + 16))  # 读取节点的数据对象
   
10.         obj_list.append(obj)  # 将对象添加到列表中
    
11.         left_node = read_mem_as_integer(hex(current_node))  # 读取当前节点的左孩子节点地址
    
12.         right_node = read_mem_as_integer(hex(current_node + 8))  # 读取当前节点的右孩子节点地址
    
13.         if left_node == end_flag and right_node == end_flag:  # 若该节点为叶子节点，则遍历完毕并返回
    
14.             return
    
15.         if left_node != end_flag:  # 否则将其左孩子节点入栈
    
16.             stack.append(left_node)
    
17.         if right_node != end_flag:  # 再将其右孩子节点入栈
    
18.             stack.append(right_node)
    
19.         count += 1
    
20.         if count >= max_size:  # 遍历节点数量达到指定阈值时停止遍历
    
21.             return

复制代码

可以看到，这段代码中的数组已经改为了Python的列表结构，而一些易语言特有的函数也做了相应的处理。同时，该代码还添加了一个调用`read_mem_as_integer()`方法的函数来读取内存数据。
有用请设置最佳答案

zxczxc5484

isdkz 发表于 2023-5-11 17:51
可以使用队列来代替递归实现二叉树的遍历。

具体实现步骤如下：

先谢谢，还得研究下

zxczxc5484

sfqxx 发表于 2023-5-11 17:53
这段代码是一个非递归实现的二叉树遍历算法，其中用到了数组来模拟栈结构。但是，这段代码也有一些问题，在 ...

先谢谢，还得研究下

歌者文明清理员

sfqxx 发表于 2023-5-11 18:01
可以记得给我最佳答案

祝不给sfqxx最佳答案的人一律身体健康，万事如意，心想事成,编程永无bug！考试一切顺利

sfqxx

歌者文明清理员 发表于 2023-5-11 18:02
祝不给sfqxx最佳答案的人一律身体健康，万事如意，心想事成,编程永无bug！考试一切顺利

反话

歌者文明清理员

sfqxx 发表于 2023-5-11 18:03
反话

我现在改改签名~