|
#include <iostream>
#include <stack>
using namespace std;
typedef struct treeNode_t
{
? ? int value;
? ? struct treeNode_t *plchild;
? ? struct treeNode_t *prchild;
? ??
? ? treeNode_t(int v, struct treeNode_t *pl, struct treeNode_t *pr)
? ? {
? ? ? ? value = v;
? ? ? ? plchild = pl;
? ? ? ? prchild = pr;
? ? }
}treeNode;
//递归遍历
void postOrder1(treeNode *root)
{
? ? if (nullptr == root)
? ? {
? ? ? ? return;
? ? }
? ??
? ? postOrder1(root->plchild);
? ? postOrder1(root->prchild);
? ? cout << root->value << endl;
}
//迭代遍历
void postOrder2(treeNode *root)
{
? ? if (nullptr == root)
? ? {
? ? ? ? return;
? ? }
? ??
? ? stack<treeNode *> s;
? ? treeNode *printNode = nullptr;
? ??
? ? while(!s.empty() || root != nullptr)
? ? {
? ? ? ? if (root != nullptr)
? ? ? ? {
? ? ? ? ? ? s.push(root);
? ? ? ? ? ? root = root->plchild;
? ? ? ? }
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? treeNode *tmp = s.top();
? ? ? ? ? ? s.pop();
? ? ? ? ? ? if (nullptr == tmp->prchild || printNode == tmp->prchild)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? cout << tmp->value << endl;
? ? ? ? ? ? ? ? printNode = tmp;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s.push(tmp);
? ? ? ? ? ? ? ? root = tmp->prchild;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ??
}
int main() {
? ? treeNode *node11 = new treeNode(11, nullptr, nullptr);
? ? treeNode *node10 = new treeNode(10, nullptr, nullptr);
? ? treeNode *node9 = new treeNode(9, nullptr, nullptr);
? ? treeNode *node8 = new treeNode(8, node10, node11);
? ? treeNode *node7 = new treeNode(7, nullptr, nullptr);
? ? treeNode *node6 = new treeNode(6, node9, nullptr);
? ? treeNode *node5 = new treeNode(5, node8, nullptr);
? ? treeNode *node4 = new treeNode(4, nullptr, nullptr);
? ? treeNode *node3 = new treeNode(3, node6, node7);
? ? treeNode *node2 = new treeNode(2, node4, node5);
? ? treeNode *node1 = new treeNode(1, node2, node3);
? ??
? ??
? ? cout << "postOrder1:" << endl;
? ? postOrder1(node1);
? ??
? ? cout << "postOrder2:" << endl;
? ? postOrder2(node1);
? ??
? ??
? ? return 0;
}
?
|