二叉树C语言实现

这篇具有很好参考价值的文章主要介绍了二叉树C语言实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最新代码仓库:https://github.com/sixsixQAQ/binary-tree

一、指针 VS 数组+索引

二叉树的实现,既可以用数组 + 索引来实现,也可以用指针来实现。

指针实现比索引+数组实现有天然的优势:

  1. 指针可以用NULL判空,无序另设判空用的值。

    • 比如索引实现时,通常需要用-1来表示非法索引/空索引。
  2. 指针实现传参更少。

    • 比如指针可以很方便地递归,只要tree->lchild就可以递归下一个子树;
    • 而索引实现时,当前树如果想要递归到子树,总是需要再传一个索引来递归。
    • 这是因为指针直指内存,而数组 + 索引才能实现这一效果,比如tree->lchild,用数组+索引表达就是tree[index].lchild,更像是在模拟指针。
  3. 指针实现的代码更清晰。

    • 单纯更清晰而已,用索引会出现多层的方括号,信息密度高,可读性差。

指针实现见在后文。

仓库的还提供了一个数组+索引实现的版本供参考,接口和指针实现差不多。


可以先看看下面一个小小对比,指针更方便:

#include <stdlib.h>
#include <stdio.h>

typedef struct binary_tree_I binary_tree_I;
struct binary_tree_I {
	char data;
	int lchild, rchild;
};

typedef struct binary_tree_P binary_tree_P;
struct binary_tree_P {
	char data;
	binary_tree_P *lchild, *rchild;
};


binary_tree_P *
get_lchild_P (binary_tree_P *tree)
{
	return tree->lchild;
}

binary_tree_P *
get_rchild_P (binary_tree_P *tree)
{
	return tree->rchild;
}

binary_tree_I *
get_lchild_I (binary_tree_I *tree, int curr)
{
	return &tree[ tree[curr].lchild ];
}

binary_tree_I *
get_rchild_I (binary_tree_I *tree, int curr)
{
	return &tree[ tree[curr].rchild];
}

int
main (void)
{

}

二、指针实现

main.c:

#include <stdio.h>
#include <string.h>
#include "binary_tree.h"


void
print_all (binary_tree_node *tree)
{
	printf ("先序遍历: "), binary_tree_print_data (tree, DLR), putchar ('\n');
	printf ("中序遍历: "), binary_tree_print_data (tree, LDR), putchar ('\n');
	printf ("后序遍历: "), binary_tree_print_data (tree, LRD), putchar ('\n');
	printf ("层序遍历: "), binary_tree_print_data (tree, LEVEL), putchar ('\n');
	
	printf ("打印树: "), binary_tree_print_tree (tree), putchar ('\n');
	
	printf ("结点数:%d\n", binary_tree_get_node_count (tree));
	printf ("叶子结点数:%d\n", binary_tree_get_leaf_node_count (tree));
	printf ("树深:%d\n", binary_tree_get_tree_depth (tree));
}

int
main (void)
{

	/**
	 * Demo
	 *                  A
	 *                /   \
	 *              B      G
	 *            /  \    / \
	 *          C     F  H   I
	 *        /
	 *      D
	 *       \
	 *        E
	*/
	
	{
		char DLR_data[] = {'A', 'B', 'C', 'D', -1, 'E', -1, -1, -1, 'F', -1, -1, 'G', 'H', -1, -1, 'I', -1, -1};
		binary_tree_node *tree = binary_tree_new_DLR (DLR_data);
		
		print_all (tree);
		
		binary_tree_delete (tree);
	}
	
	{
		puts ("--------------重建树--------------:");
		char *DLR_sequence = "ABCDEFGHI";
		char *LDR_sequence = "DECBFAHGI";
		
		binary_tree_node *tree = binary_tree_rebuild_from_DLR_and_LDR (
		                             DLR_sequence, LDR_sequence, strlen (DLR_sequence)
		                         );
		                         
		print_all (tree);
		
		binary_tree_delete (tree);
	}
	puts ("----------------------------------------------------------");
	
	
	
	/**
	 * Demo 2
	 *                  A
	 *                /   \
	 *              B      C
	 *            /  \    / \
	 *          D     E  F   G
	 *           \      / \
	 *            H    I   J
	*/
	{
		char DLR_data[] = {'A', 'B', 'D', -1, 'H', -1, -1, 'E', -1, -1, 'C', 'F', 'I', -1, -1, 'J', -1, -1, 'G', -1, -1};
		binary_tree_node *tree = binary_tree_new_DLR (DLR_data);
		print_all (tree);
		binary_tree_delete (tree);
	}
	{
		puts ("--------------重建树--------------:");
		char *DLR_sequence = "ABDHECFIJG";
		char *LDR_sequence = "DHBEAIFJCG";
		
		binary_tree_node *tree = binary_tree_rebuild_from_DLR_and_LDR (
		                             DLR_sequence, LDR_sequence, strlen (DLR_sequence)
		                         );
		                         
		print_all (tree);
		
		binary_tree_delete (tree);
	}
}

