二叉树遍历算法递归实现+层次遍历

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了二叉树遍历算法递归实现+层次遍历，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2110字，纯文字阅读大概需要4分钟。

内容图文

二叉树遍历算法

二叉树的存储结构

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;
            }
        }
    }
}

内容总结

以上是互联网集市为您收集整理的二叉树遍历算法递归实现+层次遍历全部内容，希望文章能够帮你解决二叉树遍历算法递归实现+层次遍历所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---