翻译资格考试

导航

中序遍历二叉树非递归算法

来源 :华课网校 2024-09-08 02:21:12

中序遍历是二叉树遍历的一种方式,顺序是先遍历左子树,再遍历根节点,最后遍历右子树。中序遍历可以用递归算法实现,但是也可以用非递归算法实现。

非递归算法的基本思路是利用栈来模拟递归过程。具体实现步骤如下:

1. 初始化栈,并将根节点入栈。

2. 当栈不为空时,执行以下操作:

a. 将栈顶元素出栈,并将其值输出;

b. 如果该节点有右子节点,则将右子节点入栈;

c. 如果该节点有左子节点,则将左子节点入栈;

3. 重复步骤2,直到栈为空。

这个算法的时间复杂度为O(n),空间复杂度为O(h),其中n为二叉树节点数,h为树的高度。

下面是一个示例代码:

```

void inorderTraversal(TreeNode* root) {

stack s;

TreeNode* curr = root;

while (curr != NULL || !s.empty()) {

if (curr != NULL) {

s.push(curr);

curr = curr->left;

} else {

curr = s.top();

s.pop();

cout << curr->val << ' ';

curr = curr->right;

}

}

}

```

这段代码首先初始化一个栈和一个指向根节点的指针curr。在while循环中,如果curr不为空,则将curr入栈,并将curr指向左子节点。如果curr为空,则从栈顶取出一个节点,并输出其值,然后将curr指向该节点的右子节点。重复执行这个过程,直到栈为空。

总之,中序遍历二叉树的非递归算法是通过栈来模拟递归过程,实现了遍历二叉树的目的。

分享到

您可能感兴趣的文章

相关推荐

热门阅读

最新文章