数据结构（八）二叉树遍历

秒速五厘米 2022-08-09 05:26 117阅读 0赞

![这里写图片描述][20151012221226464]

![这里写图片描述][909995_1420569532126_2.png]

## 示例1 ##

> 二叉树是一种树形结构，遍历就是要让树中的所有节点被且仅被访问一次，即按一定规律排列成一个线性队列。二叉（子）树是一种递归定义的结构，包含三个部分：根结点（N）、左子树（L）、右子树（R）。根据这三个部分的访问次序对二叉树的遍历进行分类，总共有6种遍历方案：NLR、LNR、LRN、NRL、RNL和LNR。研究二叉树的遍历就是研究这6种具体的遍历方案，显然根据简单的对称性，左子树和右子树的遍历可互换，即NLR与NRL、LNR与RNL、LRN与RLN，分别相类似，因而只需研究NLR、LNR和LRN三种即可，分别称为“先序遍历”、“中序遍历”和“后序遍历”。

![这里写图片描述][20151012222610579]  
各种形式遍历输出的结果为：

先序：ABCDEGF
    
                中序：CBEGDFA
    
                后序：CGEFDBA

代码

int main(int argc, char* argv[])
    {
        BiTreeNode *proot=NULL;
        printf("InOrder input chars to create a BiTree: ");
        proot=createBiTreePreOrder();  //输入(ABC  DE G  F   )
        printf("PreOrder Output the BiTree recursively: ");
        traverseBiTreePreOrder(proot,putchar);
        printf("\n");
        printf("PreOrder Output the BiTree non-recursively: ");
        traverseBiTreePreOrder2(proot,putchar);
        printf("\n");
        printf("InOrder Output the BiTree recursively: ");
        traverseBiTreeInOrder(proot,putchar);
        printf("\n");
        printf("InOrder Output the BiTree non-recursively(1): ");
        traverseBiTreeInOrder2(proot,putchar);
        printf("\n");
        printf("InOrder Output the BiTree non-recursively(2): ");
        traverseBiTreeInOrder3(proot,putchar);
        printf("\n");
        printf("PostOrder Output the BiTree non-recursively: ");
        traverseBiTreePostOrder(proot,putchar);
        printf("\n");
        printf("PostOrder Output the BiTree recursively: ");
        traverseBiTreePostOrder2(proot,putchar);
        printf("\n");
        return 0;
    }

[20151012221226464]: /images/20220731/706a5d8635a14a63b0ddadb75bc91e78.png
[909995_1420569532126_2.png]: /images/20220731/c1dcd3556db44ba4885f37d91fb0442e.png
[20151012222610579]: /images/20220731/f20bb0ab61354a53894018c03e996d63.png