二叉树的遍历介绍
发布时间：2021-11-15 12:03:27 所属栏目：教程 来源：互联网
导读：所谓二叉树的遍历，就是按照某种次序访问二叉树中的每个节点，而且每个节点仅访问一次的过程。以L、N、R分别表示遍历左子树、访问根节点、遍历右子树，则可有NLR、LRN、NRL、RNL、RLN等6中遍历方式。若限定先左后右，则只有三种遍历，分别成为先序遍历、中序
|
所谓二叉树的遍历，就是按照某种次序访问二叉树中的每个节点，而且每个节点仅访问一次的过程。以L、N、R分别表示遍历左子树、访问根节点、遍历右子树，则可有NLR、LRN、NRL、RNL、RLN等6中遍历方式。若限定先左后右，则只有三种遍历，分别成为先序遍历、中序遍历和后序遍历，另外还有一种按层序的遍历方式。下面我们采用一个例子来完成的描述二叉树的遍历过程： 二叉树的遍历详述 这是一个递归生成的二叉树，’#’表示节点为空。 #include<iostream> #include<cstdlib> #define MaxSize 30 using namespace std; typedef char ElementType; typedef struct node { ElementType data; struct node *lchild; struct node *rchild; }BTNode; void CreateBTree(BTNode* &T){ //按先序输入二叉树中结点的值（一个字符），空格字符代表空树， //构造二叉树表表示二叉树T。 char ch; if((ch=getchar())=='#')T=NULL;//其中getchar（）为逐个读入标准库函数 else{ T=(BTNode*)malloc(sizeof(BTNode));//产生新的子树 T->data=ch;//由getchar（A）逐个读入来 CreateBTree(T->lchild);//递归创建左子树 CreateBTree(T->rchild);//递归创建右子树 } }//CreateTree void PreOrder(BTNode *b) { if(b!=NULL) { cout<<b->data<<" "; PreOrder(b->lchild); PreOrder(b->rchild); } } //先序非递归算法 void PreOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { top++; St[top]=b; while(top!=-1) { p=St[top]; top--; cout<<p->data<<" "; if(p->rchild!=NULL) { top++; St[top]=p->rchild; } if(p->lchild!=NULL) { top++; St[top]=p->lchild; } } cout<<endl; } } //中序非递归算法 void InOrder1(BTNode *b) { BTNode *St[MaxSize],*p; int top=-1; if(b!=NULL) { p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; p=p->lchild; } if(top>-1) { p=St[top]; top--; cout<<p->data<<" "; p=p->rchild; } } cout<<endl; } } void InOrder(BTNode *b) { if(b!=NULL) { InOrder(b->lchild); cout<<b->data<<" "; InOrder(b->rchild); } } void PostOrder(BTNode *b) { if(b!=NULL) { PostOrder(b->lchild); PostOrder(b->rchild); cout<<b->data<<" "; } } //后序递归算法 void PostOrder1(BTNode *b) { BTNode *St[MaxSize]; BTNode *p=b,*q; int flag,top=-1; if(b!=NULL) { do { while(p!=NULL) { top++; St[top]=p; p=p->lchild; } q=NULL; flag=1; while(top!=-1&&flag==1) { p=St[top]; if(p->rchild==q) { cout<<p->data<<" "; top--; q=p; }else { p=p->rchild; flag=0; } } }while(top!=-1); cout<<endl; } } //层序遍历 void LevelOrder(BTNode *b) { BTNode *p; BTNode *qu[MaxSize]; int front,rear; front=rear=0; rear++; qu[rear]=b; while(front!=rear) { front=(front+1)%MaxSize; p=qu[front]; cout<<p->data<<" "; if(p->lchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->rchild; } } } int main() { BTNode *b; CreateBTree(b); cout<<"先序遍历结果:"<<endl; //PreOrder(b); PreOrder1(b); cout<<"中序遍历结果:"<<endl; //InOrder(b); InOrder1(b); cout<<endl; cout<<"后序遍历结果:"<<endl; //PostOrder(b); PostOrder1(b); cout<<"层序遍历结果："<<endl; LevelOrder(b); return 0; } 我们采用两种方式遍历二叉树，一种是递归方式，一种采用非递归方式（栈和队列）。 运行程序： 二叉树的遍历详述 各种遍历得到的结果如图所示： 二叉树的遍历详述 至此二叉树的遍历就已经讲完了，希望对大家有所帮助！  （编辑：开发网_开封站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330459号