C++ 二叉树中序遍历（递归与迭代）实现

#include #include using namespace std;

struct TNode { int data; TNode *Lsubtree; TNode *Rsubtree; };

void Access(int data) { cout << data << ' '; }

// 递归实现中序遍历 void InOrder(TNode *tree) { if (tree != NULL) { InOrder(tree->Lsubtree); Access(tree->data); InOrder(tree->Rsubtree); } }

// 迭代实现中序遍历 void InOrder2(TNode *tree) { TNode p = tree; stack<TNode> S; do { while (p != NULL) { S.push(p); p = p->Lsubtree; } if (!S.empty()) { p = S.top(); S.pop(); Access(p->data); p = p->Rsubtree; } } while (!S.empty() || p != NULL); }

int main() { TNode *tree = new TNode; // 输入树的根节点数据 cout << "请输入根节点数据："; cin >> tree->data;

// 创建左子树
tree->Lsubtree = new TNode;
cout << "请输入左子树数据：";
cin >> tree->Lsubtree->data;
// 创建左子树的左子树
tree->Lsubtree->Lsubtree = new TNode;
cout << "请输入左子树的左子树数据：";
cin >> tree->Lsubtree->Lsubtree->data;
tree->Lsubtree->Lsubtree->Lsubtree = NULL;
tree->Lsubtree->Lsubtree->Rsubtree = NULL;
// 创建左子树的右子树
tree->Lsubtree->Rsubtree = new TNode;
cout << "请输入左子树的右子树数据：";
cin >> tree->Lsubtree->Rsubtree->data;
tree->Lsubtree->Rsubtree->Lsubtree = NULL;
tree->Lsubtree->Rsubtree->Rsubtree = NULL;

// 创建右子树
tree->Rsubtree = new TNode;
cout << "请输入右子树数据：";
cin >> tree->Rsubtree->data;
// 创建右子树的左子树
tree->Rsubtree->Lsubtree = new TNode;
cout << "请输入右子树的左子树数据：";
cin >> tree->Rsubtree->Lsubtree->data;
tree->Rsubtree->Lsubtree->Lsubtree = NULL;
tree->Rsubtree->Lsubtree->Rsubtree = NULL;
// 创建右子树的右子树
tree->Rsubtree->Rsubtree = new TNode;
cout << "请输入右子树的右子树数据：";
cin >> tree->Rsubtree->Rsubtree->data;
tree->Rsubtree->Rsubtree->Lsubtree = NULL;
tree->Rsubtree->Rsubtree->Rsubtree = NULL;

cout << "InOrder traversal (recursion): ";
InOrder(tree);
cout << endl;

cout << "InOrder traversal (iteration): ";
InOrder2(tree);
cout << endl;

return 0;

}