二叉树遍历算法递归实现+层次遍历
原创
二叉树遍历算法
二叉树的存储结构
typedef struct BTNode
{
char data; //这里默认结点data为char型
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;二叉树的遍历算法
1 先序遍历
先序遍历的操作如下。
如果二叉树为空树，则什么都不做；否则：
1）访问根节点
2）先序遍历左子树
3）先序遍历右子树
描述如下：
void preorder(BTNode *p)
{
if(p != NULL)
{
visit(p); //假设访问函数Visit()已经定义过
preorder(p->lchild); //先序遍历左子树
preorder(p->rchild); //先序遍历右子树
}
}2 中序遍历
中序遍历的操作如下。
如果二叉树为空树，则什么都不做；否则：
1）中序遍历左子树
2）访问根节点
3）中序遍历右子树
描述如下：
void inorder(BTNode *p)
{
if(p != NULL)
{
inorder(p->lchild);
visit(p);
inorder(p->rchild);
}
}3 后序遍历
后序遍历的操作如下。
如果二叉树为空树，则什么都不做；否则：
1）后序遍历左子树
2）后序遍历右子树
3）访问根节点
描述如下：
void postorder(BTNode *p)
{
if(p != NULL)
{
postorder(p->lchild);
postorder(p->rchild);
visit(p);
}
}4 层次遍历
<img src="https://irabbit756.oss-cn-shanghai.aliyuncs.com/数据结构/二叉树遍历/1二叉树层次遍历.png" style="zoom: 67%;" />
上图所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3、4的层次顺序，对二叉树中各个结点进行访问（此图反映的是自左至右的层次遍历，自右至左的方式类似）
要进行层次遍历，需要建立一个循环队列先将二叉树头结点入队列，然后出队列，访问该结点，如果它有左子树，则将左子树的根结点入队；如果它有右子树，则将右子树的根结点入队。然后出队列，对出队结点访问。如此反复，直到队列为空为止。
由此得到的对应算法如下:
void level(BTNode *p)
{
int front,rear;
BTNode *que[maxSize]; //定义一个循环队列，用来记录将要访问的层次上的结点
front = rear = 0;
BTNode *q;
if(p != NULL)
{
rear = (rear + 1) % maxSize;
que[rear] = p; //根结点入队
while(front != rear) //当队列不空的时候进行循环
{
front = (front + 1) % maxSize;
q = que[front]; //队头结点出队
visit(q); //访问队头结点
if(q->lchild != NULL) //如果左子树不空，则左子树的根结点入队
{
rear = (rear + 1) % maxSize;
que[rear] = q->lchild;
}
if(q->rchild != NULL) //如果右子树不空，则右子树的根结点入队
{
rear = (rear + 1) % maxSize;
que[rear] = q->rchild;
}
}
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录