二叉树的遍历 本是古典 何须时尚 2022-03-10 08:00 128阅读 0赞 # 一、前序遍历 # ### 前序遍历的规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。 ### //结点结构体 struct Node{ //int value; int data; Node *left;//左子树指针 Node *right;//右子树指针 int lvisited, rvisited;//左、右孩子是否访问过,1表示已访问(此项只在后序非递归算法中需要) Node():lvisited(0), rvisited(0){} }; ### 递归版本: ### //前序遍历递归算法 void preordert(Node* root) { if (root != NULL) { cout << "结点数据:" << root->data << endl; preordert(root->left);//递归左子树 preordert(root->right);//递归右子树 } } ### 非递归版本一: ### //前序遍历非递归算法--用栈实现 void preordernonrec(Node* root) { Node *p = NULL; stack<Node*> st; if (root != NULL) { st.push(root); while (!st.empty()) { p = st.top(); st.pop(); cout << p->data << " "; if (p->right != NULL) {//右子树入栈 st.push(p->right); } if (p->left != NULL) {//左子树入栈 st.push(p->left); } } cout << endl; } } ### 非递归版本二: ### //非递归前序遍历 void preorderTraversal(Node *root, vector<int> &path) { stack<Node*> s; Node *p = root; while(p != NULL || !s.empty()) { while(p != NULL) { path.push_back(p->data); s.push(p); p = p->left; } if(!s.empty()) { p = s.top(); s.pop(); p = p->right; } } } # 二、中序遍历 # ### 中序遍历规则是若二叉树为空,则空操作返回,否则从根结点开始(并不是访问根结点),中序遍历根结点的左子树,然后是访问根结点,再中序遍历右子树。 ### //结点结构体 struct Node{ //int value; int data; Node *left;//左子树指针 Node *right;//右子树指针 int lvisited, rvisited;//左、右孩子是否访问过,1表示已访问(此项只在后序非递归算法中需要) Node():lvisited(0), rvisited(0){} }; ### 递归版本: ### //中序遍历递归算法 void ineordert(Node *root) { if (root != NULL) { ineordert(root->left); cout << "结点数据:" << root->data << endl; ineordert(root->right); } } ### 非递归版本一: ### //中序遍历非递归算法--用栈实现 void ineordernonrec(Node* root) { stack<Node*> st; Node *p = NULL; if (root != NULL) { p = root; while (!st.empty() || p != NULL) {//当栈不为空或root存在的时候,开始遍历左孩子 if (p != NULL)//将root进栈,并将指针向左孩子方向移动,直到移动至叶子 { st.push(p); p = p->left; }//左孩子部分已遍历完 else { p = st.top();//将左孩子放入栈中并准备输出 st.pop(); cout << p->data << " "; p = p->right;//将指针移动到具有相同父节点的右孩子上 } } cout << endl; } } ### 非递归版本二: ### //非递归中序遍历 void inorderTraversal(Node *root, vector<int> &path) { stack<Node *> s; Node *p = root; while(p != NULL || !s.empty()) { while(p != NULL) { s.push(p); p = p->left; } if(!s.empty()) { p = s.top(); path.push_back(p->val); s.pop(); p = p->right; } } } # 三、后序遍历 # ### 后序遍历规则是若二叉树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。 ### //结点结构体 struct Node{ //int value; int data; Node *left;//左子树指针 Node *right;//右子树指针 int lvisited, rvisited;//左、右孩子是否访问过,1表示已访问(此项只在后序非递归算法中需要) Node():lvisited(0), rvisited(0){} }; ### 递归版本: ### //后序遍历递归算法 void posordert(Node *root) { if (root != NULL) { posordert(root->left); posordert(root->right); cout << "结点数据:" << root->data << endl; } } ### 非递归版本一: ### //后序遍历非递归算法--用栈实现 //后序非递归遍历思路:因为后序非递归遍历二叉树的顺序是先访问左子树,再访问右子树,最后 //访问根结点。当用堆栈来存储结点,必须分清返回根结点时,是从左子树返回的,还是从右子树 //返回的。所以,使用辅助指针r,其指向最近访问过的结点。 void posordernonrec(Node* root) { Node *p = NULL,*r=NULL; stack<Node*> st; p = root; while (p!=NULL || !st.empty()){ if (p){ //走到最左边 st.push(p); p = p->left; } else //向右 { p = st.top();//取栈顶结点 if (p->right && p->right != r)//如果右子树存在,且未被访问过 { p = p->right; st.push(p); p = p->left; //再走到最左 } else //否则,访问栈顶结点并弹出 { cout << p->data << " "; r = p; //记录该结点 st.pop(); p = NULL; //结点访问完后,重置p指针 } } } cout << endl; } ### 非递归版本二: ### //思路:在结点中增加标志域,记录是否已被访问。 void posordernonrec(Node* root)//后序非递归遍历 { Node *p = NULL; stack<Node*> st; p = root; while (p != NULL || !st.empty()){ if (p!=NULL && p->lvisited == 0) //左走,且左子树未被访问 { p->lvisited = 1; st.push(p); p = p->left; } else{ p = st.top(); if (p->right != NULL && p->rvisited == 0)//右子树未被访问,右走一步 { p->rvisited = 1; p = p->right; } else //访问栈顶元素并弹栈 { cout << p->data << " "; st.pop(); if (!st.empty()) p = st.top(); else //当最后一个元素弹栈出去后,结束 return; } } } cout << endl; } # 四、层序遍历 # ### 层序遍历规则是若二叉树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。 ### 代码实现: //层序遍历(广度优先周游)二叉树算法实现(借助队列实现) void levelorder(Node* root) { queue<Node*> st; Node *q; if (root == NULL) return; //当二叉树判空时,直接返回 else { st.push(root); //根节点存入队列 while (front != rear) { q = st.front(); st.pop(); cout << q->data << " "; if (q->left != NULL) st.push(q->left); //将左孩子存储至队列尾 if (q->right != NULL) st.push(q->right);//将右孩子存储至队列尾 } } cout << endl; }
相关 二叉树 二叉树遍历 通过二叉树遍历求得二叉树 什么是二叉树 > > 二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且 偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 302 阅读
相关 遍历二叉树 1. 二叉树的遍历 遍历定义 ——顺着某一条搜索路径巡访二叉树中的结点,使得 每个结点均被访问一次,而且仅被访问一次。 “访问”的含义可以很广,如:输出结点的信息等。 迈不过友情╰/ 2022年08月22日 14:26/ 0 赞/ 438 阅读
相关 遍历二叉树 遍历二叉树 二叉树是由3个基本单元组成的:根结点、左子树和右子树。 若限定先左后右的顺序,则遍历二叉树只有三种情况分别称为先(根)序遍历、中(根)序遍历和后(根)序遍 比眉伴天荒/ 2022年06月08日 00:48/ 0 赞/ 299 阅读
相关 遍历二叉树 遍历二叉树 今天我们学习了二叉树,现在我就基于二叉树的递归定义来说一说遍历二叉树的三种方法:先序、中序和后序。 根据二叉树的递归定义可知,二叉树是由3个基本单元组成:根结点 傷城~/ 2022年06月05日 08:11/ 0 赞/ 350 阅读
相关 二叉树遍历 include<iostream> include<queue> using namespace std; //二叉树结点 ╰+攻爆jí腚メ/ 2022年06月04日 05:35/ 0 赞/ 298 阅读
相关 二叉树遍历 前序遍历(左中右)ABDGHCEIF ![前序遍历][70] 中序遍历(左根右)GDHBAEICF![中序遍历][70 1] 后序遍历(左右根)GHDBIEFCA![ Bertha 。/ 2022年05月11日 13:48/ 0 赞/ 358 阅读
相关 二叉树遍历 二叉树:二叉树是每个节点最多有两个子树的树结构。 本文介绍二叉树的遍历相关知识。 我们学过的基本遍历方法,无非那么几个:前序,中序,后序,还有按层遍历等等。 设L、D、R 痛定思痛。/ 2022年05月10日 06:24/ 0 赞/ 234 阅读
相关 二叉树遍历 二叉树是数据结构中很重要的一个章节,很多同学反应很难,今天我就把我平时的经验给大家讲解一下,今天讲一下二叉树的遍历 工具/原料 ● 数据结构知识 ● 了解树的定义 爱被打了一巴掌/ 2022年05月10日 03:08/ 0 赞/ 316 阅读
相关 遍历二叉树 用递归的方法实现前序遍历,中序遍历,后序遍历: 用递归的方法遍历的时候,其实每个节点都遍历了三遍,根据打印时间的不同,即可实现前序中序及后续,这就是三个遍历代码一样而打印顺序 浅浅的花香味﹌/ 2021年11月01日 15:28/ 0 赞/ 464 阅读
还没有评论,来说两句吧...