输出结果:

先序遍历: A B C D E F G H I 
中序遍历: D E C B F A H G I 
后序遍历: E D C F B H I G A 
层序遍历: A B G C F H I D E 
打印树: A(B(C(D(,E)),F),G(H,I))
结点数:9
叶子结点数:4
树深:5
--------------重建树--------------:
先序遍历: A B C D E F G H I 
中序遍历: D E C B F A H G I 
后序遍历: E D C F B H I G A 
层序遍历: A B G C F H I D E 
打印树: A(B(C(D(,E)),F),G(H,I))
结点数:9
叶子结点数:4
树深:5
----------------------------------------------------------
先序遍历: A B D H E C F I J G 
中序遍历: D H B E A I F J C G 
后序遍历: H D E B I J F G C A 
层序遍历: A B C D E F G H I J 
打印树: A(B(D(,H),E),C(F(I,J),G))
结点数:10
叶子结点数:5
树深:4
--------------重建树--------------:
先序遍历: A B D H E C F I J G 
中序遍历: D H B E A I F J C G 
后序遍历: H D E B I J F G C A 
层序遍历: A B C D E F G H I J 
打印树: A(B(D(,H),E),C(F(I,J),G))
结点数:10
叶子结点数:5
树深:4


binary_tree.h:

#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <stdbool.h>
#include <stddef.h>

typedef char data_type;

typedef struct binary_tree_node binary_tree_node;
struct binary_tree_node {
	data_type data;
	binary_tree_node *lchild, *rchild;
};

binary_tree_node *binary_tree_new_DLR (const data_type *data_array);

void binary_tree_delete (binary_tree_node *tree);

void binary_tree_traverse_DLR (binary_tree_node *tree,
                               void (*solve) (binary_tree_node *, void *),
                               void *arg);
void binary_tree_traverse_LDR (binary_tree_node *tree,
                               void (*solve) (binary_tree_node *, void *),
                               void *arg);
void binary_tree_traverse_LRD (binary_tree_node *tree,
                               void (*solve) (binary_tree_node *, void *),
                               void *arg);
void binary_tree_traverse_level (binary_tree_node *tree,
                                 void (*solve) (binary_tree_node *, void *),
                                 void *arg);

void binary_tree_traverse_DLR_const (const binary_tree_node *tree,
                                     void (*solve) (const binary_tree_node *, void *),
                                     void *arg);
void binary_tree_traverse_LDR_const (const binary_tree_node *tree,
                                     void (*solve) (const binary_tree_node *, void *),
                                     void *arg);
void binary_tree_traverse_LRD_const (const binary_tree_node *tree,
                                     void (*solve) (const binary_tree_node *, void *),
                                     void *arg);
void binary_tree_traverse_level_const (const binary_tree_node *tree,
                                       void (*solve) (const binary_tree_node *, void *),
                                       void *arg);

bool binary_tree_is_leaf_node (const binary_tree_node *node);

int binary_tree_get_node_count (const binary_tree_node *tree);

int binary_tree_get_leaf_node_count (const binary_tree_node *tree);

int binary_tree_get_tree_depth (const binary_tree_node *tree);

typedef enum binary_tree_traverse_order {
	DLR, LDR, LRD, LEVEL
} binary_tree_traverse_order;

void binary_tree_print_tree (const binary_tree_node *tree);
void binary_tree_print_data (const binary_tree_node *tree, binary_tree_traverse_order order);

binary_tree_node *binary_tree_rebuild_from_DLR_and_LDR (
    const data_type *DLR_sequence,
    const data_type *LDR_sequence,
    size_t length
);



