欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++ | 二叉树前序、中序、后序遍历的递归和非递归实现 +层序遍历+深度优先遍历

程序员文章站 2022-05-16 14:21:39
...

二叉树的遍历是学习二叉树最基本却极为重要的一环。当你熟练掌握二叉树的遍历之后,你会发现很多题目都是建立在遍历的基础上来解决的。本文章就是为了盘点一下各种遍历算法的原理和实现。

前序遍历

前序遍历也叫先序遍历(preorder),整个操作过程比较简单,先访问根结点,在访问左子树,左子树访问完之后访问右子树。

  1. 若二叉树为空,则什么也不做
  2. 否则:
    2.1 访问根结点
    2.2. 先序遍历左子树
    2.3. 先序遍历右子树

递归实现

void preOrder(BinTree* BT){
    if(BT){
        printf("%d ", BT->data);
        preOrder(BT->left);
        preOrder(BT->right);
    }
}

非递归实现

void preOrder(TreeNode* root){
    if(root == NULL) return;
    stack<TreeNode*> S;    // 初始化栈
    TreeNode* node = root; // 声明遍历指针
    while(node || !S.empty()){
    	if(node != NULL)}{  // 不断访问树的根节点,并且存储左子树(若存在的话)
       		 cout << node->val << " ";   
 			 S.push(node);
        	 node = node->left;
    	}
    	else{ // 遇到空指针,访问栈顶指针指向的右子树结点
        	node = S.top()->right;
             S.pop();
    	}  
    }
}

中序遍历

中序遍历(inorder),整个操作过程也比较简单。

  1. 若二叉树为空,则什么也不做
  2. 否则:
    2.1 中序遍历左子树
    2.2. 访问根结点
    2.3. 中序遍历右子树

递归实现

void preOrder(TreeNode* root){
    if(root != NULL){
        preOrder(root->left);
        cout << root->val << " ";
        preOrder(root->right);
    }
}

非递归实现

void preOrder(TreeNode* root){
    if(root == NULL) return;
    stack<TreeNode*> S;
    TreeNode* node = root;
    while(node!=NULL || !S.empty()){
    	if(node != NULL)}{
    	     // cout << node->val << " ";  先序遍历:在push时访问结点值
 			 S.push(node);
        	  node = node->left;
    	}
    	else{
            cout << node->val << " ";   // 中序遍历:在弹出栈顶指针时访问
        	node = S.top()->right;
             S.pop();
    	}  
    }
}

后序遍历

后序遍历(postorder),整个操作过程也比较简单。

  1. 若二叉树为空,则什么也不做
  2. 否则:
    2.1 后序遍历左子树
    2.2. 后序遍历右子树
    2.3 访问根结点

后序遍历的递归实现比较容易,而非递归实现则比较难。

递归实现

void preOrder(TreeNode* root){
    if(root != NULL){
        preOrder(root->left);
        preOrder(root->right);
        cout << root->val << " ";
    }
}

非递归实现

非递归实现比较难,同样的可以使用栈来存储临时值,但是我们需要区分返回根结点时,是从左子树返回还是右子树返回的。

// 先访问左子树,然后访问右子树,再访问根节点
// 使用堆栈来存储结点指针,需要分清返回根结点时是左子树或者右子树
// 我们使用一个辅助指针r来指向最近访问的结点,借助这个指针来区分根节点是从左子树还是右子树返回的。 
void postOrder(BiTree* root){
    // 初始化一个栈 S
    initStack(S);
    // 声明一个遍历指针 p
    BiTree* p = root;
    // 声明一个空的辅助指针
    BiTree* r = NULL;
    while(p ||! S.empty()){
        if(p){ // 非空结点,压栈
            push(S, p); // 压栈,走左子树
            p = p->left;
        }
        else{ // 空结点
            getTop(S, p);    // 取出栈顶结点赋值给p
            if(p->right && p->right != r){  // 存在右子树,并且未访问过
                p = p->right;   // 取右子树根结点,入栈
                push(S,  p);
                p = p->left;
            }
            else{  // 不存在右子树或者 已经访问完右子树
                pop(S, p);      // 弹出栈顶指针并赋值给p
                visit(p->val);  // 访问结点值
                r = p;          // 记录最近访问的结点
                p = NULL;       // 将p置为空
            }
        }
    }
}

层序遍历

层序遍历的思路也比较简单易懂,属于广度优先的一种方法,在访问结点之后,我们使用队列来存储一些左右结点指针。

void levelOrder(TreeNode* root){
    if(root == NULL) return;
    queue<TreeNode*> Q;
    Q.push(root);
    while(!Q.empty()){
        TreeNpde* node = Q.front();
        Q.pop();
        cout << node->val << " ";
        if(node->left != NULL)
            Q.push(node->left);
        if(node->right != NULL)
            Q.push(node->right);
    }
}

深度优先遍历

深度优先的思路也不难,思路类似层序遍历,但不同的是使用了栈来存储临时指针。

void depthOrder(TreeNode* root){
    if(root == NULL) return;
    stack<int> S;
    S.push(root);
    while(!S.empty()){
       	TreeNode* node = S.pop();
       	cout << node->val << " ";
        if(node->left != NULL)
            S.push(node->left);
        if(node->right != NULL)
            S.push(node->right);
    }
}