龙空技术网

数据结构——树基本代码

小羊的Debug 181

前言:

当前我们对“数据结构实训代码”大约比较注意,各位老铁们都需要学习一些“数据结构实训代码”的相关资讯。那么小编也在网络上搜集了一些对于“数据结构实训代码””的相关资讯,希望看官们能喜欢,姐妹们一起来学习一下吧!

树的遍历

#include<stdio.h>#include<stdlib.h>#include<string.h>struct BiTNode{	int data;	struct BiTNode*lchild, *rchild; };typedef struct BiTNode BiTNode;typedef struct BiTNode* BiTree;void preOrder(BiTNode*root){	if (root == NULL)	{		return;	}	printf("%d", root->data);	preOrder(root->lchild);	preOrder(root->rchild);}void inOrder(BiTNode *root){	if (root == NULL)	{		return;	}	preOrder(root->lchild);	printf("%d", root->data);	preOrder(root->rchild);}void postOrder(BiTNode *root){	if (root == NULL)	{		return;	}	preOrder(root->lchild);	preOrder(root->rchild);	printf("%d", root->data);}void main(){	BiTNode t1, t2, t3, t4, t5;	memset(&t1, 0, sizeof(BiTNode));	memset(&t2, 0, sizeof(BiTNode));	memset(&t3, 0, sizeof(BiTNode));	memset(&t4, 0, sizeof(BiTNode));	memset(&t5, 0, sizeof(BiTNode));	t1.data = 1;	t2.data = 2;	t3.data = 3;	t4.data = 4;	t5.data = 5;	t1.lchild = &t2;	t1.rchild = &t3;	t2.lchild = &t4;	t3.lchild = &t5;	printf("preOrder\n");	preOrder(&t1);	printf("inOrder\n");	inOrder(&t1);	printf("postOrder\n");	postOrder(&t1);	printf("hello...\n");	system("pause");	return;}

求叶子节点个数

#include<stdio.h>#include<stdlib.h>#include<string.h>struct BiTNode{	int data;	struct BiTNode*lchild, *rchild; };typedef struct BiTNode BiTNode;typedef struct BiTNode* BiTree;void preOrder(BiTNode*root){	if (root == NULL)	{		return;	}	printf("%d", root->data);	preOrder(root->lchild);	preOrder(root->rchild);}void inOrder(BiTNode *root){	if (root == NULL)	{		return;	}	preOrder(root->lchild);	printf("%d", root->data);	preOrder(root->rchild);}void postOrder(BiTNode *root){	if (root == NULL)	{		return;	}	preOrder(root->lchild);	preOrder(root->rchild);	printf("%d", root->data);}int sum;void  coutLeaf(BiTNode *T,int *sum)//递归里的指针做函数参数{	if (T != NULL)	{		if (T->lchild == NULL&&T->rchild == NULL)		{			(*sum)++;		}		if (T->lchild)		{			coutLeaf(T->lchild,sum);		}		if (T->rchild)		{			coutLeaf(T->rchild,sum);		}	}}void main(){	BiTNode t1, t2, t3, t4, t5;	memset(&t1, 0, sizeof(BiTNode));	memset(&t2, 0, sizeof(BiTNode));	memset(&t3, 0, sizeof(BiTNode));	memset(&t4, 0, sizeof(BiTNode));	memset(&t5, 0, sizeof(BiTNode));	t1.data = 1;	t2.data = 2;	t3.data = 3;	t4.data = 4;	t5.data = 5;	t1.lchild = &t2;	t1.rchild = &t3;	t2.lchild = &t4;	t3.lchild = &t5;	{		int mysum = 0;		coutLeaf(&t1, &sum);		printf("sum:%d\n", sum);	}	printf("hello...\n");	system("pause");	return;}

求树的高度

#include<stdio.h>#include<stdlib.h>#include<string.h>struct BiTNode{	int data;	struct BiTNode*lchild, *rchild; };typedef struct BiTNode BiTNode;typedef struct BiTNode* BiTree;void inOrder(BiTNode *root){	if (root == NULL)	{		return;	}	inOrder(root->lchild);	printf("%d", root->data);	inOrder(root->rchild);}int  Depth(BiTNode* T){	int deptLeft = 0;	int deptRight = 0;	int deptval = 0;	if (T == NULL)	{		deptval = 0;		return  deptval;	}	deptLeft  = Depth(T->lchild);	deptRight = Depth(T->rchild);	deptval = 1 + (deptLeft > deptRight ? deptLeft : deptRight);	return deptval;}void main(){	BiTNode t1, t2, t3, t4, t5;	memset(&t1, 0, sizeof(BiTNode));	memset(&t2, 0, sizeof(BiTNode));	memset(&t3, 0, sizeof(BiTNode));	memset(&t4, 0, sizeof(BiTNode));	memset(&t5, 0, sizeof(BiTNode));	t1.data = 1;	t2.data = 2;	t3.data = 3;	t4.data = 4;	t5.data = 5;	t1.lchild = &t2;	t1.rchild = &t3;	t2.lchild = &t4;	t3.lchild = &t5;	printf("%d\n", Depth(&t1));	printf("inOrder\n");	inOrder(&t1);	printf("hello...\n");	system("pause");	return;}

