当前位置:   article > 正文

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

写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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/1015391
推荐阅读
相关标签
  

闽ICP备14008679号