#endif // BINARY_TREE_H

binary_tree.c:文章来源地址https://www.toymoban.com/news/detail-430020.html

#include "binary_tree.h"
#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>

static inline void *
Malloc (size_t size)
{
	void *mem = malloc (size);
	if (mem == NULL) {
		fprintf (stderr, "malloc() failed");
		exit (EXIT_FAILURE);
	}
	return mem;
}

static const data_type EMPTY_BRANCH = -1;

static binary_tree_node *
real_binary_tree_new_DLR (const data_type *data_array, int *curr)
{
	binary_tree_node *tree;
	if (data_array[*curr] == EMPTY_BRANCH) {
		tree = NULL, ++*curr;
	} else {
		tree = Malloc (sizeof (binary_tree_node));
		tree->data = data_array[*curr], ++*curr;
		tree->lchild = real_binary_tree_new_DLR (data_array, curr);
		tree->rchild =  real_binary_tree_new_DLR (data_array, curr);
	}
	return tree;
}

binary_tree_node *
binary_tree_new_DLR (const data_type *data_array)
{
	int beg = 0;
	return real_binary_tree_new_DLR (data_array, &beg);
}

void
binary_tree_delete (binary_tree_node *tree)
{
	if (tree == NULL)
		return;
	else {
		binary_tree_delete (tree->lchild);
		binary_tree_delete (tree->rchild);
		free (tree);
	}
}

void
binary_tree_traverse_DLR (binary_tree_node *tree, void (*solve) (binary_tree_node *, void *), void *arg)
{
	if (tree == NULL)
		return;
	solve (tree, arg);
	binary_tree_traverse_DLR (tree->lchild, solve, arg);
	binary_tree_traverse_DLR (tree->rchild, solve, arg);
}

void
binary_tree_traverse_LDR (binary_tree_node *tree, void (*solve) (binary_tree_node *, void *), void *arg)
{
	if (tree == NULL)
		return;
	binary_tree_traverse_LDR (tree->lchild, solve, arg);
	solve (tree, arg);
	binary_tree_traverse_LDR (tree->rchild, solve, arg);
}

void
binary_tree_traverse_LRD (binary_tree_node *tree, void (*solve) (binary_tree_node *, void *), void *arg)
{
	if (tree == NULL)
		return;
	binary_tree_traverse_LRD (tree->lchild, solve, arg);
	binary_tree_traverse_LRD (tree->rchild, solve, arg);
	solve (tree, arg);
}

void
binary_tree_traverse_DLR_const (const binary_tree_node *tree,
                                void (*solve) (const binary_tree_node *, void *),
                                void *arg)
{
	binary_tree_traverse_DLR (
	    (binary_tree_node *) tree,
	    (void (*) (binary_tree_node *, void *)) solve,
	    arg
	);
}

void
binary_tree_traverse_LDR_const (const binary_tree_node *tree,
                                void (*solve) (const binary_tree_node *, void *),
                                void *arg)
{
	binary_tree_traverse_LDR (
	    (binary_tree_node *) tree,
	    (void (*) (binary_tree_node *, void *)) solve,
	    arg
	);
}

void
binary_tree_traverse_LRD_const (const binary_tree_node *tree,
                                void (*solve) (const binary_tree_node *, void *),
                                void *arg)
{
	binary_tree_traverse_LRD (
	    (binary_tree_node *) tree,
	    (void (*) (binary_tree_node *, void *)) solve,
	    arg
	);
}

bool
binary_tree_is_leaf_node (const binary_tree_node *node)
{
	if (node == NULL)
		return false;
	else
		return node->lchild == NULL && node->rchild == NULL;
}



static void inline
callback_INC_node_count (const binary_tree_node *tree, void *count)
{
	++* (int *) count;
}

int
binary_tree_get_node_count (const binary_tree_node *tree)
{
	int count = 0;
	binary_tree_traverse_DLR_const (tree, callback_INC_node_count, &count);
	return count;
}

static void inline
callback_INC_leaf_node_count (const binary_tree_node *tree, void *count)
{
	if (binary_tree_is_leaf_node (tree))
		++* (int *) count;
}

int
binary_tree_get_leaf_node_count (const binary_tree_node *tree)
{
	int count = 0;
	binary_tree_traverse_DLR_const (tree, callback_INC_leaf_node_count, &count);
	return count;
}

