二叉木の非再帰遍歴C言語版

作者:Slyar文章来源:Slyar Home(www.slyar.com)転載ご明記ください.ご協力ありがとうございます.
先周のデータ构造の授业は二叉木の遍歴を言って、先生は再帰アルゴリズムだけを言って、技术の含有量がなくて、自分で非再帰アルゴリズムを考えて実现します...
前順ループ:ルートノードにアクセスしてから左サブツリーにアクセスし、最後に右サブツリーにアクセスします.スタックを設定します.スタックを出るとアクセスノードになります.まずルートノードをスタックに入れ、スタックが空でないときは、スタックを出て、アクセスして、右の子供をスタックに入れて、左の子供をスタックに入れます.
中順遍歴:左サブツリーにアクセスし、ルートノードにアクセスし、最後に右サブツリーにアクセスします.スタックを設定します.スタックを出るとアクセスノードになります.ルートノードの左ノードをすべてスタックに入れてから、ノードをスタックしてアクセスします.ノードの右の子ノードをスタックに入れ、右の子ノードのすべての左ノードをスタックに入れます...こうして桟が空くまで.
後順ループ:左サブツリーにアクセスしてから右サブツリーにアクセスし、最後にルートノードにアクセスします.スタックを設定します.まず、ルートノードの左ノードをすべてスタックに入れます.1つのノードをスタックして、そのノードの右の子供をスタックに入れて、右の子供の左のノードをすべてスタックに入れます...ノードの左、右の子供がアクセスされた後、スタックが空になるまでノードにアクセスします.(ノードの右の子がアクセスされているかどうかを判断するには、アクセスしたばかりのノードを追跡するポインタを個別に設定する必要があります.後のループでは、ノードの右の子ノードがノードの直前にアクセスされているに違いありません)
コードの重点は非再帰遍歴であるため,二叉木を構築する過程で「前順再帰」を用いた.空のノードを「#」で表すツリーの場合、前の順序でツリーを再帰的に作成するために必要な入力データは、前の順序で遍歴する順序と同じであり、各リーフノードの左右の子供は「#」である.
入力:ABDH##I##EJ##K##CF#L##G##前順遍歴:A B D H I E J K C F L G中順遍歴:H D I B J E K A F L C G後順遍歴:H I D J K E B L G C A
コードは次のとおりです.

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

/*
Slyar
http://www.slyar.com
2009.5.16
*/
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 200

/*           */
typedef struct node
{
    char data;
    struct node *lchild, *rchild;
}BTNode;

/*      */
BTNode* CreatBitTree();
void PreOrder(BTNode*);
void InOrder(BTNode*);
void PostOrder(BTNode*);

/*     */
int main()
{
    BTNode *root = NULL;
    root = CreatBitTree();
    PreOrder(root);
    InOrder(root);
    PostOrder(root);
    system("pause");
    return 0;
}

/*           */
BTNode* CreatBitTree()
{
    char ch;
    BTNode *b;
    scanf("%c", &ch);
    /*           */
    if (ch == '#')
    {
        b = NULL;
    }
    else
    {
        b = (BTNode*) malloc(sizeof(BTNode));
        /*       */
        b->data = ch;
        /*           */
        b->lchild = CreatBitTree();
        /*           */
        b->rchild = CreatBitTree();
    }
    return b;
}

/*            */
void PreOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int top = -1;
    if (b != NULL)
    {
        /*       */
        top++;
        stack[top] = b;
        /*        */
        while (top > -1)
        {
            /*          */
            p = stack[top];
            top--;
            printf("%c ", p->data);
            /*       */
            if (p->rchild != NULL)
            {
                top++;
                stack[top] = p->rchild;
            }
            /*       */
            if (p->lchild != NULL)
            {
                top++;
                stack[top] = p->lchild;
            }
        }
        printf("/n");
    }
}

/*            */
void InOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int top = -1;
    if (b != NULL)
    {
        p = b;
        while (top > -1 || p != NULL)
        {
            /*   p          */
            while (p != NULL)
            {
                top++;
                stack[top] = p;
                p = p->lchild;
            }
            if (top > -1)
            {
                /*          */
                p = stack[top];
                top--;
                printf("%c ", p->data);
                /*   p     */
                p = p->rchild;
            }
        }
        printf("/n");
    }
}

/*            */
void PostOrder(BTNode* b)
{
    BTNode *stack[MAXSIZE], *p;
    int sign, top = -1;
    if (b != NULL)
    {
        do
        {
            /* b        */
            while (b != NULL)
            {
                top++;
                stack[top] = b;
                b = b->lchild;
            }
            /* p             */
            p = NULL;
            /*  b     */
            sign = 1;
            while (top != -1 && sign)
            {
                /*        */
                b = stack[top];
                /*                 b */
                if (b->rchild == p)
                {
                    printf("%c ", b->data);
                    top--;
                    /* p         */
                    p = b;
                }
                else
                {
                    /* b        */
                    b = b->rchild;
                    /*        */
                    sign = 0;
                }
            }
        }while (top != -1);
        printf("/n");
    }
}