二叉树的递归与非递归遍历实现 二叉树是一种常用的数据结构,在计算机科学中应用非常广泛。二叉树的遍历是指从根节点开始访问每个节点的过程,常用的遍历方法有前序遍历、中序遍历和后序遍历。在IT面试中,二叉树的遍历问题经常被问到,因此,掌握二叉树的递归和非递归遍历实现非常重要。 一、递归遍历 递归遍历是指使用函数递归调用自身来遍历二叉树的每个节点。递归遍历的优点是实现简单、易于理解,但缺点是可能会出现堆栈溢出错误。 1. 前序遍历 前序遍历是指先访问根节点,然后访问左子树和右子树。递归实现前序遍历的代码如下所示: ```c void pre_order_traversal(tree_item *root) { if (root == NULL) return; printf("[%d]", root->data); pre_order_traversal(root->left); pre_order_traversal(root->right); } ``` 2. 中序遍历 中序遍历是指先访问左子树,然后访问根节点,最后访问右子树。递归实现中序遍历的代码如下所示: ```c void in_order_traversal(tree_item *root) { if (root == NULL) return; in_order_traversal(root->left); printf("[%d]", root->data); in_order_traversal(root->right); } ``` 3. 后序遍历 后序遍历是指先访问左子树和右子树,然后访问根节点。递归实现后序遍历的代码如下所示: ```c void post_order_traversal(tree_item *root) { if (root == NULL) return; post_order_traversal(root->left); post_order_traversal(root->right); printf("[%d]", root->data); } ``` 二、非递归遍历 非递归遍历是指使用栈或队列来遍历二叉树的每个节点。非递归遍历的优点是不会出现堆栈溢出错误,但缺点是实现较为复杂。 1. 前序遍历 非递归实现前序遍历的代码如下所示: ```c void pre_order_traversal_non_recursive(tree_item *root) { stack<tree_item*> stack; stack.push(root); while (!stack.empty()) { tree_item *node = stack.top(); stack.pop(); printf("[%d]", node->data); if (node->right) stack.push(node->right); if (node->left) stack.push(node->left); } } ``` 2. 中序遍历 非递归实现中序遍历的代码如下所示: ```c void in_order_traversal_non_recursive(tree_item *root) { stack<tree_item*> stack; tree_item *node = root; while (node || !stack.empty()) { while (node) { stack.push(node); node = node->left; } node = stack.top(); stack.pop(); printf("[%d]", node->data); node = node->right; } } ``` 3. 后序遍历 非递归实现后序遍历的代码如下所示: ```c void post_order_traversal_non_recursive(tree_item *root) { stack<tree_item*> stack1, stack2; stack1.push(root); while (!stack1.empty()) { tree_item *node = stack1.top(); stack1.pop(); stack2.push(node); if (node->left) stack1.push(node->left); if (node->right) stack1.push(node->right); } while (!stack2.empty()) { tree_item *node = stack2.top(); stack2.pop(); printf("[%d]", node->data); } } ``` 二叉树的递归和非递归遍历实现都是非常重要的知识点,在IT面试中经常被问到。掌握这些知识点可以帮助你更好地应对二叉树相关的问题。