二叉树的遍历——先序遍历、中序遍历、后序遍历

淡淡的烟草味﹌ 2022-12-01 15:44 221阅读 0赞

# 遍历二叉树 #

（本文的二叉树均使用指针方式构建）

## 先序遍历 ##

### 操作定义： ###

**若二叉树为空，则空操作；** 否则：

1.  访问根节点；
2.  先序遍历左子树；
3.  先序遍历右子树；

### 代码： ###

void preOrderTraveral(treeNode* node){
        
        if (node == NULL){
        
            return;
        }
    
        cout << node->data;
        preOrderTraveral(node->lchild);
        preOrderTraveral(node->rchild);
    }

--------------------

## 中序遍历 ##

### 操作定义： ###

**若二叉树为空，则空操作；** 否则：

1.  中序遍历左子树；
2.  访问根节点；
3.  中序遍历右子树；

### 代码： ###

void inOrderTraveral(treeNode* node){
        
        if (node == NULL){
        
            return;
        }
    
        inOrderTraveral(node->lchild);
        cout << node->data;
        inOrderTraveral(node->rchild);
    }

--------------------

## 后序遍历 ##

### 操作定义： ###

**若二叉树为空，则空操作；** 否则：

1.  后序遍历左子树；
2.  后序遍历右子树；
3.  访问根节点；

### 代码： ###

void postOrderTraveral(treeNode* node){
        
        if (node == NULL){
        
            return;
        }
    
        postOrderTraveral(node->lchild);
        postOrderTraveral(node->rchild);
        cout << node->data;
    }

--------------------

# 举例： #

对于如图所示二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQxMzY4OQ_size_16_color_FFFFFF_t_70_pic_center]  
其先序遍历、中序遍历、后序遍历分别为：  
![在这里插入图片描述][20200827233148978.jpg_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQxMzY4OQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/439a978dc314499d9a849a462ee95549.png
[20200827233148978.jpg_pic_center]: /images/20221123/5cbe731906fe4cccb187fcb01ba10798.png