树的拷贝

#include<stdio.h>#include<stdlib.h>#include<string.h>struct BiTNode{	int data;	struct BiTNode*lchild, *rchild; };typedef struct BiTNode BiTNode;typedef struct BiTNode* BiTree;void inOrder(BiTNode *root){	if (root == NULL)	{		return;	}	inOrder(root->lchild);	printf("%d", root->data);	inOrder(root->rchild);}int  Depth(BiTNode* T){	int deptLeft = 0;	int deptRight = 0;	int deptval = 0;	if (T == NULL)	{		deptval = 0;		return  deptval;	}	deptLeft  = Depth(T->lchild);	deptRight = Depth(T->rchild);	deptval = 1 + (deptLeft > deptRight ? deptLeft : deptRight);	return deptval;}BiTNode *CopyTree(BiTNode* T){	BiTNode *newNode = NULL;	BiTNode *newLp = NULL;	BiTNode *newRp = NULL;	if (T == NULL)//递归结束标志	{		return NULL;	}	if (T->lchild != NULL)	{		newLp = CopyTree(T->lchild);	}	else	{		newLp = NULL;	}	if (T->rchild != NULL)	{		newRp = CopyTree(T->rchild);	}	else	{		newRp = NULL;	}	newNode = (BiTNode*)malloc(sizeof(BiTNode));	if (newNode == NULL)	{		return  NULL;	}	newNode->lchild = newLp;	newNode->rchild = newRp;	newNode->data = T->data;	return newNode;}void main(){	BiTNode t1, t2, t3, t4, t5;	memset(&t1, 0, sizeof(BiTNode));	memset(&t2, 0, sizeof(BiTNode));	memset(&t3, 0, sizeof(BiTNode));	memset(&t4, 0, sizeof(BiTNode));	memset(&t5, 0, sizeof(BiTNode));	t1.data = 1;	t2.data = 2;	t3.data = 3;	t4.data = 4;	t5.data = 5;	t1.lchild = &t2;	t1.rchild = &t3;	t2.lchild = &t4;	t3.lchild = &t5;	printf("%d\n", Depth(&t1));	{		BiTNode *root = CopyTree(&t1);		printf("inorder\n");		inOrder(&t1);		printf("hello...\n");	}	system("pause");	return;}

#法创建树

BiTNode *CreateBiThrTree(){	BiTNode *node = NULL;	BiTNode *pL = NULL;	BiTNode *pR = NULL;	char h;	scanf("%c", &h);	if (h == '#')	{		return NULL;	}	else	{		node = (BiTNode*)malloc(sizeof(BiTNode));		memset(node, 0, sizeof(BiTNode));		node->data = h;		pL = CreateBiThrTree();		if (pL != NULL)		{			node->lchild = pL;		}		else		{			node->rchild = NULL;		}		pR = CreateBiThrTree();		if (pR != NULL)		{			node->rchild = pR;		}		else		{			node->rchild = NULL;		}	}	return node;}

二叉树线索化

Status  InOrderThreading(BiThrTree *Thrt, BiThrTree T){	*Thrt = (BiThrTree)malloc(sizeof(BiThrNode));	if (!*Thrt)		exit(OVERFLOW);	(*Thrt)->LTag = Link;	(*Thrt)->RTag = Thread;	(*Thrt)->rchild = (*Thrt);	if (!T)		(*Thrt)->lchild = *Thrt;	else	{		(*Thrt)->lchild = T;		pre = (*Thrt);		InThreading(T);		pre->rchild = *Thrt;		pre->RTag = Thread;		(*Thrt)->rchild = pre;	}	return OK;	}Status InOrderTraverse_Thr(BiThrTree T){	BiThrTree p;	p = T->lchild;	while (p != T)	{		while(p->LTag==Link)			p=p->lchild;		if (!visit(p->data))			return ERROP;		while (p->RTag == Thread&&p->rchild != T)		{			p = p->rchild;			visit(p->data);		}		p = p->rchild;	}	return OK;}Status InOrderTraverse_Thr(  BiThrTree T){	BiThrTree p;	p = T->lchild;	while (p != T)	{		p = p->rchild;	}	return OK;}

标签: #数据结构实训代码