二叉树中序遍历非递归+递归C++实现

非递归版本：
 

#include<iostream>
#include<stack>
using namespace std;
struct TreeNode {int _val;TreeNode* left, * right;TreeNode(const int& val) :_val(val), left(nullptr), right(nullptr) {}~TreeNode() {delete left, right;}
};
void inorderTraversal(TreeNode* root) {TreeNode* cur = root;stack<TreeNode*> st;while (cur || !st.empty()) {while (cur) {st.push(cur);cur = cur->left;}cur = st.top();st.pop();cout << cur->_val << " ";cur = cur->right;}
}
int main() {// 用例1：简单的二叉搜索树TreeNode* root1 = new TreeNode(5);root1->left = new TreeNode(3);root1->right = new TreeNode(7);root1->left->left = new TreeNode(2);root1->left->right = new TreeNode(4);root1->right->left = new TreeNode(6);root1->right->right = new TreeNode(8);cout << "Inorder traversal of BST: ";inorderTraversal(root1);cout << endl;// 用例2：只有一个节点的树TreeNode* root2 = new TreeNode(10);cout << "Inorder traversal of single node tree: ";inorderTraversal(root2);cout << endl;// 用例3：空树TreeNode* root3 = nullptr;cout << "Inorder traversal of empty tree: ";inorderTraversal(root3);cout << endl;// 用例4：不平衡的树TreeNode* root4 = new TreeNode(1);root4->left = new TreeNode(2);root4->left->left = new TreeNode(3);root4->left->left->left = new TreeNode(4);cout << "Inorder traversal of unbalanced tree: ";inorderTraversal(root4);cout << endl;// 用例5：退化成链表的树TreeNode* root5 = new TreeNode(1);TreeNode* cur = root5;for (int i = 2; i <= 5; ++i) {cur->right = new TreeNode(i);cur = cur->right;}cout << "Inorder traversal of linked list tree: ";inorderTraversal(root5);cout << endl;// 释放所有节点的内存delete root1;delete root2;delete root3; // 虽然是空指针，但delete空指针是安全的delete root4;delete root5;return 0;
}

值得注意的点：

1.stack中存放的是树的节点的地址也就是TreeNode*类型。

2. TreeNode的析构函数千万不要忘记，因为我们是在堆上申请的内存。

3.delete空指针什么都不做。

下面我们实现递归版本，这个要容易地多。

#include<iostream>
#include<stack>
using namespace std;
struct TreeNode {int _val;TreeNode* left, * right;TreeNode(const int& val) :_val(val), left(nullptr), right(nullptr) {}~TreeNode() {delete left, right;}
};
void inorderTraversal(TreeNode* root) {if (root == nullptr)return;inorderTraversal(root->left);cout << root->_val << " ";inorderTraversal(root->right);    
}
int main() {// 用例1：简单的二叉搜索树TreeNode* root1 = new TreeNode(5);root1->left = new TreeNode(3);root1->right = new TreeNode(7);root1->left->left = new TreeNode(2);root1->left->right = new TreeNode(4);root1->right->left = new TreeNode(6);root1->right->right = new TreeNode(8);cout << "Inorder traversal of BST: ";inorderTraversal(root1);cout << endl;// 用例2：只有一个节点的树TreeNode* root2 = new TreeNode(10);cout << "Inorder traversal of single node tree: ";inorderTraversal(root2);cout << endl;// 用例3：空树TreeNode* root3 = nullptr;cout << "Inorder traversal of empty tree: ";inorderTraversal(root3);cout << endl;// 用例4：不平衡的树TreeNode* root4 = new TreeNode(1);root4->left = new TreeNode(2);root4->left->left = new TreeNode(3);root4->left->left->left = new TreeNode(4);cout << "Inorder traversal of unbalanced tree: ";inorderTraversal(root4);cout << endl;// 用例5：退化成链表的树TreeNode* root5 = new TreeNode(1);TreeNode* cur = root5;for (int i = 2; i <= 5; ++i) {cur->right = new TreeNode(i);cur = cur->right;}cout << "Inorder traversal of linked list tree: ";inorderTraversal(root5);cout << endl;// 释放所有节点的内存delete root1;delete root2;delete root3; // 虽然是空指针，但delete空指针是安全的delete root4;delete root5;return 0;
}