以二叉链表作为二叉树的存储结构,编写二叉树中序遍历函数。
时间: 2024-08-12 09:10:05 浏览: 48
在计算机科学中,二叉链表是一种常见的二叉树存储结构,它将每个节点表示为一个包含两个指针的结构:一个指向左子节点,另一个指向右子节点。如果某个节点没有对应的子节点,它的指针则为NULL。这种结构方便了对二叉树的遍历操作。
二叉树的中序遍历是一种按照“左-根-右”的顺序访问节点的方法。对于二叉链表的中序遍历,我们通常使用递归或迭代的方式实现:
1. **递归实现**:
```cpp
void inorderTraversal(Node* root) {
if (root != nullptr) {
inorderTraversal(root->left); // 遍历左子树
cout << root->data << " "; // 访问当前节点
inorderTraversal(root->right); // 遍历右子树
}
}
```
2. **迭代实现(使用栈)**:
```cpp
void inorderTraversal(Node* root) {
stack<Node*> s;
Node* curr = root;
while (curr != nullptr || !s.empty()) {
while (curr != nullptr) {
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
cout << curr->data << " "; // 访问当前节点
curr = curr->right;
}
}
```
在这两种方法中,`Node`是一个代表二叉树节点的结构体或类,包含`data`(节点值)、`left`和`right`指针。
阅读全文