树的基本操作(数据结构)

树的创建

//结构结点 
typedef struct Node
{
	int data;
	struct Node *leftchild;
	struct Node *rightchild;
}*Bitree,BitNode;

//初始化树 
void Create(Bitree &T)
{
	int d;
	printf("输入结点(按0为空结点):");
	scanf("%d",&d);
	if(d!=0)
	{
		T = (Bitree)malloc(sizeof(BitNode));
		T->data=d;
		Create(T->leftchild);
		Create(T->rightchild);
	}
	else{
		T=NULL;
		return;
	}
}
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

遍历树(递归)

//先序遍历 
void PreOrder(Bitree &T)
{
	Bitree D;
	D=T;
	if (D)
	{
		printf("%d", D->data);
		PreOrder(D->leftchild);
		PreOrder(D->rightchild);
	}
}

//中序遍历
void InOrder(Bitree &T)
{
	Bitree D;
	D=T;
	if (T)
	{
		InOrder(D->leftchild);
		printf("%d", D->data);
		InOrder(D->rightchild);
	}
 }
 
//后序遍历
void PostOrder(Bitree &T)
{
	Bitree D;
	D=T;	
	if (T)
	{
		PostOrder(D->leftchild);
		PostOrder(D->rightchild);
		printf("%d", D->data);
	}
}
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

非递归遍历

#define MaxSize 100
typedef struct{
	BitNode *data[MaxSize];
	int top;
}SqStack;

//初始化栈
void InitStack(SqStack &S){
	S.top = -1;
} 

//判断栈空
bool StackEmpty(SqStack S){
	if(S.top==-1) return true;//空栈
	else return false; 
} 

//进栈
void Push(SqStack &S, BitNode *x){
	if(S.top==MaxSize-1) return;//满栈
	S.top = S.top+1;//指针加1
	S.data[S.top]=x;//新元素入栈  
} 

//出栈
BitNode* Pop(SqStack &S){
	if(S.top==-1) return NULL;//空栈
	BitNode *x;
	x= S.data[S.top];
	S.top = S.top-1; 
	return x;
} 
//非递归遍历
void InOrder2(Bitree &T){
	SqStack S;
	InitStack(S);//初始化栈 
	Bitree P=T;//p是遍历指针 
	while(P||!StackEmpty(S)){
		if(P){//一路向左 
			Push(S,P);//当前结点入栈 
			P=P->leftchild;//左孩子不为空，一直向左走 
		} 
		else{
			P=Pop(S);//出栈，并转向右子树 
			printf("%d",P->data);//输出出栈元素 
			P=P->rightchild;//向右子树走 
		}
	}
}

void PreOrder2(Bitree &T){
	SqStack S;
	InitStack(S);//初始化栈 
	Bitree P=T;//p是遍历指针 
	while(P||!StackEmpty(S)){
		if(P){//一路向左 
			printf("%d",P->data);
			Push(S,P);//当前结点入栈 
			P=P->leftchild;//左孩子不为空，一直向左走 
		} 
		else{
			P=Pop(S);
			P=P->rightchild; 
		}
	}
}
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

层次遍历

#define MaxSize 100
typedef struct{
	int front,rear;
	BitNode *data[MaxSize];
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
	Q.front=Q.rear=0;
} 

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
	if(Q.front==Q.rear) return true;//空队列
	else return false; 
}

//入队
bool EnQueue(SqQueue &Q,BitNode *x){
	if((Q.rear+1)%MaxSize==Q.front){//判断队满
		return false; 
	}
	Q.data[Q.rear]=x;//新元素入队 
	Q.rear = (Q.rear+1)%MaxSize;//队尾指针加一取模 让队列循环使用 
	return true;
} 

//出队
BitNode* DeQueue(SqQueue &Q){
	if(Q.front==Q.rear) return NULL;//队列为空 
	BitNode *x;
	x = Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;//对头指针后移 
	return x;
} 

//层次遍历
void LevelOrder(Bitree &T){
	SqQueue Q;
	InitQueue(Q);
	Bitree P;
	EnQueue(Q,T);
	while(!QueueEmpty(Q)){
		P=DeQueue(Q);
		printf("%d ",P->data);
		if(P->leftchild!=NULL)
			EnQueue(Q,P->leftchild);
		if(P->rightchild!=NULL)
			EnQueue(Q,P->rightchild);
	}
} 
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 T;
	Create(T);
	printf("前序遍历:");
	PreOrder(T);
	printf("\n");
	printf("中序遍历:");
	InOrder(T);
	printf("\n");
	printf("后序遍历:");
	PostOrder(T);
	printf("\n");
	
	printf("中序遍历(非):");
	InOrder2(T);
	printf("\n");
	printf("前序遍历(非):"); 
	PreOrder2(T);
	printf("\n");
	
	printf("层次遍历:");
	LevelOrder(T);
	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