二叉树 先根遍历 中跟遍历 后跟遍历 迭代+递归实现代码

遍历 中跟遍历 后跟遍历 迭代+递归实现代码"/>

二叉树 先根遍历 中跟遍历 后跟遍历 迭代+递归实现代码

二叉树 先根遍历 中跟遍历 后跟遍历

结构体：

struct Node{int val;Node *LC;Node *RC;Node(int k){this->val=k;LC=NULL;RC=NULL;}
};

函数：

void preOrder(Node *root){//先根遍历就是DFS呀 递归实现 if(root==NULL){return;}cout<<root->val<<" ";preOrder(root->LC);preOrder(root->RC); 
}
void inOrder(Node *root){if(root==NULL){return;}inOrder(root->LC);cout<<root->val<<" ";inOrder(root->RC);
}
void postOrder(Node *root){if(root==NULL){return;}postOrder(root->LC);postOrder(root->RC);cout<<root->val<<" ";
} 
//迭代实现     先访问，然后去左节点，最后右节点 stack起到了保存的作用。 
void ppreOrder(Node *root){stack<Node*> s;Node *p=root;while(p!=NULL||!s.empty()){while(p!=NULL){cout<<p->val<<" ";s.push(p);p=p->LC;}if(!s.empty()){p=s.top();s.pop();p=p->RC;}}
}
void iinOrder(Node *root){stack<Node *> s;Node *p=root;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p->LC;} if(!s.empty()){p=s.top();cout<<p->val<<" ";s.pop();p=p->RC;}}
} 
void ppostOrder(Node *root){  // 后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。所以，使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被访问Node *p = root, *r = NULL;stack<Node*> s;while (p!=NULL || !s.empty()) {if (p!=NULL) {//走到最左边s.push(p);p = p->LC;}else {p = s.top();if (p->RC!=NULL && p->RC != r)//右子树存在，未被访问p = p->RC;else {s.pop();cout<<(p->val)<<" ";r = p;//记录最近访问过的节点p = NULL;//节点访问完后，重置p指针}}//else}//while
}

要写头文件 include<stack>
Main函数：

int main(){Node *p=new Node(5);Node *q=new Node(2);Node *l=new Node(6);Node *k=new Node(3);q->RC=k; p->LC=q;p->RC=l;preOrder(p);cout<<endl;inOrder(p);cout<<endl;postOrder(p);cout<<endl;	ppreOrder(p);cout<<endl;iinOrder(p); cout<<endl;ppostOrder(p);
}

结果输出：

先跟遍历和BFS一样，DFS利用queue来实现。
参考博客：二叉树前序（先序）中序后序遍历 C++递归和非递归实现