int
binary_tree_get_tree_depth (const binary_tree_node *tree)
{
	if (tree == NULL)
		return 0;
	else {
		int ldepth = binary_tree_get_tree_depth (tree->lchild);
		int rdepth = binary_tree_get_tree_depth (tree->rchild);
		if (ldepth > rdepth)
			return ldepth + 1;
		else
			return rdepth + 1;
	}
}

typedef
void (*binary_tree_traverse_func) (
    binary_tree_node *, void (*) (binary_tree_node *, void *), void *
);

typedef
void (*binary_tree_traverse_func_const) (
    const binary_tree_node *, void (*) (const binary_tree_node *, void *), void *
);

static binary_tree_traverse_func
get_traverse_func (binary_tree_traverse_order order)
{
	static binary_tree_traverse_func func_array[4] = {NULL};
	
	if (func_array[0] == NULL) {
		func_array[DLR] = binary_tree_traverse_DLR;
		func_array[LDR] = binary_tree_traverse_LDR;
		func_array[LRD] = binary_tree_traverse_LRD;
		func_array[LEVEL] = binary_tree_traverse_level;
	}
	
	return func_array[order];
}

static binary_tree_traverse_func_const
get_traverse_func_const (binary_tree_traverse_order order)
{
	static binary_tree_traverse_func_const func_array[4] = {NULL};
	
	if (func_array[0] == NULL) {
		func_array[DLR] = binary_tree_traverse_DLR_const;
		func_array[LDR] = binary_tree_traverse_LDR_const;
		func_array[LRD] = binary_tree_traverse_LRD_const;
		func_array[LEVEL] = binary_tree_traverse_level_const;
	}
	
	return func_array[order];
}

static void
callback_print_node_data (const binary_tree_node *tree, void *unused)
{
	printf ("%c ", tree->data);
}

void
binary_tree_print_data (const binary_tree_node *tree, binary_tree_traverse_order order)
{
	binary_tree_traverse_func_const func = get_traverse_func_const (order);
	func (tree, callback_print_node_data, NULL);
}

void
binary_tree_print_tree (const binary_tree_node *tree)
{
	if (tree == NULL)
		return;
	putchar (tree->data);
	if (tree->lchild != NULL) {
		putchar ('(');
		
		binary_tree_print_tree (tree->lchild);
		if (tree->rchild != NULL) {
			putchar (',');
			binary_tree_print_tree (tree->rchild);
		}
		
		putchar (')');
	} else if (tree->rchild != NULL) {
		putchar ('(');
		
		binary_tree_print_tree (tree->lchild);
		if (tree->rchild != NULL) {
			putchar (',');
			binary_tree_print_tree (tree->rchild);
		}
		
		putchar (')');
	}
}

binary_tree_node *
binary_tree_rebuild_from_DLR_and_LDR (const data_type *DLR_sequence, const data_type *LDR_sequence, size_t length)
{
	if (length == 0)
		return NULL;
	else {
		binary_tree_node *tree = Malloc (sizeof (binary_tree_node));
		char D = DLR_sequence[0];
		tree->data = D;
		
		char *D_in_LDR_sequence = strchr (LDR_sequence, D);
		size_t llength = D_in_LDR_sequence - LDR_sequence;
		size_t rlength = length - llength - 1;
		
		tree->lchild = binary_tree_rebuild_from_DLR_and_LDR (&DLR_sequence[1], LDR_sequence, llength);
		tree->rchild = binary_tree_rebuild_from_DLR_and_LDR (&DLR_sequence[1 + llength], D_in_LDR_sequence + 1, rlength);
		return tree;
	}
}

