树的非递归遍历

一、二叉树的非递归遍历

先序遍历：

　　1、根节点p不为空，打印，根节点入栈，并将左孩子作为当前节点，左孩子即当前节点不为空，打印。。。一个while搞定

　　2、若左孩子为空，跳出while循环；if stack 不为空，top栈顶作为当前节点，pop栈顶，将当前节点的右孩子作为当前节点

void preOrder(binaryTree* root)
{
　　stack<binaryTree*> s;
　　binaryTree* current = root;
　　while(NULL != current || false == s.empty())
　　{
　　　　while(NULL != current)
　　　　{
 　　　　　 cout << current->data << " ";  //打印当前节点
　　　　　　s.push(current);
　　　　　　current = current->leftChild;
　　　　}
　　　　if( false == s.empty())
　　　　{
　　　　　　current = s.top();  //保存栈顶节点
　　　　　　s.pop();
　　　　　　current = current->rightChild;
　　　　}
　　}
}

中序遍历：（跟前序遍历很像，利用栈结构达到链表从后向前打印的效果）

void midOrder(binaryTree* root)
{
　　stack<binaryTree*> s;
　　binaryTree* current = root;
　　while(NULL != current || false == s.empty())
　　{
　　　　while(NULL != current)
　　　　{
　　　　　　s.push(current);
　　　　　　current = current->leftChild;
　　　　}
　　　　if( false == s.empty())
　　　　{
　　　　　　current = s.top();  //保存栈顶节点
 　　　　　 cout << current->data << " ";  //打印当前节点
　　　　　　s.pop();
　　　　　　current = current->rightChild;
　　　　}
　　}
}

后续遍历：

要保证根结点在左孩子和右孩子访问之后才能访问根节点；

因此对于任一结点P，先将其入栈。if P不存在左孩子和右孩子，或者P存在左孩子或者右孩子都已被访问过了，则同样可以直接访问该结点。

否则，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候按照左右根的顺序访问。

void postOrder(BinTree *root)     //非递归后序遍历
{
 stack<BinatyTree*> s;
 BinatyTree *current;                      //当前结点 
    BinatyTree *pre = NULL;                 //前一次访问的结点 
 s.push(root);
while(false == s.empty())
 {
 current = s.top();
if((NULL == current->leftChild && NULL == current->rightChild) ||
 (NULL != pre && ( pre==current->leftChild || pre==current->rightChild)))
 {
 cout<<current->data<<" ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
 s.pop();
 pre = current; 
 }
else
 {
if(NULL != current->rightChild)
 s.push(current->rightChild);
if(NULL != current->leftChild) 
 s.push(current->leftChild);
 }
 } 
}

二、多叉树的遍历

原文链接

多叉树的节点包括当前节点pNode和以链表list<Node*>存储的孩子节点

struct Node{ 
 Node *pNode; 
 list<Node *> childsNode; 
};

递归：

//前序遍历(正序遍历):   
void EnumNode(Node *root) 
{ 
 if(NULL == root)
 　 return;
 Node* current = root;
　if(NULL != current->pNode){
　cout << root->pNode->data << " "; 
 } 
 if(NULL != current->childsNode.size){ 　　list<Node *>::iterator iter; //正向遍历器   
  　　for(iter=pNode->childsNode.begin(); iter!=pNode->childsNode.end(); ++iter) 
 　　{ 
 　　EnumNode(*iter); 
 　　 } 
　　} } 

//后序遍历(反序遍历):   
void REnumNode(Node *root) //考虑异常输入，同上即可
{ 
 list<Node *>::reverse_iterator iter; //反向遍历器   
for(iter=pNode->childsNode.rbegin();iter!=pNode->childsNode.rend();++iter) 
 { 
 REnumNode(*iter); 
 } 
 cout << root->pNode->data << " "; 
}

非递归：（栈）

//多叉树堆栈遍历 
//前序遍历(正序遍历):   
void EnumNode(Node *root) 
{ 
 if(NULL == root)
 return;
 stack<Node *> stack; stack.push(root); 
 Node *current; 
while(!stack.empty()) 
 { 
 current = stack.top(); 
 stack.pop(); 
 cout << current->pNode->data << " "; 
　　　 if(NULL != current->childsNode.size()){ 　　list<Node *>::reverse_iterator iter; //反向遍历器   
      　　for(iter=current->childsNode.rbegin();iter!=pNode->childsNode.rend();++iter) //逆序插入栈中
 　　{ 
 　　 stack.push(*iter); 
 　　}
　　　　} } 
}

//后序遍历(反序遍历): 
void REnumNode(Node *root) 
{ 
if(NULL != root)
　　 return;
　stack<Node *> stack; 
 stack.push(root); 
 Node *current; 
 Node *keyNode = NULL; //保存最近一次处理的节点,或者说某个节点的第一个子节点 
while(!stack.empty()) 
 { 
 current = stack.top(); 
//keyNode是 最后一个儿子节点 到 第一个儿子节点 
 //当一个儿子节点遍历过后，再将该儿子节点赋给keyNode
 //当keyNode == *current->childsNode.begin()，表示第一个儿子节点已经遍历完毕，并从栈中弹出。
 　　　　//此时当前节点为其父节点，防止current->childsNode.size()为真，继续遍历儿子节点，
 // 所以加入keyNode != *current->childsNode.begin()避免二次遍历儿子节点
　　　  if (NULL != current->childsNode.size() && keyNode != *current->childsNode.begin())   //size不为0，说明current有孩子

 { 
 list<Node *>::iterator iter; //正向遍历器 
for(iter = childsNode.begin();iter! = current->childsNode.end();++iter) 
 { 
 stack.push(*iter); 
 } 
 }
　　　　else{ cout << current->pNode->data << " "; 
 keyNode = current;
　　　　　 stack.pop();
　　　　}
　　}
}

秒客网

树的非递归遍历

相关文章