二叉树

为什么需要二叉树

因为要模拟递归。

编程是在干嘛？

编程是在管理数据，问题在于怎么个管理法。管理着管理着就发现原来管理本身就是数据。
写代码的过程就是一个递归的过程:

function coding(){
   if (NoError){
       done
   } else {
       coding(change_some_codes)
   }
 }

所以我喜欢git这种东西，这是在模拟人在编码过程中不断后退重来的困境。

二叉树实现（c）

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
#include <stdio.h>
#include <stdlib.h>

typedef int Status;
typedef struct {
    void *data;
    struct BinaryTreeNode *Lchild;
    struct BinaryTreeNode *Rchild;
} BinaryTreeNode;

typedef BinaryTreeNode *BinaryTree;

/**
 * 初始化
 * @param T 
 */
void init_binaryTree(BinaryTree *T);

/**
 * 创建
 * @param T 
 * @return 
 */
Status create_binaryTree(BinaryTree *T);

/**
 * 打印
 * @param e 
 * @return 
 */
Status print_element(void *e);

/**
 * 遍历
 * @param T 
 * @param visit 
 * @return 
 */
Status traverse(BinaryTree T, Status (*visit)(void *));

/**
 * 复制
 * @param T 
 * @param newT 
 */
void copy(BinaryTree T, BinaryTree *newT);

/**
 * 深度
 * @param T 
 * @return 
 */
int depth(BinaryTree T);

/**
 * 节点个数
 * @param T 
 * @return 
 */
int count_node(BinaryTree T);


void init_binaryTree(BinaryTree *T) {
    *T = NULL;
}

Status create_binaryTree(BinaryTree *T) {
    char ch;
    scanf(&ch);

    if (ch == '^') {
        *T = NULL;
    } else {
        *T = (BinaryTree) malloc(sizeof(BinaryTree));
        if (!(*T))
            exit(-1);
        (*T)->data = (void *) ch;
        create_binaryTree(&(*T)->Lchild);
        create_binaryTree(&(*T)->Rchild);
    }

    return 0;
}

Status print_element(void *e) {
    printf(e);
    return 0;
}

Status traverse(BinaryTree T, Status (*visit)(void *)) {
    if (T) {
        if (visit(T->data)) {
            if (traverse(T->Lchild, visit)) {
                if (traverse(T->Rchild, visit)) {
                    return 0;
                }
            }
        } else
            return -1;
    } else {
        return 0;
    }
}

void copy(BinaryTree T, BinaryTree *newT) {
    if (T == NULL) {
        (*newT) = NULL;
        return;
    } else {
        (*newT) = (BinaryTree) malloc(sizeof(BinaryTreeNode));
        (*newT)->data = T->data;
        copy(T->Lchild, (*newT)->Lchild);
        copy(T->Rchild, (*newT)->Rchild);
    }
}

int depth(BinaryTree T) {
    int m, n;

    if (T == NULL)
        return 0;
    else {
        m = depth(T->Lchild);
        n = depth(T->Rchild);

        if (m > n)
            return m + 1;
        else
            return n + 1;
    }
}

int count_node(BinaryTree T) {
    if (T == NULL) {
        return 0;
    } else {
        return count_node(T->Lchild) + count_node(T->Rchild) + 1;
    }
}