二叉树各类算法实现_写c语言程序,创建一个具有十个节点的完全二叉树 要求:先定义二叉树的节点,该程序

数据结构----二叉树各类算法实现

二叉树的各类算法设计实现

主要功能：
① 建立不少于10个结点的二叉树T；
② 用非递归方式先序遍历方式输出树T的结点；
③ 用非递归方式中序遍历方式输出树T的结点；
④ 用后序遍历方式输出树T的结点；
⑤ 用层次遍历方式输出树T的结点；
⑥ 输出树T的深度；
⑦ 输出树T的叶子结点和非叶子结点；

测试数据说明：
以完全二叉树的方式从左到右，从上到下，输入数据，数据为0表示对应没有结点，指针为空
1 5 8 0 9 0 10 0 0 54 3 0 0 9 -1 //二叉树的数据，以-1结尾

测试案例
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 -1

> 输出案例
> The tree is:
         --6
              --14
                     --7
       --18
                     --8
              --15
                     --9
--20
                     --10
              --16
                     --11
       --19
                            --2
                     --12
                            --3
              --17
                            --4
                     --13
                            --5
The result of  PreOrder traversal not recursion:
20 19 17 13 5 4 12 3 2 16 11 10 18 15 9 8 14 7 6
The result of  InOrder traversal not recursion:
5 13 4 17 3 12 2 19 11 16 10 20 9 15 8 18 7 14 6
The result of recursion PostOrder traversal:
5 4 13 3 2 12 17 11 10 16 19 9 8 15 7 6 14 18 20
The result of level traversal:
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
The deepth of the tree is: 4
All the leaves of the tree after sorting:
2 3 4 5 6 7 8 9 10 11
All the not leaves of the tree after sorting:
12 13 14 15 16 17 18 19 20
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

BiTree.h

#ifndef BITREE_H
#define BITREE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int ItemType;

//二叉树结点结构定义
typedef struct TreeNode
{
	ItemType data;
	struct	TreeNode* leftChild;
	struct TreeNode* rightChild;
	
}BiTreeNode; 

void CreateTree(BiTreeNode** root,int i, ItemType d[], int n);  
void PreOrder(BiTreeNode* root,ItemType data[], int* n);
void InOrder(BiTreeNode* root,ItemType data[], int* n);
void PostOrder(BiTreeNode* root, ItemType data[], int* n);
void LevelorderTraverse(BiTreeNode  *root,ItemType data[], int* n);
int  Deepth(BiTreeNode  *root);
void GetLeaves(BiTreeNode  *root,ItemType leaves[], int* n);
void GetNotLeaves(BiTreeNode  *root,ItemType notleaves[], int* n);
void PrintTree(BiTreeNode *root,int n);
void FreeTree(BiTreeNode** root);
#endif

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

SeqCQueue.h

#ifndef SEQCQUEUE_H
#define SEQCQUEUE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BiTree.h"

#define MaxQueueSize 100
typedef BiTreeNode* QDataType;

//顺序循环队列的结构体
typedef struct Queue
{ 
	QDataType queue[MaxQueueSize];
	int rear;  //队尾指针
	int front;  //队头指针
	int count;  //计数器
} SeqCQueue; 

void QueueInitiate(SeqCQueue *Q);

int QueueNotEmpty(SeqCQueue Q);

int QueueAppend(SeqCQueue *Q, QDataType x);

int QueueDelete(SeqCQueue *Q, QDataType *d);

int QueueGet(SeqCQueue Q, QDataType *d);

#endif

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

SeqStack.h

#ifndef SEQSTACK_H
#define SEQSTACK_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BiTree.h"

#define MaxStackSize 100
typedef BiTreeNode* DataType;

//顺序堆栈结构体定义
typedef struct
{	DataType stack[MaxStackSize];			
	int top;
} SeqStack;


void StackInitiate(SeqStack *S);	

