关于数据结构:二叉树遍历算法递归实现层次遍历

二叉树遍历算法

二叉树的存储构造

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