二叉树的遍历 (前序 中序 后序) 递归&非递归

二叉树由3个基本单元组成,根节点、左子树和右子树。因此,若能依次遍历这三部分,便是遍历了整个二叉树。假如从L、D、R分别表示遍历左子树、访问根节点和遍历右子树,则可有DLR、LDR、LRD、DRL、RDL、RLD这6种方案,若限定先左后右,则只有前3种情况,分别称为先序遍历、中序遍历和后序遍历。

这里使用的二叉树的存储结构见 二叉树的链式存储结构 C语言实现

遍历二叉树的递归算法

  • 先序遍历
void PreOrderTraverse(BiTNode* T){
    if (T) {
        printf("%c", T->Data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
  • 中序遍历
void InOrderTraverse(BiTNode* T) {
    if (T) {
        InOrderTraverse(T->lchild);
        printf("%c", T->Data);
        InOrderTraverse(T->rchild);
    }
}
  • 后序遍历
void PostOrderTraverse(BiTNode* T) {
    if (T) {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c", T->Data);
    }
}

遍历二叉树的非递归算法

可以利用栈的特性实现非递归遍历。在T存在或栈非空的情况下循环,先压栈并遍历左子树,直到遍历到终端节点的左子树,然后出栈进入右子树,借此实现结点的回退和先左后右的遍历方式。先序遍历和中序遍历的差别仅在访问根节点的时机不同。

Ps:栈需要另外实现,代码中函数InitStack()为初始化栈、Push()为压栈、Pop()为出栈、IsEmpty()为判断栈是否为空、getTop()为获取栈顶元素。

  • 先序遍历
void PreOrderTraverse2(BiTNode* T) {
    Stack* mstack = InitStack();
    while (T || !IsEmpty(mstack)) {

        if (T)
        {
            Push(mstack, T);
            printf("%c", T->Data);
            T = T->lchild;
        }
        else {
            T = Pop(mstack);
            T = T->rchild;
        }

    }
}
  • 中序遍历
void InOrderTraverse2(BiTNode* T) {
    Stack* mstack = InitStack();
    while (T || !IsEmpty(mstack)) {
        if (T) {
            Push(mstack, T);
            T = T->lchild;
        }
        else {
            T = Pop(mstack);
            printf("%c", T->Data);
            T = T->rchild;
        }
    }
}

后序遍历比较麻烦,因为在访问根节点前必须要确认已经遍历过它的左右两个子树,这里采用增加一个pre指针的方式。每次访问根节点之后,都将pre指针指向这个结点,当某个结点的左右子树等于这个pre指针时,就说明它的两个子树已经被遍历。

void PostOrderTraverse2(BiTNode* T) {
    Stack* mstack = InitStack();
    BiTNode* cur;
    BiTNode* pre = NULL;
    Push(mstack, T);
    while (!IsEmpty(mstack)) {
        cur = getTop(mstack);
        if ((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild))) {
            printf("%c ", cur->Data);
            Pop(mstack);
            pre = cur;
        }
        else {
            if (cur->rchild != NULL)
                Push(mstack, cur->rchild);
            if (cur->lchild != NULL)
                Push(mstack, cur->lchild);
        }
    }
}

留下你的评论