int StackNotEmpty(SeqStack*S);

int StackPush(SeqStack *S, DataType x);

int StackPop(SeqStack *S, DataType *d);

int StackTop(SeqStack S, DataType *d);

#endif

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

SeqCQueue.c

#include "SeqCQueue.h"

//初始化QueueInitiate(Q)
void QueueInitiate(SeqCQueue *Q)
{
	Q->rear = 0;		
	Q->front = 0;
	Q->count = 0;
}


//判断循环队列Q非空否，非空则返回1，否则返回0
int QueueNotEmpty(SeqCQueue Q)
{
	if(Q.count != 0)	return 1;
	else return 0;
}


//把数据元素值x插入顺序循环队列Q的队尾，成功返回0，失败返回-1
int QueueAppend(SeqCQueue *Q, QDataType x)
{
	if(Q->count > 0 && Q->rear == Q->front)
	{	
		printf("The queue is full!\n");
		return -1;
	}
	else
	{	
		Q->queue[Q->rear] = x;
		Q->rear = (Q->rear + 1) % MaxQueueSize;
		Q->count++;
		return 0;
	}
}


//删除顺序循环队列Q的队头元素并赋值给d，成功则返回0，失败返回-1
int QueueDelete(SeqCQueue *Q, QDataType *d)
{
	if(Q->count == 0)
	{	printf("The queue is empty!\n");
		return -1;
	}
	else
	{	*d = Q->queue[Q->front];
		Q->front = (Q->front + 1) % MaxQueueSize;
		Q->count--;
		return 0;
	}
}

