树是 n（n ≥ 0）个节点的有限集。当 n = 0 时，称为空树。在任意一棵非空树中应满足：1）有且仅有一个特定的称为根的结点。2）当 n > 1 时，其余节点可分为 m（m > 0）个互不相交的有限集 $T_1,T_2,…, T_m$，其中每个集合本身又是一棵树，并且称为根的子树。以下为我在学习和实战练习过程中所做的笔记，可供参考。
一、树和二叉树的结构
数据结构可视化参考：Data Structure Visualizations。
树作为—种逻辑结构，同时也是一种分层结构，具有以下两个特点：1）树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。2）树中所有结点可以有零个或多个后继。
二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。与树相似，二叉树也以递归的形式定义。二叉树是 n（n ≥ 0）个结点的有限集合：①或者为空二叉树，即 n = 0。②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
树结点数据结构：
1
2
3
4
5
6
7
8
9
10
11
| 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;
|
二、二叉树的建树（层次建树）
层次建树的操作：
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
| int main()
{
BiTree pnew;
int i,j,pos;
char c;
BiTree tree=NULL;
ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
while(scanf("%c",&c)!=EOF)
{
if(c=='\n')
{
break;
}
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;
continue;
}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;
}
}
printf("--------前序遍历----------\n");
preOrder(tree);
printf("\n--------中序遍历------------\n");
InOrder(tree);
printf("\n--------后序遍历------------\n");
PostOrder(tree);
printf("\n--------中序遍历非递归------\n");
InOrder2(tree);
printf("\n--------层次遍历-----------\n");
LevelOrder(tree);
printf("\n");
system("pause");
}
|
三、二叉树的遍历
递归实现：
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
|
void preOrder(BiTree p)
{
if(p!=NULL)
{
putchar(p->c);
preOrder(p->lchild);
preOrder(p->rchild);
}
}
void InOrder(BiTree p)
{
if(p!=NULL)
{
InOrder(p->lchild);
putchar(p->c);
InOrder(p->rchild);
}
}
void PostOrder(BiTree p)
{
if(p!=NULL)
{
PostOrder(p->lchild);
PostOrder(p->rchild);
putchar(p->c);
}
}
void InOrder2(BiTree T)
{
SqStack S;
InitStack(S);BiTree p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}else{
Pop(S,p);putchar(p->c);
p=p->rchild;
}
}
}
void LevelOrder(BiTree T)
{
LinkQueue Q;
InitQueue(Q);
BiTree p;
EnQueue(Q,T);
while(!IsEmpty(Q))
{
DeQueue(Q,p);
putchar(p->c);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
|
上方所用到的栈和队列相关数据结构：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#define MaxSize 50
typedef BiTree ElemType;
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack &S);
bool Push(SqStack &S,ElemType x);
bool Pop(SqStack &S,ElemType &x);
bool GetTop(SqStack &S,ElemType &x);
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue;
void InitQueue(LinkQueue &Q);
bool IsEmpty(LinkQueue Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &x);
|