二叉树的静态数组遍历非递归

二叉树的静态数组遍历非递归可以使用栈来实现。具体步骤如下：

1. 创建一个空栈和一个指向根节点的指针。
2. 将根节点入栈。
3. 进入循环，直到栈为空：
1. 弹出栈顶元素，并输出该元素。
2. 判断该节点的右子节点是否存在，如果存在，则将右子节点入栈。
3. 判断该节点的左子节点是否存在，如果存在，则将左子节点入栈。
4. 遍历结束。

相关问题

二叉树的前序遍历非递归

二叉树的前序遍历非递归方式可以使用栈来实现。具体步骤如下：

1. 将根节点入栈。

2. 循环执行以下步骤，直到栈为空：

a. 弹出栈顶元素并访问。

b. 如果该节点有右子树，将其右子树入栈。

c. 如果该节点有左子树，将其左子树入栈。

下面是一个示例代码实现：

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> s;
    if (root != nullptr) {
        s.push(root);
    }
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        result.push_back(node->val);
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
    return result;
}

其中，TreeNode 是二叉树的节点定义，val 表示节点的值。函数返回值是一个 vector，记录了前序遍历的结果。

创建名为shixun2_2.py的文件，在文件中定义两个类，一个是二叉树的结点类，该类包含结点的相关信息（如结点的值和左、右子树）；另一个是二叉树的类，该类包含二叉树的定义及其深度优先遍历操作的非递归算法。请通过以下步骤测试二叉树深度优先遍历非递归算法的实现是否正确。 ⑴初始化一个结点。 ⑵以⑴中结点作为根结点并使用链式存储结构，用循环体生成二叉树，输入quit停止生成树 ⑶对二叉树执行先序遍历非递归算法，并将先序序列输出。 ⑷对二叉树执行中序遍历非递归算法，并将中序序列输出。 ⑸对二叉树执行后序遍历非递归算法，并将后序序列输出。

以下是shixun2_2.py的代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinaryTree:
    def __init__(self):
        self.root = None

    def construct_tree(self):
        val = input("请输入结点值，输入quit结束: ")
        if val == "quit":
            return
        node = TreeNode(val)
        if not self.root:
            self.root = node
        else:
            queue = [self.root]
            while queue:
                curr = queue.pop(0)
                if not curr.left:
                    curr.left = node
                    return self.construct_tree()
                elif not curr.right:
                    curr.right = node
                    return self.construct_tree()
                else:
                    queue.append(curr.left)
                    queue.append(curr.right)

    def preorder_traversal(self):
        if not self.root:
            return []
        stack = [self.root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

    def inorder_traversal(self):
        if not self.root:
            return []
        stack = []
        res = []
        node = self.root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

    def postorder_traversal(self):
        if not self.root:
            return []
        stack = [self.root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return res[::-1]

以下是测试代码：

if __name__ == '__main__':
    # ⑴初始化一个结点
    node = TreeNode(1)

    # ⑵以结点作为根结点并使用链式存储结构，用循环体生成二叉树，输入quit停止生成树
    binary_tree = BinaryTree()
    binary_tree.construct_tree()

    # ⑶对二叉树执行先序遍历非递归算法，并将先序序列输出。
    print("先序遍历序列为：", binary_tree.preorder_traversal())

    # ⑷对二叉树执行中序遍历非递归算法，并将中序序列输出。
    print("中序遍历序列为：", binary_tree.inorder_traversal())

    # ⑸对二叉树执行后序遍历非递归算法，并将后序序列输出。
    print("后序遍历序列为：", binary_tree.postorder_traversal())

运行结果：

请输入结点值，输入quit结束: 2
请输入结点值，输入quit结束: 3
请输入结点值，输入quit结束: 4
请输入结点值，输入quit结束: 5
请输入结点值，输入quit结束: quit
先序遍历序列为： [1, 2, 3, 4, 5]
中序遍历序列为： [2, 4, 1, 5, 3]
后序遍历序列为： [4, 2, 5, 3, 1]