//取队头数据元素 ,成功则返回0，失败返回-1
int QueueGet(SeqCQueue Q, QDataType *d)
{
	if(Q.count == 0)
	{
		printf("The queue is empty!\n");
		return -1;
	}
	else
	{
		*d = Q.queue[Q.front];
		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
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

SeqStack.c

#include "SeqCQueue.h"

//初始化QueueInitiate(Q)
void QueueInitiate(SeqCQueue *Q)
{
	Q->rear = 0;		
	Q->front = 0;
	Q->count = 0;
}


//判断循环队列Q非空否，非空则返回1，否则返回0
int QueueNotEmpty(SeqCQueue Q)
{
	if(Q.count != 0)	return 1;
	else return 0;
}


//把数据元素值x插入顺序循环队列Q的队尾，成功返回0，失败返回-1
int QueueAppend(SeqCQueue *Q, QDataType x)
{
	if(Q->count > 0 && Q->rear == Q->front)
	{	
		printf("The queue is full!\n");
		return -1;
	}
	else
	{	
		Q->queue[Q->rear] = x;
		Q->rear = (Q->rear + 1) % MaxQueueSize;
		Q->count++;
		return 0;
	}
}


//删除顺序循环队列Q的队头元素并赋值给d，成功则返回0，失败返回-1
int QueueDelete(SeqCQueue *Q, QDataType *d)
{
	if(Q->count == 0)
	{	printf("The queue is empty!\n");
		return -1;
	}
	else
	{	*d = Q->queue[Q->front];
		Q->front = (Q->front + 1) % MaxQueueSize;
		Q->count--;
		return 0;
	}
}

//取队头数据元素 ,成功则返回0，失败返回-1
int QueueGet(SeqCQueue Q, QDataType *d)
{
	if(Q.count == 0)
	{
		printf("The queue is empty!\n");
		return -1;
	}
	else
	{
		*d = Q.queue[Q.front];
		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
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

BiTree.c

#include "BiTree.h"
#include "SeqStack.h"
#include "SeqCQueue.h"


//根据ItemType d[]的数据创建不带头结点的二叉树
void CreateTree(BiTreeNode** root,int i, ItemType d[], int n)
{
	if(i>=n||d[i]==0){  //数据是0，则表示没有此结点
	 	*root=NULL;
		return ;
	}
	*root =(BiTreeNode*)malloc(sizeof(BiTreeNode));
	(*root)->data=d[i];
	CreateTree(&((*root)->leftChild),2*i+1,d,n);
	CreateTree(&((*root)->rightChild),2*i+2,d,n);

}


//非递归先序遍历,遍历的数据放入数组data[ ]中带出函数外，n为数组元素的个数
void PreOrder(BiTreeNode* root,ItemType data[], int* n){
    SeqStack *stk;
    stk = (SeqStack*)malloc(sizeof(SeqStack));
    StackInitiate(stk);
    BiTreeNode *p=root;
    while (p || StackNotEmpty(stk)) {
    if(p) { 
			StackPush(stk, p);
			data[*n] = p->data;
			(*n)++;
			p = p->leftChild;
	}
	else
	{
		StackPop(stk, &p);
		p = p->rightChild;
	}
   }
}
//非递归中序遍历，遍历的数据放入数组data[]中带出函数外，n为数组元素的个数
void InOrder(BiTreeNode* root,ItemType data[], int* n){
	//填充代码
	SeqStack* stk;
	stk = (SeqStack*)malloc(sizeof(SeqStack));
	StackInitiate(stk);
	BiTreeNode *p = root;
	while (p || StackNotEmpty(stk)) {
		if (p) {
			StackPush(stk, p);
			p = p->leftChild;
		}
		else {
			StackPop(stk, &p);
			data[*n] = p->data;
			(*n)++;
			p = p->rightChild;
		}
	}	
}

//递归后序遍历二叉树,遍历的数据放入数组data[]中带出函数外，n为数组元素的个数
void PostOrder(BiTreeNode* root,ItemType data[], int* n)
{
    if (root->leftChild != NULL)
    {
		PostOrder(root->leftChild, data, n);
	}
	if (root->rightChild != NULL)
	{
		PostOrder(root->rightChild, data, n);
	}
	data[*n] = root->data;
	(*n)++;
	//printf("%d",p->data);
}

//层次遍历,遍历的数据放入数组data[]中带出函数外，n为数组元素的个数
void  LevelorderTraverse(BiTreeNode  *root, ItemType data[], int* n){  
	SeqCQueue *q;
	q = (SeqCQueue*)malloc(sizeof(SeqCQueue));
	QueueInitiate(q);
	BiTreeNode *pt =root;
	QueueAppend(q,pt);
	while (QueueNotEmpty(*q))
		{
			QueueDelete(q, &pt);
			data[*n]=pt->data;
			(*n)++;
			if (pt->leftChild != NULL)
				QueueAppend(q, pt->leftChild);
			if (pt->rightChild != NULL)
				QueueAppend(q, pt->rightChild);
		}   
}

//求树的深度，深度通过返回值带回函数外，注意：根的深度为0
int Deepth(BiTreeNode  *root){ 
	//填充代码
	int h1,h2;
	if(root == NULL){
		return -1;
	}
		h1 = Deepth(root->leftChild);
		h2 = Deepth(root->rightChild);
		if(h1>h2)
		{
			return h1+1;
		}
		else
		{
			 return h2+1;
		}
}
//得到所有叶子结点，叶子结点数据放入数组leaves[]带出函数外，n为数组元素的个数
void GetLeaves(BiTreeNode  *root,ItemType leaves[], int* n){

	//填充代码
	if(root!=NULL)
	{
	if(root->leftChild == NULL && root->rightChild == NULL)
	{
		leaves[*n]=root->data;
		(*n)++;
	}
	GetLeaves(root->leftChild, leaves, n);
	GetLeaves(root->rightChild, leaves, n);
	}	
}

//得到所有非叶子结点,非叶子结点数据放入数组notleaves[]带出函数外，n为数组元素的个数
void GetNotLeaves(BiTreeNode  *root, ItemType notleaves[], int* n){

	if(root!=NULL)
	{
	if(root->leftChild!= NULL || root->rightChild!= NULL)
	{
		notleaves[*n]=root->data;
		(*n)++;
	}
	GetNotLeaves(root->leftChild, notleaves, n);
	GetNotLeaves(root->rightChild, notleaves, n);
	}		
}

//打印二叉树
void PrintTree(BiTreeNode* root,int n){
	int i;
	if(root==NULL)return;
	PrintTree(root->rightChild,n+1);
	for(i=0;i<n;i++)printf("       ");
	if(n>=0){
		printf("--");
		printf("%d\n",root->data);
	}
	PrintTree(root->leftChild,n+1);
}


void FreeTree(BiTreeNode** root)
{
  if(*root==NULL)
   return ;
   FreeTree(&((*root)->leftChild));
   FreeTree(&((*root)->rightChild));
   free(*root);
   *root=NULL;
}

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
169

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BiTree.h"



/*
功能：
	主函数
	
参数：
	argc - argv 数组的长度，大小至少为 1，argc - 1 为命令行参数的数量。
	argv - 字符串指针数组，数组长度为命令行参数个数 + 1。其中 argv[0] 固定指向当前
	       所执行的可执行文件的路径字符串，argv[1] 及其后面的指针指向各个命令行参数。
	       例如通过命令行输入 "C:\hello.exe -a -b" 后，main 函数的 argc 的值为 3，
	       argv[0] 指向字符串 "C:\hello.exe"，argv[1] 指向字符串 "-a"，argv[2] 指向字符串 "-b"。

返回值:
	成功返回 0， 失败返回 1
*/
//用直接插入法对a[0]--a[n-1]排序
void InsertSort (ItemType a[], int n)

{
	int i, j;
	ItemType temp;
	for(i=0;  i<n-1; i++)
	{
		temp = a[i+1];
		j = i;
		while(j > -1 && temp <a[j])
		{
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = temp;
	}
}
int main(int argc, char* argv[])
{
	// 使用第一个参数输入待处理文件的名称，若没有输入此参数就报告错误
	if(argc < 2)
	{
		printf("Usage: app.exe filename\n");
		return 1;
	}
	
	// 打开待处理的文件。读取文件中的内容。
	FILE* file = fopen(argv[1], "rt");
	if(NULL == file)
	{
		printf("Can not open file \"%s\".\n", argv[1]);
		return 1;
	}
	
	int length=0;
	int data[100];
	 while(1){
	  fscanf(file,"%d",&data[length]);
	  if(data[length]==-1)
	   	 break;
	   length++;
	 }
	 
	BiTreeNode* root=NULL; 
	
	int n=0;
	CreateTree(&root,0, data, length) ;
	printf("The tree is:");
	printf("\n");
	PrintTree(root,0);
	n=0;
	PreOrder(root,data,&n);
	printf("The result of  PreOrder traversal not recursion:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	printf("\n");
	n=0;
	InOrder(root,data,&n);
	printf("The result of  InOrder traversal not recursion:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	printf("\n");
	n=0;
	PostOrder(root,data,&n);
	printf("The result of recursion PostOrder traversal:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	printf("\n");
	n=0;
	LevelorderTraverse(root, data,&n);
	printf("The result of level traversal:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	printf("\n");
	int deep=Deepth(root);
	printf("The deepth of the tree is: %d",deep);
	printf("\n");
	
	n=0;
	GetLeaves(root,data,&n);
	InsertSort(data, n);
	printf("All the leaves of the tree after sorting:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	printf("\n");	
	n=0;
	GetNotLeaves(root,data,&n);
	InsertSort(data, n);
	printf("All the not leaves of the tree  after sorting:");
	printf("\n");
	for(int i=0;i<n-1;i++)
	  printf("%d ",data[i]);
	printf("%d",data[n-1]);//单独打印最后一个数据，为了去掉最后一个空格
	
	FreeTree(&root);
	fclose(file);	
	
	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
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