树
树是n（n>=0）个节点的有限集。当n=0时，称为空树。在任意一棵非空树应满足：
- 有且仅有一个特定的称为根的结点。
- 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、…、T_m，其中每个集合本身又是一棵树，并且称为根的子树。
1
2
3
4
5
6
| typedef char BiElemType;
typedef struct BiTNode{
BiElemType c;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*BiTree;
|
二叉树
一般用链式存储实现
二叉树树一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。二叉树是n（n>=0）个结点的有限集合：
- 或者为空二叉树，即n=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
| typedef char BiElemType;
typedef struct BiTNode {
BiElemType c;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
typedef struct tag {
BiTree p;
struct tag *pnext;
} tag_t, *ptag_t;
int main() {
BiTree pnew;
BiTree tree = NULL;
ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur = NULL;
char c;
while (scanf("%c", &c) && c != '\n') {
pnew = (BiTree) calloc(1, sizeof(BiTNode));
pnew->c = c;
listpnew = (ptag_t) calloc(1, sizeof(tag_t));
listpnew->p = pnew;
if (NULL == tree) {
tree = pnew;
phead = listpnew;
ptail = listpnew;
pcur = listpnew;
} else {
ptail->pnext = listpnew;
ptail = listpnew;
if (NULL == pcur->p->lchild) {
pcur->p->lchild = pnew;
} else if (NULL == pcur->p->rchild) {
pcur->p->rchild = pnew;
pcur = pcur->pnext;
}
}
}
PreOrder(tree);
printf("\n----------\n");
InOrder(tree);
printf("\n----------\n");
PostOrder(tree);
return 0;
}
|
前序遍历（深度优先遍历）
优先访问根结点然后左结点、右结点
1
2
3
4
5
6
7
| void PreOrder(BiTree p) {
if (p) {
printf("%c", p->c);
PreOrder(p->lchild);
PreOrder(p->rchild);
}
}
|
中序遍历
优先访问左结点然后根结点、右结点
1
2
3
4
5
6
7
| void InOrder(BiTree p){
if(p){
InOrder(p->lchild);
printf("%c", p->c);
InOrder(p->rchild);
}
}
|
后序遍历
优先访问左结点然后右结点、根结点
1
2
3
4
5
6
7
| void PostOrder(BiTree p){
if(p){
PostOrder(p->lchild);
PostOrder(p->rchild);
printf("%c",p->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
| typedef BiTree ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode;
typedef struct {
LNode *front;
LNode *rear;
} LQueue;
bool IsEmpty(LQueue q) {
return q.front == q.rear;
}
void EnQueue(LQueue &q, ElemType e) {
LNode *p = (LNode *) malloc(sizeof(LNode));
p->data = e;
q.rear->next = p;
q.rear = p;
p->next = NULL;
}
bool DeQueue(LQueue &q, ElemType &e) {
if (IsEmpty(q)) {
return false;
}
LNode *p = q.front->next;
e = p->data;
q.front->next = p->next;
if (q.rear == p) {
q.rear = q.front;
}
free(p);
return true;
}
void LevelOrder(BiTree t) {
LQueue q;
InitQueue(q);
BiTree p;
EnQueue(q, t);
while (!IsEmpty(q)) {
DeQueue(q, p);
putchar(p->c);
if (p->lchild) {
EnQueue(q, p->lchild);
}
if (p->rchild) {
EnQueue(q, p->rchild);
}
}
}
|
