二叉树递归遍历

二叉树模型

　　编写简单的程序对下图二叉树进行遍历

实现方式

二叉树结点

typedef struct BINARYNODE{
    char ch;
    struct BINARYNODE* lchild;
    struct BINARYNODE* rchild;
}BinaryNode;

遍历方式

先序遍历

    //先访问根节点
    printf("%c", root->ch);
    //再遍历左子树
    Recursion(root->lchild);
    //再遍历右子数
    Recursion(root->rchild);

中序遍历

    //再遍历左子树
    Recursion(root->lchild);
    //先访问根节点
    printf("%c", root->ch);
    //再遍历右子数
    Recursion(root->rchild);

后序遍历

    //再遍历左子树
    Recursion(root->lchild);
    //再遍历右子数
    Recursion(root->rchild);
    //先访问根节点
    printf("%c", root->ch);

递归遍历

    Recursion(&node1);

创建结点

    //创建结点
    BinaryNode node1 = { 'A',NULL,NULL };
    BinaryNode node2 = { 'B',NULL,NULL };
    BinaryNode node3 = { 'C',NULL,NULL };
    BinaryNode node4 = { 'D',NULL,NULL };
    BinaryNode node5 = { 'E',NULL,NULL };
    BinaryNode node6 = { 'F',NULL,NULL };
    BinaryNode node7 = { 'G',NULL,NULL };
    BinaryNode node8 = { 'H',NULL,NULL };

建立结点关系

    //建立结点关系
    node1.lchild = &node2;
    node1.rchild = &node6;
    node2.rchild = &node3;
    node3.lchild = &node4;
    node3.rchild = &node5;
    node6.rchild = &node7;
    node7.lchild = &node8;

运行结果

先序遍历

中序遍历

后序遍历

源码

main.c

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdlib.h>
 4 #include<stdio.h>
 5 #include<string.h>
 6 
 7 //二叉树结点
 8 typedef struct BINARYNODE{
 9     char ch;
10     struct BINARYNODE* lchild;
11     struct BINARYNODE* rchild;
12 }BinaryNode;
13 
14 //递归函数
15 void Recursion(BinaryNode* root)
16 {
17     if (root == NULL)
18         return;
19     //先访问根节点
20     printf("%c", root->ch);
21     //再遍历左子树
22     Recursion(root->lchild);
23     //再遍历右子数
24     Recursion(root->rchild);
25 }
26 
27 //创建二叉树结点
28 void CreateBinaryTree()
29 {
30     //创建结点
31     BinaryNode node1 = { 'A',NULL,NULL };
32     BinaryNode node2 = { 'B',NULL,NULL };
33     BinaryNode node3 = { 'C',NULL,NULL };
34     BinaryNode node4 = { 'D',NULL,NULL };
35     BinaryNode node5 = { 'E',NULL,NULL };
36     BinaryNode node6 = { 'F',NULL,NULL };
37     BinaryNode node7 = { 'G',NULL,NULL };
38     BinaryNode node8 = { 'H',NULL,NULL };
39 
40     //建立结点关系
41     node1.lchild = &node2;
42     node1.rchild = &node6;
43     node2.rchild = &node3;
44     node3.lchild = &node4;
45     node3.rchild = &node5;
46     node6.rchild = &node7;
47     node7.lchild = &node8;
48 
49     //递归遍历
50     Recursion(&node1);
51     printf("
");
52 }
53 
54 int main()
55 {
56     CreateBinaryTree();
57     return 0;
58 }