JZTXT

二叉树的前序、中序、后序、层序遍历

发布时间 2023-11-12 21:59:20作者: 小白不败

在写遍历函数前，我们需要知道这几种遍历方法的访问结点的顺序。

  • 前序遍历：
    1.先访问根节点。
    2.再访问左子树。
    3.最后访问右子树。
  • 中序遍历：
    1.先访问左子树。
    2.在访问根结点。
    3.最后访问右子树。
  • 后序遍历：
    1.先访问左子树。
    2.在访问右子树。
    3.最后访问根结点。
  • 层序遍历：
    按照二叉树的层次遍历，每层依次从左至右。

对于前序、中序、后序遍历函数，我们可以这样写：

int PreOrder(Node *root){//前序遍历函数
      if(root==nullptr){
        return 0;
      }else{
        cout<<root->data;        //输出当前结点的数值   I式
        PreOrder(root->lchild);  //访问当前结点的左子树 II式
        PreOrder(root->rchild);  //访问当问结点的右子树 III式
      }
}

而对于中序、后序遍历函数无非是改变一下I式、II式、III式的顺序，这里就不再赘述。

重点来了！！！

层序遍历函数，需要用到队列的知识，因为在对二叉树层序遍历时就非常满足队列的性质。
//层序遍历
void Tree::LeverOrder() {
	Node *Queue[20];                //定义一个数组指针，用来存储入队的结点指针
	Node* q = nullptr;              //定义一个临时指针
	int front = -1, rear = -1;      //front、rear是指示器，用来指示Queue的下标
	if (root == nullptr) {
		return ;
	}
	Queue[++rear] = root;
	while (front != rear) {
		q = Queue[++front];
		cout << q->data;
        //如果根节点的左、右子树非空就入队
		if (q->lchild != nullptr) {
			Queue[++rear] = q->lchild;
		}
		if (q->rchild != nullptr) {
			Queue[++rear] = q->rchild;
		}
	}
}