두 갈래 나무의 여섯 가지 역행 방식

8191 단어 두 갈래 나무
1. 귀속 실현 전순, 중순 및 후순 두루
1 void printTree(node *T)

2 {

3     if(T)

4     {

5         printTree(T->left);

6         cout<<T->val;// T , , 

7         printTree(T->right);

8     }

9 }

2. 순환은 전순, 중순과 후순을 반복한다
아이디어 참조:
http://blog.csdn.net/ns_code/article/details/12977901
(1) 앞 순서
 1 void Pre_treverse(node *T)

 2 {

 3     stack<node *> STA;

 4     node *p=T;

 5     while(p || !STA.empty())

 6     {

 7         cout<<p->val;

 8         STA.push(p);

 9         p=p->left;

10         while(p==NULL && !STA.empty())

11         {

12             p=STA.top();

13             p=p->right;

14             STA.pop();

15         }

16     }

17 }

(2) 중간 순서
 1 void in_traverse(node *T)

 2 {

 3     stack<node *> STA;

 4     node *p=T;

 5     while(p || !STA.empty())

 6     {

 7         if(p->left)

 8         {

 9             STA.push(p);

10             p=p->left;

11         }

12         else

13         {

14             cout<<p->val<<endl;

15             p=p->right;

16             while(!p && !STA.empty())

17             {

18                 p=STA.top();

19                 cout<<p->val<<endl;

20                 STA.pop();

21                 p=p->right;

22             }

23         }

24     }

25 }

(3) 후순
 1 void beh_traverse(node *T)

 2 {

 3     stack<node *>STA;

 4     node *p;

 5     node *pre=NULL;

 6     STA.push(T);

 7     while(!STA.empty())

 8     {

 9         p=STA.top();

10         if((p->left==NULL && p->right==NULL) || ((pre==NULL)&&(pre==p->left || pre==p->right)))

11         {

12             cout<<p->val<<endl;

13             STA.pop();

14             pre=p;

15         }

16         else

17         {

18             if(p->right)

19                 STA.push(p->right);

20             if(p->left)

21                 STA.push(p->left);

22         }

23     }

24 }

좋은 웹페이지 즐겨찾기