数据结构—基础知识(11):二叉树的遍历
二叉树的遍历
二叉树的遍历是指按某条搜索路径访问树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。由于二叉树是一种非线性结构,每个结点都可能有两棵子树,因而需要寻找一种规律,以便使二叉树上的结点能排列在一个线性队列上,进而便于遍历。
由二叉树的递归定义可知,遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法,其中“序”指的是根结点在何时被访问。
先序遍历:ABCDEFGH
中序遍历:BDCEAFHG
后序遍历:DECBHGFA
-
先序遍历
先序遍历的操作过程如下:
若二叉树为空则什么都不做;否则,①访问根节点;②先序遍历左子树;③先序遍历右子树。
对应的递归算法:文章来源:https://www.toymoban.com/news/detail-827589.html
void PreOrder(BinTree T) {//先序遍历的递归算法 if(T!=NULL) { visit(T);//访问根结点 PreOrder(T->lchild);//递归遍历左子树 PreOrder(T->rchild);//递归遍历右子树 } }
先序遍历的非递归算法:
void PreOrder2(BinTree T) {//先序遍历的非递归算法 InitStack(S);BiTree p=T;//初始化栈S;p是遍历指针 while(p||!IsEmpty(S))//栈不空或p不空时循环 { if(p){//一路向左 visit(p);Push(S,p);//访问当前结点,并入栈 p=p->lchild;//左孩子不空,一直向左走 } else{//出栈,并转向出栈结点的右子树 Pop(S,p);//栈顶元素出栈 p=p->rchild;//向右子树走,p赋值为当前结点的右子树 }//返回while循环继续进入if-else语句 } }
-
中序遍历
中序遍历的操作过程如下:
若二叉树为空则什么都不做;否则,①先序遍历左子树;②访问根节点;③先序遍历右子树。
对应的递归算法:
void InOrder(BinTree T) {//中序遍历的递归算法 if(T!=NULL) { InOrder(T->lchild);//递归遍历左子树 visit(T);//访问根结点 InOrder(T->rchild);//递归遍历右子树 } }
中序非递归遍历
void InOrder2(BiTree T) { InitStack(S); BiTree p=T;//初始化栈S;p是遍历指针 while(p||!IsEmpty(S))//栈不空或p不空时循环 { if(p){//一路向左 Push(S,p);//当前结点入栈 p=p->1child;//左孩子不空,一直向左走 } else{//出栈,并转向出栈结点的右子树 Pop(S,p);visit(p);//栈顶元素出栈,访问出栈结点 p=p->rchild;//向右子树走,p赋值为当前结点的右孩子 }//返回 while 循环继续进入if-else语句 } }
-
后序遍历
后序遍历的操作过程如下:
若二叉树为空则什么都不做;否则,①先序遍历左子树;②先序遍历右子树;③访问根节点。
对应的递归算法:
void PostOrder(BinTree T) {//后序遍历的递归算法 if(T!=NULL) { PostOrder(T->lchild);//递归遍历左子树 PostOrder(T->rchild);//递归遍历右子树 visit(T);//访问根结点 } }
后序遍历的非递归算法:文章来源地址https://www.toymoban.com/news/detail-827589.html
void PostOrder (BiTree T) { InitStack(S); BiTNode *p=T; BiTNode *r=NULL; while(p||!IsEmpty(S)) { if(p){//走到最左边 push(S,p); p=p->lchild; } else{//向右 GetTop(S,p);//读栈顶结点(非出栈) if(p->rchild&&p->rchild!=r)//若右子树存在,且未被访问过 p=p->rchild;//转向右 else{//否则,弹出结点并访问 pop(S,p);//将结点弹出 visit(p->data);//访问该结点 r=p;//记录最近访问过的结点 p=NULL;//结点访问完后,重置p指针 } }//else }//while }
到了这里,关于数据结构—基础知识(11):二叉树的遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!