更新时间:2022-09-15 21:04:05
1 void PreOrderTraverse(Node *root) 2 { 3 stack<Node *> ns; 4 Node *n=root; 5 while(n!=NULL || !ns.empty()) 6 { 7 if(n!=NULL) 8 { 9 print(n); 10 ns.push(n); 11 n=n->pLeft; 12 } 13 else 14 { 15 ns.pop(n); 16 n=n->pRight; 17 } 18 } 19 }
1 void InOrderTraverse(Node *root) 2 { 3 stack<Node *> ns; 4 Node *n=root; 5 while(n!=NULL || !ns.empty()) 6 { 7 if(T!=NULL) 8 { 9 ns.push(n); 10 n=n->pLeft; 11 } 12 else 13 { 14 ns.pop(n); 15 print(n); 16 n=n->pRight; 17 } 18 } 19 }
1 void PostOrderTraverse(Node *root) 2 { 3 stack<Node *> ns; 4 Node *n=root; 5 while(n!=NULL || !ns.empty()) 6 { 7 if(n!=NULL) 8 { 9 n->IsFirst=true;//The first time to be the top of ns stack. 10 ns.push(n); 11 n=n->pLeft; 12 } 13 else 14 { 15 if(!ns.empty()) 16 { 17 ns.pop(n); 18 if(n->IsFirst==true)//The first time to be the top of ns stack.Don't print. 19 { 20 n->IsFirst=false; 21 ns.push(n); 22 n=n->pRight; 23 } 24 else //The second time.Print it. 25 print(n); 26 } 27 } 28 } 29 }
1 void PostOrderTraverse2(Node *root) 2 { 3 stack<Node *> ns; 4 Node *n=root; 5 Node *previous=NULL;//It is NULL at first. 6 ns.push(n); 7 while(n!=NULL || !ns.empty()) 8 { 9 n=ns.top(); 10 if( (n->pLeft==NULL && n->pRight==NULL) || (previous==n->pLeft || previous==n->pRight)) 11 { 12 print(n); 13 ns.pop(); 14 previous=n; 15 } 16 else 17 { 18 if(n->pRight!=NULL) 19 ns.push(n->pRight); 20 if(n->pLeft!=NULL) 21 ns.push(n->pLeft); 22 } 23 } 24 }