두 갈래 나무의 비귀속 역력(귀속 사상을 참고하여 비귀속 역력을 실현)

1 //  

2 typedef struct TNode

3 {

4     int value;

5     TNode *left;

6     TNode *right;

7 }*PTNode;

 1 void preOrderNoneRecursion(PTNode root)

 2 {

 3     if(root == NULL)

 4     　　return;

 5     PTNode p = root;

 6     stack<PTNode> nodeStack;

 7     nodeStack.push(p);

 8     while(!nodeStack.empty())

 9     {

10     　　p = nodeStack.top();

11     　　nodeStack.pop();

12     　　cout << p->value;

13     　　if(p->right != NULL)

14     　　　　nodeStack.push(p->right);

15     　　if(p->left != NULL)

16     　　　　nodeStack.push(p->left);

17     }

18 }            

 1 void postOrderNoneRecursion(PTNode root)

 2 {

 3     if(root == NULL)

 4     　　return;

 5     PTNode p = root;

 6     PTNode pre = NULL;

 7     stack<PTNode> nodeStack;

 8     nodeStack.push(p);

 9     while(!nodeStack.empty())

10     {

11     　　p = nodeStack.top()

12         

13     　　if( (p->left == NULL && p->right == NULL) 

14         　　|| ((pre! == NULL) && (pre == p->left || pre == p->right))

15     　　{

16         　　cout << p->value;

17         　　nodeStack.pop();

18         　　pre = p;

19     　　}

20     　　else

21     　　{

22         　　if(p->right != NULL)

23         　　　　nodeStack.push(p->right);

24    　　　　　if(p->left != NULL)

25         　　　　nodeStack.push(p->left);

26     　　}

27     }

28 }