二叉树的二叉链表的简单实现及操作

梦里梦外; 2022-06-14 00:48 200阅读 0赞

本文主要简单的说一说二叉树的二叉链表的简单实现及操作。简单的说一说二叉链表的结点定义，树的创建，结点的插入，子树的销毁、树的拷贝等常用操作。

**一、创建二叉树、拷贝二叉树**

本文创建的二叉树采用二叉链表的形式来创建，二叉链表定义的树的结点通常包含一个数据域，两个地址域（分别用来指向左右子树），所以在创建树之前需要定义一个表示结点的结构体，具体实现如下：

/* 定义一个结构体用于表示二叉树的结点 */
    typedef char datatype;	// 表示结点的数据元素类型
    typedef struct Tnode{
    	datatype data;			// 数据域
    	struct Tnode *lchild;	// 左子树根结点指针
    	struct Tnode *rchild;	// 右子树根结点指针
    } Bnode;

首先实现创建二叉树的操作：本文创建的二叉树是按照先根遍历的方式来创建二叉树，就是先创建根节点，再创建左子树，最后创建右子树，采用递归的方式进行。具体的实现如下：

/*	创建一颗二叉树，要求:按照先序遍历的方式来创建二叉树
     *		返回值: 要创建的树的根结点
     */
    Bnode *btree_create()
    {
    	datatype data;
    	Bnode *T;
    	data = getchar();	// 通过控制台获得一个结点数据
    	if('#' == data)		// 如果为空树结点
    	{
    		T = NULL;
    	}
    	else				// 如果为非空树结点
    	{
    		T = malloc(sizeof(Bnode));	// 分配一块内存给根结点
    		if(NULL == T)				// 判断内存分配是否成功
    			return NULL;
    		/* 如果内存分配成功则递归创建二叉树 */
    		T->data = data;					// 创建根结点数据
    		T->lchild = btree_create();		// 递归创建左子树
    		T->rchild = btree_create();		// 递归创建右子树
    	}
    	return T;	// 返回树根结点
    }

接下来实现一个函数用来拷贝二叉树，将一颗二叉树的全部数据包括二叉树的存储结构拷贝到另一颗二叉树当中，这个也采用先根遍历的方式进行，具体的实现如下：

/*	二叉树拷贝函数:
     *		先拷贝根结点，然后递归拷贝左子树，递归拷贝右子树
     *		original : 原始树的根结点
     *		返回值: 新创建的树的根结点
     */
    Bnode *btree_copy(Bnode *original)
    {
    	Bnode *T;
    
    	if(original)
    	{
    		T = malloc(sizeof(Bnode));
    		if(NULL == T)
    		{
    			printf("btree_copy error!\n");
    			return NULL;
    		}
    
    		/* 递归的构造新树 */
    		T->data = original->data;
    		T->lchild = btree_copy(original->lchild);
    		T->rchild = btree_copy(original->rchild);
    
    		return T;
    	}
    
    	return NULL;
    }

下面定义一个函数用来显示二叉树中的元素，这个函数的实现也采用先根遍历的方式进行，具体实现如下：

/*	将一颗二叉树中的数据元素按照先序遍历的方式显示出来
     *		先显示根结点，再递归显示左子树，最后显示右子树，如果为空则显示'#'
     *		T : 要显示的树的根结点
     */
    void btree_show_elements(Bnode *T)
    {
    	if(NULL == T)	// 如果为空树
    	{
    		printf("#");
    		return;
    	}
    
    	printf("%c", T->data);
    	btree_show_elements(T->lchild);
    	btree_show_elements(T->rchild);
    }

测试程序的实现如下：

/* 程序的主函数 */
    int main(int argc, char *argv[])
    {
    	Bnode *tree1 = btree_create();		// 创建一颗树
    	Bnode *tree2 = btree_copy(tree1);	// 赋值前面创建的树
    
    	btree_show_elements(tree2);		// 将复制的树的数据元素显示出来
    	printf("\n");
    
    	return 0;
    }

![Center][]  
  
**二、在二叉树中指定位置插入左结点、插入右结点**

插入左结点的函数实现如下：

