使用C语言实现二叉树的链式存储

目录

1.二叉树的顺序存储

（1）数据结构的定义

（2）常用操作

2.二叉树的链式存储

（1）结构

（2）基本操作

（3）定义数据结构

（4）创建和销毁二叉树

（5）前序，中序，后序遍历

（6）二叉树高度

（7）统计叶子节点，统计第k层节点数

（8）主函数

（9）测试

---

1.二叉树的顺序存储

定义：用一组地址连续的存储单元依次自上而下，自左向右存储完全二叉树上的节点元素。

（1）数据结构的定义

#include
#include
 
#define MAXSIZE 10
 
typedef int ElemType;
 
typedef struct {
	ElemType value;//节点中的数据元素 
	bool isEmpty;//节点是否为空 
}TreeNode;
 
TreeNode T[MAXSIZE];

注：完全二叉树

 

注：二叉树

（2）常用操作

i的左孩子：2i 
i的右孩子：2i+1
i的双亲节点：[i/2]（向下取整）
i所在层：[log2(n+1)]（向上取整）或者[log2n]+1（向下取整）

完全二叉树中共有n个节点，则以下判断操作：
判断i是否有左孩子：2i<=n
判断i是否有右孩子：2i+1<=n
判断i是否为分子节点/叶子节点：i>[n/2]（向下取整）

注：二叉树的顺序存储只适用于完全二叉树。

2.二叉树的链式存储

（1）结构

 

 链式存储：二叉树的节点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的节点至少包含3个域：数据域和左，右指针域。

（2）基本操作

1.创建二叉树

2.二叉树的前序遍历

3.二叉树的中序遍历

4.二叉树的后序遍历

5.二叉树的高度

6.二叉树的叶子节点数

7.二叉树的节点数

8.第k层节点数

9.重新初始化节点

10.二叉树的销毁操作

11.结束操作

（3）定义数据结构

#include
#include
#include
#include
 
#define MAXSIZE 10
 
#define maxn 100
 
typedef char ElemType;
 
typedef struct BiTNode{
	ElemType data;//节点中的数据元素 
	struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;
 
int depth=0;
 
void InitBitree(){
	printf("--------------1.创建二叉树------------\n");
	printf("--------------2.二叉树的前序遍历------\n");
	printf("--------------3.二叉树的中序遍历------\n");
	printf("--------------4.二叉树的后序遍历------\n");
	printf("--------------5.二叉树的高度----------\n");
	printf("--------------6.二叉树的叶子节点数----\n");
	printf("--------------7.二叉树的节点数--------\n");
	printf("--------------8.第k层节点数----------\n");
	printf("--------------9.重新初始化节点-------\n");
	printf("--------------10.二叉树的销毁操作-----\n");
	printf("--------------11.结束操作-------------\n");
}

（4）创建和销毁二叉树

void DestryBitree(BiTree&T){
	if(T==NULL){
		return;
	}
	DestryBitree(T->lchild);
	DestryBitree(T->rchild);
	free(T);
}
//创建二叉树 
void createBitree(BiTree&T,char list[maxn],int k,int mask,int length){
	if(list[k]=='\0')mask=0;
	if(k>=length)return;
	if(mask==1){
		T=(BiTNode*)malloc(sizeof(BiTNode));
		T->data=list[k];
		T->lchild=NULL;
		T->rchild=NULL;
		createBitree(T->lchild,list,2*k+1,mask,length);
		createBitree(T->rchild,list,2*k+2,mask,length);
	}
	return;
}

（5）前序，中序，后序遍历

//前序遍历 
void PreOrderTraverse(BiTree T){
	if(T==NULL)return;
	printf("%c\t",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}
//中序遍历 
void InOrderTraverse(BiTree T){
	if(T==NULL)return;
	PreOrderTraverse(T->lchild);
	printf("%c\t",T->data);
	PreOrderTraverse(T->rchild);
}
//后序遍历 
void PostOrderTraverse(BiTree T){
	if(T==NULL)return;
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
	printf("%c\t",T->data);
}

（6）二叉树高度

//二叉树的高度
int HeightBitree(BiTree T){
	if(T==NULL){ 
		return 0;
	}else{
		int Lheight=HeightBitree(T->lchild);
		int Rheight=HeightBitree(T->rchild);
		depth=Lheight>Rheight?Lheight+1:Rheight+1;
	}
	return depth;
} 

（7）统计叶子节点，统计第k层节点数

//二叉树的节点数
int count=0;
void CountNode(BiTree T){
	if(T==NULL)return ;
	if(T){
		count++;
	}
	CountNode(T->lchild);
	CountNode(T->rchild);
} 
 
//二叉树第k层节点数
int KLayerNode(BiTree T,int k){
	int a,b;
	if(T==NULL)return 0;
	if(k==1)return 1;
	a=KLayerNode(T,k-1);
	b=KLayerNode(T,k-1);
	return a+b;
} 

（8）主函数

int main(){
	//根节点初始化为NULL 
	BiTree T=NULL;
	ElemType list[maxn];
	int flag=0;
	while(1){
		InitBitree();
		printf("请输入操作: ");
		scanf("%d",&flag);
		int k=0;
		int mask=1;
		int depth=0;
		int length=0;
		count=0;
		switch(flag){
			case 1:
				printf("请输入字符序列: ");
				scanf("%s",&list);
				length=strlen(list);
				createBitree(T,list,k,mask,length);
				break;
			case 2:
				PreOrderTraverse(T);
				printf("\n");
				break;
			case 3:
				InOrderTraverse(T);
				printf("\n");
				break;
			case 4:
				PostOrderTraverse(T);
				printf("\n");
				break;
			case 5:
				//二叉树的高度 
				depth=HeightBitree(T);
				printf("二叉树的高度为 = %d\n",depth);
				break;
			case 6:
				//叶子节点数 
				count=CountLeaf(T);
				printf("叶子节点数 = %d\n",count);
				break; 
			case 7:
				//节点数
				CountNode(T); 
				printf("节点数 = %d\n",count);
				break;
			case 8:
				//第k层节点数 
				printf("请输入查找节点的第k层: ");
				scanf("%d",&k);
				depth=HeightBitree(T);
				if(k>depth){
					printf("输入的不合法!\n");
				}else{
					count=KLayerNode(T,k);
					printf("第k层节点数 = %d\n",count);
				}
				break; 
			case 9:
				//重新初始化 
				DestryBitree(T);
				T=NULL;
				break;  
			case 10:
				DestryBitree(T);
				break;
			default:
				if(T!=NULL){
					DestryBitree(T);
				}
				printf("结束操作!");
				break;
		}
		if(flag==11){
			break;
		} 
	}
	return 0;
}

（9）测试