C语言用顺序表实现二叉树

C语言用顺序表实现二叉树

在本文中，我们将介绍如何使用顺序表来实现二叉树。二叉树是一种重要的数据结构，其中每个节点最多有两个子节点：左子节点和右子节点。顺序表是一种连续存储数据元素的线性表，通过数组实现，适合表示完全二叉树。本文将探讨如何利用顺序表构建二叉树、实现遍历、计算树的高度和密度、插入和删除节点等功能。

代码分析

数据结构定义

typedef struct BinTree {
    TREE_TYPE* arr;
    size_t cap;
} BinTree;

构建和销毁二叉树

BinTree* create_tree(TREE_TYPE* arr, size_t len);
void destroy_tree(BinTree* tree);

遍历方式实现

• 先序遍历： pre_order
• 中序遍历： mid_order
• 后序遍历： back_order
• 层序遍历： layer_order

计算树的高度和密度

int high_tree(BinTree* tree);
float density_tree(BinTree* tree);

插入和删除节点

bool insert_tree(BinTree* tree, int index, TREE_TYPE data);
bool del_tree_node(BinTree* tree, int index);

求左右子树和根节点

TREE_TYPE left_tree(BinTree* tree, int index);
TREE_TYPE right_tree(BinTree* tree, int index);
TREE_TYPE root_tree(BinTree* tree);

代码运行

int main(int argc, const char* argv[]) {
    char* str = "ABCD#EF#G#HIJK";
    BinTree* tree = create_tree(str, strlen(str));
    

    // 先序遍历
    pre_order(tree);
    printf("\n");
    
    // 计算树的高度
    printf("树的高度: %d\n", high_tree(tree));
    
    // 计算树的密度
    printf("树的密度: %.2f%%\n", density_tree(tree) * 100);
    
    // 插入节点
    insert_tree(tree, 4, 'S');
    pre_order(tree);
    printf("\n");
    
    // 删除叶子节点
    del_tree_node(tree, 11);
    pre_order(tree);
    printf("\n");
    
    // 求右子树和根节点
    TREE_TYPE val = right_tree(tree, 0);
    printf("根节点: %c\n", root_tree(tree));
    printf("右子树节点: %c\n", val);
    
    destroy_tree(tree);
    
    return 0;

}

完整代码

#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
#include<math.h>

#define TREE_TYPE char
#define EMPTY '#'

typedef struct BinTree
{
	TREE_TYPE* arr;
	size_t cap;
}BinTree;

//构建
BinTree* create_tree(TREE_TYPE* arr, size_t len)
{
	BinTree* tree = malloc(sizeof(BinTree));
	tree->arr = malloc(sizeof(TREE_TYPE) * len);
	memcpy(tree->arr, arr, len * sizeof(TREE_TYPE));
	tree->cap = len;
	return tree;
}

//销毁
void destroy_tree(BinTree* tree)
{
	free(tree->arr);
	free(tree);
}

void visit(TREE_TYPE data)
{
	printf("%c ", data);
}

//先序
bool _pre_show_tree(BinTree* tree, int index)
{

	if (index >= tree->cap || tree->arr[index] == EMPTY)
	{
		return false;
	}
	visit(tree->arr[index]);
	if (EMPTY != tree->arr[index * 2 + 1])
	{
		_pre_show_tree(tree, 2 * index + 1);
	}
	if (EMPTY != tree->arr[index * 2 + 2])
	{
		_pre_show_tree(tree, 2 * index + 2);
	}
	return true;
}

bool pre_order(BinTree* tree)
{
	if (!tree)return false;
	_pre_show_tree(tree, 0);
	return true;
}

//中序
void _mid_order(BinTree* tree, int index)
{

	if (EMPTY != tree->arr[index * 2 + 1])
	{
		_pre_show_tree(tree, 2 * index + 1);
	}
	visit(tree->arr[index]);
	if (EMPTY != tree->arr[index * 2 + 2])
	{
		_pre_show_tree(tree, 2 * index + 2);
	}
}