/*	向二叉树中的指定结点插入一个左孩子结点，如果有原左子树则作为新插入的左孩子结点的左子树结点
     *		curr : 为指定的结点
     *		data : 要插入的左孩子结点的结点数据
     *		返回值: 要插入的左孩子结点的地址
     */
    Bnode *btree_insert_left_node(Bnode *curr, datatype data)
    {
    	Bnode *p, *q;
    	if(NULL == curr)	// 如果指定的结点为空，则直接返回NULL
    		return NULL;
    
    	p = curr->lchild;
    	q = malloc(sizeof(Bnode));	// 分配一块结点内存给要插入的结点使用
    	if(NULL == q)				// 分配失败
    		return NULL;
    
    	/* 为分配的结点添加数据 */
    	q->data = data;
    	q->lchild = p;
    	q->rchild = NULL;
    
    	curr->lchild = q;
    
    	return q;
    }

插入右结点的函数实现如下：

/*	向二叉树中的指定结点插入一个右孩子结点，如果有原右子树则作为新插入的右孩子结点的右子树结点
     *		curr : 为指定的结点
     *		data : 要插入的右孩子结点的结点数据
     *		返回值: 要插入的右孩子结点的地址
     */
    Bnode *btree_insert_right_node(Bnode *curr, datatype data)
    {
    	Bnode *p, *q;
    	if(NULL == curr)	// 如果指定的结点为空，则直接返回NULL
    		return NULL;
    
    	p = curr->rchild;
    	q = malloc(sizeof(Bnode));	// 分配一块结点内存给要插入的结点使用
    	if(NULL == q)				// 分配失败
    		return NULL;
    
    	/* 为分配的结点添加数据 */
    	q->data = data;
    	q->lchild = NULL;
    	q->rchild = p;
    	
    	curr->rchild = q;
    
    	return q;
    }

对测试函数进行修改，如下所示：

/* 程序的主函数 */
    int main(int argc, char *argv[])
    {
    	Bnode *tree = btree_create();		// 创建一颗树
    
    	btree_insert_left_node(tree, 'x');	// 给根节点添加一个元素内容为'x'的左子结点
    	btree_insert_right_node(tree, 'y');	// 给根节点添加一个元素内容为'y'的右子结点
    
    	btree_show_elements(tree);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	return 0;
    }

测试结果如下所示：

![SouthEast][]  
从结果中可以看出，成功的实现了以根节点为父节点，成功的跟它插入了左右两个子结点。

**三、销毁指定结点的左子树、右子树**

销毁指定结点的左子树的函数具体实现如下：

/*	将指定结点的左子树销毁
     *		curr : 为指定的结点
     *		返回值: 指定结点的地址
     */
    Bnode * btree_destroy_left_tree(Bnode *curr)
    {
    	/* 如果指定结点为空或者该结点的左子树为空 */
    	if((NULL == curr) || (NULL == curr->lchild))
    		return NULL;
    
    	btree_destroy(&(curr->lchild));	// 销毁该结点的左子树
    	curr->lchild = NULL;
    	return curr;
    }

销毁指定结点的右子树的函数具体实现如下：

/*	将指定结点的右子树销毁
     *		curr : 为指定的结点
     *		返回值: 指定结点的地址
     */
    Bnode * btree_destroy_right_tree(Bnode *curr)
    {
    	/* 如果指定结点为空或者该结点的右子树为空 */
    	if((NULL == curr) || (NULL == curr->rchild))
    		return NULL;
    
    	btree_destroy(&(curr->rchild));	// 销毁该结点的右子树
    	curr->rchild = NULL;
    	return curr;
    }

在上面两个函数的实现过程当中都需要调用btree\_destroy()这个函数，它的具体实现如下所示：

/*	销毁根结点为root的子树
     *		采用递归方式
     */
    void btree_destroy(Bnode **root)
    {
    	/* 判断根结点以及左结点是否为空 */
    	if((NULL != (*root)) && (NULL != ((*root)->lchild)))
    	{
    		btree_destroy(&((*root)->lchild));
    	}
    
    	
    	/* 判断根结点以及右结点是否为空 */
    	if((NULL != (*root)) && (NULL != ((*root)->rchild)))
    	{
    		btree_destroy(&((*root)->rchild));
    	}
    
    	free(*root);	// 释放该结点分配的内存单元
    	*root = NULL;	
    }

修改测试代码如下：

/* 程序的主函数 */
    int main(int argc, char *argv[])
    {
    	Bnode *tree1 = btree_create();		// 创建一颗树
    	Bnode *tree2 = btree_copy(tree1);	// 拷贝tree1
    
    	btree_destroy_left_tree(tree1);		// 将树一的左子树销毁
    	btree_destroy_right_tree(tree2);	// 将树二的右子树销毁
    
    	btree_show_elements(tree1);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	btree_show_elements(tree2);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	return 0;
    }

