(31)王道数据结构-二叉树的前中后序遍历

定义

遍历: 按照某种次序把所有结点都访问一遍
层次遍历: 基于树的层次特性确定的次序规则

递归特征:
①要么是个空二叉树
②要么就是由“根节点+左子树+右子树”组成的二叉树

先序遍历: 根左右(NLR)
中序遍历: 左根右(LNR)
后续遍历: 左右根(LRN)

算数表达式分析树

将操作数作为二叉树的叶子结点,操作符作为二叉树的非叶子结点

graph TD;
    A(("-"));
    B(("+"));
    C(("/"));
    D(("a"));
    E(("*"));
    F(("e"));
    G(("f"));
    H(("b"));
    I(("-"));
    J(("c"));
    K(("d"));
    A-->B;
    A-->C;
    B-->D;
    B-->E;
    C-->F;
    C-->G;
    E-->H;
    E-->I;
    I-->J;
    I-->K;

算数表达式:
a + b * (c - d) - e/f

先序遍历: -+ab-cd/ef
中序遍历: a+bc-d-e/f
后续遍历: abcd-*ef/-

先序遍历->前缀表达式
中序遍历->中缀表达式(要加界限符)
后续遍历->后缀表达式

三种遍历

先序遍历

先序遍历的操作过程如下:
1.若二叉树为空，则什么也不做
2.若二叉树非空:
①访问根节点
②先序遍历左子树
③先序遍历右子树

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//先序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);   //访问根节点
        PreOrder(T->lchild);    //递归遍历左子树
        PreOrder(T->rchild);    //递归遍历右子树
    }
}

中序遍历

中序遍历操作过程如下
1.若二叉树为空，则什么也不做
2.若二叉树非空:
②先序遍历左子树
①访问根节点
③先序遍历右子树

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//中序遍历
void midOrder(BiTree T) {
    if (T != NULL) {
        midOrder(T->lchild);    //递归遍历左子树
        visit(T);   //访问根节点
        midOrder(T->rchild);    //递归遍历右子树
    }
}

后续遍历

后续遍历操作过程如下
1.若二叉树为空，则什么也不做
2.若二叉树非空:
②先序遍历左子树
③先序遍历右子树
①访问根节点

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

//后续遍历
void afterOrder(BiTree T) {
    if (T != NULL) {
        afterOrder(T->lchild);    //递归遍历左子树
        afterOrder(T->rchild);    //递归遍历右子树
        visit(T);   //访问根节点
    }
}

代码实现

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode {
    char data;
    struct BiTNode *left, *right;
}BiTNode, *BiTree;

//为树的当前节点添加左子节点
bool addLeftChild(BiTree root, char leftData) {
  //分配新节点
  BiTree leftNode = (BiTree)malloc(sizeof(BiTNode));
  //为新节点挂载数据
  leftNode->data = leftData;
  //新节点暂时无子节点
  leftNode->left = NULL;
  leftNode->right = NULL;
  //将新节点挂到当前节点下
  root->left = leftNode;
  return true;
}

//为树的当前节点添加右子节点
bool addRightChild(BiTree root, char rightData) {
  //分配新节点
  BiTree rightNode = (BiTree)malloc(sizeof(BiTNode));
  //为新节点挂载数据
  rightNode->data = rightData;
  
  //新节点暂时无子节点
  rightNode->left = NULL;
  rightNode->right = NULL;
  
  //将新节点挂到当前节点下
  root->right = rightNode;
  return true;
}

void visit(BiTree root) {
    printf("%c ", root->data);
}

// 前序遍历，根--左--右
void preOrder(BiTree root) {
  if (root != NULL) {
        visit(root);   //访问根节点
        preOrder(root->left);    //递归遍历左子树
        preOrder(root->right);    //递归遍历右子树
    }
}

// 中序遍历，左--根--右
void midOrder(BiTree root) {
   if (root != NULL) {
        midOrder(root->left);    //递归遍历左子树
        visit(root);   //访问根节点
        midOrder(root->right);    //递归遍历右子树
    }
}


// 后序遍历，左--根--右
void afterOrder(BiTree root) {
   if (root != NULL) {
        afterOrder(root->left);    //递归遍历左子树
        afterOrder(root->right);    //递归遍历右子树
        visit(root);   //访问根节点
    }
}

//释放二叉树节点内存
void deltree(BiTree tree){
    if (tree != NULL) {
        deltree(tree->left);//先往左子树一直寻找
        deltree(tree->right);//再往右子树一直寻找
        free(tree); //找不到了free返回上一级
    }
}

int main() {
  //设定根节点
  BiTree root;
  root = (BiTree)malloc(sizeof(BiTNode));
  
  //根节点A
  root->data = 'A';
  addLeftChild(root, 'B');
  addRightChild(root, 'C');
  
  //为B节点增加子节点
  addLeftChild(root->left, 'D');
  addRightChild(root->left, 'E');
  
  //为C节点增加子节点
  addLeftChild(root->right, 'F');
  addRightChild(root->right, 'G');
  printf("\n前序遍历：");
  preOrder(root);
  
  printf("\n中序遍历：");
  midOrder(root);
  
  printf("\n后序遍历：");
  afterOrder(root);
  
  deltree(root);
  return 0;
}