bool mid_order(BinTree* tree)
{
	if (!tree)return false;
	_mid_order(tree, 0);
	return true;
}

//后序
void _back_order(BinTree* tree, int index)
{

	if (EMPTY != tree->arr[index * 2 + 1])
	{
		_pre_show_tree(tree, 2 * index + 1);
	}
	if (EMPTY != tree->arr[index * 2 + 2])
	{
		_pre_show_tree(tree, 2 * index + 2);
	}
	visit(tree->arr[index]);
}

bool back_order(BinTree* tree)
{
	if (!tree)return false;
	_back_order(tree, 0);
	return true;
}
//层序
void layer_order(BinTree* tree)
{
	for (int i = 0; tree->arr[i]; i++)
	{
		if (EMPTY != tree->arr[i])
			visit(tree->arr[i]);
	}
}
// 计算树的高度
int high_tree(BinTree* tree)
{
	int height = 0;
	int i = tree->cap - 1;
	while (i >= 0 && tree->arr[i] == EMPTY)
	{
		i--;
	}
	height = (int)log2(i + 1) + 1;

	return height;
}
//树的密度
float density_tree(BinTree* tree)
{
	float density = 0;
	int empty = 0;
	int i = 0;
	for (i; tree->arr[i]; i++)
	{
		if (EMPTY == tree->arr[i])empty++;
	}
	density = (float)(i - empty) / (float)i;
	return density;
}
//插入
bool insert_tree(BinTree* tree, int index, TREE_TYPE data)
{

	if (index >= tree->cap)
	{
		return false;
	}
	if (tree->arr[index] != EMPTY)
	{
		printf("此结点已有数据\n");
		return false;
	}
	tree->arr[index] = data;
	return true;
}
//删除 只删除叶子节点
bool del_tree_node(BinTree* tree, int index)
{
	if (EMPTY == tree->arr[index * 2 + 1] && EMPTY == tree->arr[index * 2 + 2])
	{
		tree->arr[index] = EMPTY;
		return true;
	}
	else if (index*2+1>=tree->cap)
	{
		tree->arr[index] = EMPTY;
		return true;
	}
	return false;
}
//求左子树
TREE_TYPE left_tree(BinTree *tree,int index)
{
	if(EMPTY != tree->arr[index * 2 + 1]||index*2<tree->cap)
	{
	TREE_TYPE val=tree->arr[index*2+1];
	return val;
	}
}
//求右子树
TREE_TYPE right_tree(BinTree *tree,int index)
{
	if(EMPTY != tree->arr[index * 2 + 2]||index*2<tree->cap)
	{
	TREE_TYPE val=tree->arr[index*2+2];
	return val;
	}
}
//求根
TREE_TYPE root_tree(BinTree *tree)
{
	return tree->arr[0];	
}

int main(int argc, const char* argv[])
{
	char* str = "ABCD#EF#G#HIJK";
	BinTree* tree = create_tree(str, strlen(str));
	pre_order(tree);
	printf("\n%d\n", high_tree(tree));
	printf("%.2f%%\n", density_tree(tree) * 100);
	insert_tree(tree, 4, 'S');
	pre_order(tree);
	printf("\n");
	del_tree_node(tree, 11);
	pre_order(tree);
	TREE_TYPE val=right_tree(tree,0);
	printf("\n%c\n",val);
	printf("%c \n",root_tree(tree));
	return 0;
}

总结

通过本文，我们详细介绍了如何使用顺序表实现二叉树，并展示了构建二叉树、遍历、计算高度和密度、插入和删除节点等功能的实现。顺序表实现二叉树具有简单高效的特点，适合用于教学和小规模应用场景。读者可以通过本文更深入地理解二叉树的实现和应用，以及顺序表的使用方法。

希望本文对读者有所帮助，欢迎提出意见和建议。谢谢阅读！