void
binary_tree_traverse_level (binary_tree_node *tree,
                            void (*solve) (binary_tree_node *, void *),
                            void *arg)
{
	const int QUEUE_MAX_SIZE = 4096;
	binary_tree_node *queue[QUEUE_MAX_SIZE];
	int front, rear, tmp;
	front = rear = 0;
	
#define ENQUEUE(node)\
	queue[rear] = node, rear = (rear +1) % QUEUE_MAX_SIZE
	
#define DEQUEUE()                           \
	( tmp = front,                          \
	  front = (front +1) % QUEUE_MAX_SIZE,  \
	  queue[tmp]                            \
	)
#define IS_QUEUE_EMPTY()\
	( rear == front )
#define IS_QUEUE_FULL()\
	( (rear +1 ) % QUEUE_MAX_SIZE == front )
	
	
	ENQUEUE (tree);
	for (; !IS_QUEUE_EMPTY() ;) {
		binary_tree_node *curr = DEQUEUE();
		solve (curr, arg);
		if (curr->lchild != NULL)
			ENQUEUE (curr->lchild);
		if (curr->rchild != NULL)
			ENQUEUE (curr->rchild);
	}
	
#undef ENQUEUE
#undef DEQUEUE
#undef IS_QUEUE_EMPTY
#undef IS_QUEUE_FULL
}

void
binary_tree_traverse_level_const (const binary_tree_node *tree,
                                  void (*solve) (const binary_tree_node *, void *),
                                  void *arg)
{
	binary_tree_traverse_level (
	    (binary_tree_node *) tree,
	    (void (*) (binary_tree_node *, void *)) solve,
	    arg
	);
}

到了这里,关于二叉树C语言实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis的实现三:c语言实现平衡二叉树,通过平衡二叉树实现排序集

    概况 :Redis中的排序集数据结构是相当复杂的独特而有用的东西。它不仅提供了顺序排序数据的能力,而且具有按排名查询有序数据的独特特性。 (Sorted Set)是一种特殊的数据结构,它结合了集合(Set)和有序列表(List)的特点。在Redis中,每个成员都有一个分数(score),

    2024年01月16日
    浏览(43)
  • 二叉树--C语言实现数据结构

    本期带大家一起用C语言实现二叉树🌈🌈🌈 二叉树是一种特殊的树状数据结构,它由节点组成,每个节点最多有两个子节点,分别称为左子节点和右子节点 二叉树的链式存储结构是指用 链表 来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点

    2024年02月17日
    浏览(41)
  • 二叉树的编程与实现(C语言)

    一 、目的 : 掌握指针变量、动态变量的含义; 掌握二叉树的结构特征,以及各种存储结构的特点及适用范围; 掌握指针类型描述、访问和处理二叉树的运算; 二 、环境: operating system version:Win11 CPU instruction set:  x64 Integrated Development Environment:Viusal Studio 2022 三 、内容:

    2024年02月05日
    浏览(38)
  • 二叉树相关操作---纯代码实现详解

    目录 前言 (很重要) 二叉树的概念 二叉树的相关术语 相关操作菜单   二叉树的构造  创建二叉树 先序遍历二叉树    中序遍历二叉树  后序遍历二叉树  层次遍历二叉树  二叉树的深度  二叉树的叶子结点数  二叉树的结点数 整体代码 结果展示 结束语         大家好,

    2023年04月09日
    浏览(30)
  • 二叉树的实现(C语言数据结构)

    目录 一、以下是我们需要实现的功能 二、以下是我们具体功能的实现 1.创建新的结点 2.通过数组生成二叉树  3.先序遍历 4.中序遍历 5.后序遍历   6.层序遍历 7.计算二叉树的结点个数 8.查找指定值为x的结点 9.查找第K层的结点个数 10.统计二叉树叶子结点的个数 11.判断是否为

    2024年02月04日
    浏览(39)
  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(45)
  • 数据结构-二叉树的代码实现(详解)

    内容:二叉树的前、中,后序遍历,层序遍历,二叉树节点个数,叶子节点个数,二叉树高度,第k层节点的个数,查找某个节点,二叉树销毁,判断是否为完全二叉树 目录  前序遍历: 中序遍历: 后序遍历: 层次遍历:需要借助队列  二叉树节点个数:  二叉树叶子节点

    2024年02月03日
    浏览(42)
  • 【数据结构初阶】八、非线性表里的二叉树(二叉树的实现 -- C语言链式结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)-CSDN博客  ==========

    2024年02月08日
    浏览(52)
  • 【数据结构】二叉树OJ题(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年03月17日
    浏览(45)
  • ACM模式数组构建二叉树Go语言实现

    想输入一个数组,然后构造二叉树 例如数组为 [6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5] 对应的二叉树为: ACM模式数组构建二叉树 重点:如果父节点的数组下标是 i ,那么它的左孩子下标就是 i*2+1 ,右孩子下标就是 i*2+2 。 输出:

    2024年02月10日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包