数据结构与算法--二叉树的遍历以及实现

以你之姓@ 2022-12-25 09:52 75阅读 0赞

## 二叉树的遍历 ##

二叉树的遍历方法有三种：先序遍历，中序遍历和后序遍历

# 先序遍历 #

先序遍历的方法：如果二叉树为空则返回空，否则先访问根结点，然后前序遍历左子树，在先序遍历右子树  
基本算法：

void PreOrderTraverse(BiTree T){
        
        if(T==NULL){
        
            return;
        }
        printf("%c",T->data);
        PostOrderTraverse(T->lchild);//先遍历左子树
        PostOrderTraverse(T->rchild);//在遍历右子树

## 中序遍历 ##

中序遍历的方法:先中序遍历根结点的左子树，在访问根结点，在中序遍历根结点的右子树，  
基本算法

void InOrderTraverse(BiTree T){
        
        if(T==NULL){
        
            return;
        }
        PostOrderTraverse(T->rchild);//在遍历右子树
        PostOrderTraverse(T->lchild);//先遍历左子树
       
        printf("%c",T->data);

### 后序遍历 ###

基本算法：先后序遍历访问根结点的左子树，在后序遍历根结点的右子树，最后访问根结点

void PostOrderTraverse(BiTree T){
        
        if(T==NULL){
        
            return;
        }
        PostOrderTraverse(T->lchild);//先遍历左子树
        PostOrderTraverse(T->rchild);//在遍历右子树
        printf("%c",T->data);
    }

## 例子 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70]

### 关键还是递归的调用 ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2tpbmdKYW1lc2JvbmQ_size_16_color_FFFFFF_t_70]: /images/20221120/ba413936c69c40b99d4009a533cfde98.png