测试结果如下所示：

![SouthEast 1][]  
  
**四、判断两颗二叉树是否相等**  
  
判断两颗二叉树是否相等的函数如下所示：

/*	判断两颗二叉树是否相等
     *		T1,T2 : 要比较的两个二叉树的根结点
     *		返回值: 相等返回1，否者返回0
     */
    int btree_equal(Bnode *T1, Bnode *T2)
    {
    	return ((!T1 && !T2) || 
    			(T1 && T2 && (T1->data == T2->data) && btree_equal(T1->lchild, T2->lchild) &&
    			btree_equal(T1->rchild, T2->rchild)));
    }

测试代码的实现如下所示：

/* 程序的主函数 */
    int main(int argc, char *argv[])
    {
    	Bnode *tree1 = btree_create();		// 创建一颗树
    	Bnode *tree2 = btree_copy(tree1);	// 拷贝tree1
    
    	btree_show_elements(tree1);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	btree_show_elements(tree2);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	if(btree_equal(tree1, tree2))
    	{
    		printf("They are equation!\n");
    	}
    	else
    	{
    		printf("They are not equation!\n");
    	}
    
    	return 0;
    }

测试结果如下所示：

![SouthEast 2][]

**附录：完整的程序代码实现如下**

#include <stdio.h>
    #include <stdlib.h>
    
    /* 定义一个结构体用于表示二叉树的结点 */
    typedef char datatype;	// 表示结点的数据元素类型
    typedef struct Tnode{
    	datatype data;			// 数据域
    	struct Tnode *lchild;	// 左子树根结点指针
    	struct Tnode *rchild;	// 右子树根结点指针
    } Bnode;
    
    /*	创建一颗二叉树，要求:按照先序遍历的方式来创建二叉树
     *		返回值: 要创建的树的根结点
     */
    Bnode *btree_create()
    {
    	datatype data;
    	Bnode *T;
    	data = getchar();	// 通过控制台获得一个结点数据
    	if('#' == data)		// 如果为空树结点
    	{
    		T = NULL;
    	}
    	else				// 如果为非空树结点
    	{
    		T = malloc(sizeof(Bnode));	// 分配一块内存给根结点
    		if(NULL == T)				// 判断内存分配是否成功
    			return NULL;
    		/* 如果内存分配成功则递归创建二叉树 */
    		T->data = data;					// 创建根结点数据
    		T->lchild = btree_create();		// 递归创建左子树
    		T->rchild = btree_create();		// 递归创建右子树
    	}
    	return T;	// 返回树根结点
    }
    
    /*	向二叉树中的指定结点插入一个左孩子结点，如果有原左子树则作为新插入的左孩子结点的左子树结点
     *		curr : 为指定的结点
     *		data : 要插入的左孩子结点的结点数据
     *		返回值: 要插入的左孩子结点的地址
     */
    Bnode *btree_insert_left_node(Bnode *curr, datatype data)
    {
    	Bnode *p, *q;
    	if(NULL == curr)	// 如果指定的结点为空，则直接返回NULL
    		return NULL;
    
    	p = curr->lchild;
    	q = malloc(sizeof(Bnode));	// 分配一块结点内存给要插入的结点使用
    	if(NULL == q)				// 分配失败
    		return NULL;
    
    	/* 为分配的结点添加数据 */
    	q->data = data;
    	q->lchild = p;
    	q->rchild = NULL;
    
    	curr->lchild = q;
    
    	return q;
    }
    
    /*	向二叉树中的指定结点插入一个右孩子结点，如果有原右子树则作为新插入的右孩子结点的右子树结点
     *		curr : 为指定的结点
     *		data : 要插入的右孩子结点的结点数据
     *		返回值: 要插入的右孩子结点的地址
     */
    Bnode *btree_insert_right_node(Bnode *curr, datatype data)
    {
    	Bnode *p, *q;
    	if(NULL == curr)	// 如果指定的结点为空，则直接返回NULL
    		return NULL;
    
    	p = curr->rchild;
    	q = malloc(sizeof(Bnode));	// 分配一块结点内存给要插入的结点使用
    	if(NULL == q)				// 分配失败
    		return NULL;
    
    	/* 为分配的结点添加数据 */
    	q->data = data;
    	q->lchild = NULL;
    	q->rchild = p;
    	
    	curr->rchild = q;
    
    	return q;
    }
    
    /*	销毁根结点为root的子树
     *		采用递归方式
     */
    void btree_destroy(Bnode **root)
    {
    	/* 判断根结点以及左结点是否为空 */
    	if((NULL != (*root)) && (NULL != ((*root)->lchild)))
    	{
    		btree_destroy(&((*root)->lchild));
    	}
    
    	
    	/* 判断根结点以及右结点是否为空 */
    	if((NULL != (*root)) && (NULL != ((*root)->rchild)))
    	{
    		btree_destroy(&((*root)->rchild));
    	}
    
    	free(*root);	// 释放该结点分配的内存单元
    	*root = NULL;	
    }
    
    /*	将指定结点的左子树销毁
     *		curr : 为指定的结点
     *		返回值: 指定结点的地址
     */
    Bnode * btree_destroy_left_tree(Bnode *curr)
    {
    	/* 如果指定结点为空或者该结点的左子树为空 */
    	if((NULL == curr) || (NULL == curr->lchild))
    		return NULL;
    
    	btree_destroy(&(curr->lchild));	// 销毁该结点的左子树
    	curr->lchild = NULL;
    	return curr;
    }
    
    /*	将指定结点的右子树销毁
     *		curr : 为指定的结点
     *		返回值: 指定结点的地址
     */
    Bnode * btree_destroy_right_tree(Bnode *curr)
    {
    	/* 如果指定结点为空或者该结点的右子树为空 */
    	if((NULL == curr) || (NULL == curr->rchild))
    		return NULL;
    
    	btree_destroy(&(curr->rchild));	// 销毁该结点的右子树
    	curr->rchild = NULL;
    	return curr;
    }
    
    /*	二叉树拷贝函数:
     *		先拷贝根结点，然后递归拷贝左子树，递归拷贝右子树
     *		original : 原始树的根结点
     *		返回值: 新创建的树的根结点
     */
    Bnode *btree_copy(Bnode *original)
    {
    	Bnode *T;
    
    	if(original)
    	{
    		T = malloc(sizeof(Bnode));
    		if(NULL == T)
    		{
    			printf("btree_copy error!\n");
    			return NULL;
    		}
    
    		/* 递归的构造新树 */
    		T->data = original->data;
    		T->lchild = btree_copy(original->lchild);
    		T->rchild = btree_copy(original->rchild);
    
    		return T;
    	}
    
    	return NULL;
    }
    
    /*	判断两颗二叉树是否相等
     *		T1,T2 : 要比较的两个二叉树的根结点
     *		返回值: 相等返回1，否者返回0
     */
    int btree_equal(Bnode *T1, Bnode *T2)
    {
    	return ((!T1 && !T2) || 
    			(T1 && T2 && (T1->data == T2->data) && btree_equal(T1->lchild, T2->lchild) &&
    			btree_equal(T1->rchild, T2->rchild)));
    }
    
    /*	将一颗二叉树中的数据元素按照先序遍历的方式显示出来
     *		先显示根结点，再递归显示左子树，最后显示右子树，如果为空则显示'#'
     *		T : 要显示的树的根结点
     */
    void btree_show_elements(Bnode *T)
    {
    	if(NULL == T)	// 如果为空树
    	{
    		printf("#");
    		return;
    	}
    
    	printf("%c", T->data);
    	btree_show_elements(T->lchild);
    	btree_show_elements(T->rchild);
    }
    
    /* 程序的主函数 */
    int main(int argc, char *argv[])
    {
    	Bnode *tree1 = btree_create();		// 创建一颗树
    	Bnode *tree2 = btree_copy(tree1);	// 拷贝tree1
    
    	btree_show_elements(tree1);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	btree_show_elements(tree2);		// 将树的结点数据元素显示出来
    	printf("\n");
    
    	if(btree_equal(tree1, tree2))
    	{
    		printf("They are equation!\n");
    	}
    	else
    	{
    		printf("They are not equation!\n");
    	}
    
    	return 0;
    }

[Center]: /images/20220614/b9140826f799466f8916bafcffaedf23.png
[SouthEast]: /images/20220614/342f9a99bbef48fab233f928397672f3.png
[SouthEast 1]: /images/20220614/c1dab144ee7b4f87b9cca12695b94728.png
[SouthEast 2]: /images/20220614/a1e1a35fa21c4dd4958b9a20a678c339.png