C语言二叉树的基本操作

earthchen

发布于 2020-09-24 11:12:48

1.2K0

发布于 2020-09-24 11:12:48

文章被收录于专栏：earthchen的专栏

树是数据结构中一门很重要的数据结构，在很多地方都能经常见到他的面孔，比如数据通信，压缩数据等都能见到树的身影。但是最常见的还是相对简单的二叉树，二叉树和常规树都可以进行相互转换。所以，二叉树的操作必不可少。我这里来简单介绍一下。在数据结构中给的树和图中，我们最好使用递归来进行各种操作，会让代码更清晰易懂，代码也会更简洁。

开始

添加适当的头文件，定义hex一个栈数据结构，

首先我们定义一个二叉树的数据结构

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

创建一个二叉树（前序）

这里以前序作为例子，前中后序遍历的不同之在于递归的顺序

void creatBiTree(BiTree *T) {
	ElemType c;
	scanf("%c", &c);
	if ('#' == c)
	{
		*T = NULL;
	}
	else
	{
		*T = (BiTNode *)malloc(sizeof(BiTNode));
		(*T)->data = c;
		creatBiTree(&(*T)->lchild);
		creatBiTree(&(*T)->rchild);
	}
}

遍历二叉树(前序遍历)

这里依然以前序作为例子，前中后序遍历的不同之在于递归的顺序

void preorder(BiTree T) {
	if (T) {
		printf("%c\n", T->data);
		preorder(T->lchild);
		preorder(T->rchild);
	}
}

层次遍历二叉树

void levelorder(BiTree T) {
	//用一个队列保存结点信息,这里的队列采用的是顺序队列中的数组实现
	int front = 0;
	int rear = 0;
	BiTree BiQueue[MAXSIZE];
	BiTree tempNode;
	if (!IsEmpty_BiTree(&T)) {
		//将根结点加入到队列中　
		BiQueue[rear++] = T;

		while (front != rear) {
			//取出队头元素，并使队头指针向后移动一位　
			tempNode = BiQueue[front++];
			//判断左右子树是否为空,若为空，则加入队列　
			if (!IsEmpty_BiTree(&(tempNode->lchild)))
				BiQueue[rear++] = tempNode->lchild;

			if (!IsEmpty_BiTree(&(tempNode->rchild)))
				BiQueue[rear++] = tempNode->rchild;

			//输出队头结点元素　
			//Vist_BiTreeNode(tempNode->data);
			printf("%c\n", tempNode->data);

		}
	}
}

复制树

将二叉树复制给另一个二叉树

void copybitree(BiTree T, BiTree *newT) {
	if (T == NULL)
	{
		*newT = NULL;
		return;
	}
	else
	{
		*newT = (BiTNode *)malloc(sizeof(BiTNode));
		((*newT)->data) = (T->data);
		copybitree(T->lchild, &(*newT)->lchild);
		copybitree(T->rchild, &(*newT)->rchild);
	}
}

计算结点个数

计算二叉树的结点个数

int countleaf(BiTree T) {
	if (T == NULL)
	{
		return 0;
	}
	else {
		return countleaf(T->lchild) + countleaf(T->rchild) + 1;
	}
}

左、右子树交换

交换一颗二叉树的左右子树

void exchange(BiTree T) 
{
	BiTree p;
	if (T != NULL)
	{
		p = T->lchild;
		T->lchild = T->rchild;
		T->rchild = p;
		exchange(T->lchild);
		exchange(T->rchild);
	}
}

主函数

void main() {
	BiTree T=NULL,newT=NULL;
	creatBiTree(&T);
	printf("前序遍历\n");
	preorder(T);
	printf("中序遍历\n");
	inorder(T);
	printf("中后遍历\n");
	postorder(T);
	printf("层序遍历\n");
	levelorder(T);
	printf("节点个数为%d\n", countleaf(T));
	copybitree(T, &newT);
	printf("newT前序遍历\n");
	preorder(newT);
	exchange(T);
	printf("交换左右子树之后前序遍历为");
	preorder(T);
}