《数据结构》二叉树 —— 二叉树的建立和遍历

| |

前言：《数据结构》作为计算机专业的一门重点学科，无论是将来考研、就业，对其的考察都是重中之重，之前的文章已经对此进行过论述。作为考察程序员“编程能力”的一种方式，考验的是我们如何将数据结构的思想用编程语言精确的编码出来。所有的《数据结构》课本都详细的讲解了每一种数据结构和算法的思想，然后给出具体的编程语言代码或者伪代码。算法思想只要认真看书，还是比较容易掌握的 ，真正考验我们的，是从算法思想到具体编码的这个思考过程，就是思考如何编码实现，这个过程是逃不掉的，除非参考别人的现有代码，但一段时间过后一定会忘记（百分之百的，我就忘记了无数次了）。所以，尽量在编程实现前，自己有个清晰的思路，尝试着自己去实现。

代码

代码托管在github ，需要的可以下载或者直接复制代码运行，只有一个cpp文件。已经通过测试，完全没有问题。这里重点是实现算法思想，所以没有考虑代码的健壮性，没有异常处理。

定义二叉树的节点

1
2
3
4
5
6
7
8
struct Node
{
    int value;
    struct Node *left_node;
    struct Node *right_node;
};
typedef struct Node TNode;    //定义二叉树节点 (方式一)
typedef TNode *BTree;    //定义二叉树链表（方式二）

二叉树的节点定义很简单，采用结构体，一个数据域和两个指针域。但有一个问题是让我不解的，就是为什么在typedef时要采用两种方式，而且我看过的所有课本中，无一例外的都采用了这两种方式（在链表的定义中也是如此）。我试验只采用第一种，完全没任何问题。我去网上搜索，也没人给出答案。看到这篇文章的同学，如果知道的话，希望在简书留言告诉我！

二叉树的建立

思路：一般的题目中，都是直接告诉我们有一棵二叉树，直接让我们进行各种遍历，让我们从零创建一棵树的还真不多见。仔细想想，思路还真不是那么清晰。如果说给我们两种遍历的结果，让我们反推这棵树，那结果是唯一的。但直接给我们一个数组，让我们创建一棵二叉树，那创建的方式太多了，一时还真没啥思路。不过翻看了一本书，书中给了一种创建过程，他采用的原则是“小于父节点的值放在左子树，大于父节点的值放在右子树”。但是，让我困惑的是，他说“建立二叉树必须遵守这个原则”，我怎么从来没听说过这个原则？？？这个先不管了，不过这是创建二叉树的一种方式，总算有个可以依据的原则，接下来就创建吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
void Add_Node(int value)
{
    /*定义需要用到的变量*/
    TNode *newNode;        //待插入的新节点
    BTree currentNode;        //临时的指针
    int flag = 0;        //记录是否插入了新的节点
    newNode = (TNode *)malloc(sizeof(TNode));        //为新节点分配空间并输入内容
    newNode->value = value;
    newNode->left_node = NULL;
    newNode->right_node = NULL;
    /*将新节点插入二叉树*/
    if(bTree == NULL)
        bTree = newNode;
    else
    {
        currentNode = bTree;
        while(!flag)        //循环结束的时刻是：flag=1，即节点已被插入
        {
            if(value<currentNode->value)
            {
                if(currentNode->left_node==NULL)
                {
                    currentNode->left_node=newNode;
                    flag=1;
                }
                else
                    currentNode=currentNode->left_node;
            }
            else
            {
                if(currentNode->right_node==NULL)
                {
                    currentNode->right_node=newNode;
                    flag=1;
                }
                else
                    currentNode=currentNode->right_node;
            }
        }
    }
}
int main()
{
    int content[ArraySize];
    cout<<"请输入6个整数："<<endl;    //输入数据
    for(int i=0;i<ArraySize;i++)
        cin>>content[i];
    for(i=0;i<ArraySize;i++)    //建树
        Add_Node(content[i]);
    return 0;
}

三种遍历方式(递归&非递归)

直接上代码吧，注释还比较详细。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
void Preorder(BTree bTree)        //递归前序遍历
{
    if(bTree!=NULL)
    {
        cout<<bTree->value<<" ";
        Preorder(bTree->left_node);
        Preorder(bTree->right_node);
    }
}
void Preorder2(BTree bTree)        //非递归前序遍历
{
    /*定义需要用到的变量*/
    BTree stack[ArraySize];        //用数组来充当栈
    int top=0;        //top变量来充当栈顶指针，top为0说明栈空
    BTree p=bTree;
    while(p||top!=0)
    {
        if(p)
        {
            cout<<p->value<<" ";
            stack[top++]=p;
            p=p->left_node;
        }
        else
        {
            p=stack[--top];        //注意这里是“--top”
            p=p->right_node;
        }
    }
}
void Inorder(BTree bTree)        //递归中序遍历
{
    if(bTree!=NULL)
    {
        Inorder(bTree->left_node);
        cout<<bTree->value<<" ";
        Inorder(bTree->right_node);
    }
}
void Inorder2(BTree bTree)        //非递归中序遍历
{
    /*定义需要用到的变量*/
    BTree stack[ArraySize];        //用数组来充当栈
    int top=0;        //top变量来充当栈顶指针，top为0说明栈空
    BTree p=bTree;
    while(p||top!=0)    //举例：建立一个只有三个节点的二叉树发现，当p的指向为空，且top=0的时候，所有的元素都已经遍历过了
    {
        if(p)
        {
            stack[top++]=p;
            p=p->left_node;
        }
        else    //举例发现，当p指向为空时，就要执行出战操作，然后输出元素
        {
            p=stack[--top];        //注意这里是“--top”
            cout<<p->value<<" ";
            p=p->right_node;
        }
    }
}
void Postorder(BTree bTree)        //递归后序遍历
{
    if(bTree!=NULL)
    {
        Postorder(bTree->left_node);
        Postorder(bTree->right_node);
        cout<<bTree->value<<" ";
    }
}
void Postorder2(BTree bTree)        //非递归后序遍历
{
    BTree stack1[ArraySize];
    int stack2[ArraySize];
    int top1=0,top2=0;
    int flag;
    BTree p=bTree;
    while(p||top1!=0)
    {
        if(p)
        {
            stack1[top1++]=p;
            stack2[top2++]=0;
            p=p->left_node;
        }
        else
        {
            p=stack1[top1-1];       
            flag=stack2[top2-1];
            if(flag==0)
            {
                stack2[top2-1]=1;
                p=p->right_node;
            }
            else
            {
                p=stack1[--top1];
                --top2;
                cout<<p->value<<" ";
                p=NULL;        //这一句很关键，调试了一上午，问题就是没有加上这一句。
            }
        }
    }
}