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

快来打我* 2022-11-30 04:12 213阅读 0赞

## 二叉树遍历算法 ##

### 二叉树的存储结构 ###

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 层次遍历 ####

![1_.png][]

上图所示为二叉树的层次遍历，即按照箭头所指方向，按照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;
    			}
            }
        }
    }

[1_.png]: /images/20221124/64808f5dbad9442487059497b9a25671.png