遍历 中跟遍历 后跟遍历 迭代+递归实现代码"/>
二叉树 先根遍历 中跟遍历 后跟遍历 迭代+递归实现代码
二叉树 先根遍历 中跟遍历 后跟遍历
结构体:
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++递归和非递归实现
更多推荐
二叉树 先根遍历 中跟遍历 后跟遍历 迭代+递归实现代码
发布评论