【数据结构】链式二叉树

发布于：2025-05-23 ⋅ 阅读:(17) ⋅ 点赞:(0)

 本文是小编巩固自身而作，如有错误，欢迎指出！

之前已经简介过儿二叉树的基本概念和基于数组的堆的实现，如有兴趣可以访问

【数据结构】堆

1.链式二叉树的概念

所谓链式二叉树，就是基于链表的结构构成的二叉树。通常的⽅法 是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩 ⼦所在的链结点的存储地址。

2.链式二叉树的实现 

2.1链式二叉树结构声明

typedef char btdatatype;
typedef struct binarytreenode
{
	btdatatype data;
	struct binarytreenode* left;
	struct binarytreenode* right;
}BTnode;

2.2创建一个简单的链式二叉树 

BTnode* creatbinarytree()
{
	
	
		BTnode* nodeA = buynode('A');
		BTnode* nodeB = buynode('B');
		BTnode* nodeC = buynode('C');
		BTnode* nodeD = buynode('D');
		BTnode* nodeE = buynode('E');
		BTnode* nodeF = buynode('F');

		nodeA->left = nodeB;
		nodeA->right = nodeC;
		nodeB->left = nodeD;
		nodeC->left = nodeE;
		nodeC->right = nodeF;

		return nodeA;
	

}

ps：相关函数会在文章末尾统一展示

3.前中后序遍历

⼆叉树的操作离不开树的遍历，我们先来看看⼆叉树的遍历有哪些⽅式。

3.1遍历规则

按照规则，⼆叉树的遍历有：前序/中序/后序的递归结构遍历：

1.前序遍历(PreorderTraversal亦称先序遍历)：访问根结点的操作发⽣在遍历其左右⼦树之前

 访问顺序为：根结点、左⼦树、右⼦树

2.中序遍历(InorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之中（间）

访问顺序为：左⼦树、根结点、右⼦树

3.后序遍历(PostorderTraversal)：访问根结点的操作发⽣在遍历其左右⼦树之后

 访问顺序为：左⼦树、右⼦树、根结点

 3.1.1遍历的思想

我们在链式二叉树的遍历中一般采用递归思想，如下图所示

3.1.2前序遍历

void preorder(BTnode* root)//前序遍历，中左右
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preorder(root->left);
	preorder(root->right);
}

 因为是前序所以在访问节点时先对储存数据的部分进行操作，打印出来后进行下一步。

当遇到下一个节点为空时就返回。

结果如图

3.1.3中序遍历 

void inorder(BTnode* root)//中序遍历，左中右
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
		inorder(root->left);
		printf("%c ", root->data);
		inorder(root->right);
	}
}

3.1.4后序遍历

void postorder(BTnode* root)//后序遍历，左右根
{
	if (root == NULL)
	{
		printf("NULL ");
		return;

	}
	postorder(root->left);
	postorder(root->right);
	printf("%c ", root->data);
	
}

3.2求二叉树节点个数 

如果需要求一个二叉树节点的个数，我们需要怎么做呢

我们这里提供两个方法

首先是创建一个变量size，每经历一个节点，让其自加。

int BinaryTreeSize2(BTnode* root,int* psize)//求二叉树节点个数
{
	
	if (root == NULL)
	{
		printf("%p\n", root);
		return 0;
	}
	(*psize)++;
	BinaryTreeSize2(root->left,psize);
	BinaryTreeSize2(root->right,psize);
	return *psize;
	
}

第二个思路就是不额外创建变量， 用经历过节点的数目直接实现

int BinaryTreeSize1(BTnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize1(root->left)
		+ BinaryTreeSize1(root->right);
}

3.3求二叉树的深度

int BinaryTreeDepth(BTnode* root)//求二叉树深度
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = BinaryTreeDepth(root->left);
	int rightdep = BinaryTreeDepth(root->right);
	return 1 + (leftdep > rightdep ? leftdep : rightdep);
}

其思想就是走到最下层节点，向上每一层加一。

3.4二叉树的查找函数 

BTnode* BinaryTreeFind(BTnode* root, btdatatype x)//在二叉树中查找
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTnode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)//如果左子树未找到
	{
		return leftfind;
	}
	BTnode* rightfind= BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}

先遍历左子树数，再遍历右子树进行查找。

4.层序遍历

  除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数 为1，层序遍历就是从所在⼆叉树的根结点出发，⾸先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，⾃上⽽下，⾃左⾄右逐层访问树的结点的过程就是层 序遍历。

而层序遍历需要借助一个我们学过的数据结构，队列，其相对应知识可以看前文

【数据结构】栈与队列

其核心思想就是当首先放进去的节点记录，将其取出，判断其两个子节点是否为空，如果非空就将其放入，然后循环这个过程，直至将队列的所有数据取出来

void leverorder(BTnode* root)//层序遍历
{
	QU q;
	QUinit(&q);
	QUpushi(&q, root);

	while (!QUempty(&q))//当队列不为时
	{
		//取队头，出队头
		BTnode* top = QUfront(&q);
		QUpop(&q);
		printf("%c ", top->data);
		//将队头非空左右孩子入列
		if (top->left)
			QUpushi(&q, top->left);
		if (top->right)
			QUpushi(&q, top->right);
	}
	
}

5.完整代码实现

.h文件

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef char btdatatype;
typedef struct binarytreenode
{
	btdatatype data;
	struct binarytreenode* left;
	struct binarytreenode* right;
}BTnode;

void preorder(BTnode* root);//前序遍历，中左右
void inorder(BTnode* root);//中序遍历，左中右
BTnode* buynode(char x);//创建节点
int BinaryTreeSize1(BTnode* root);//求二叉树节点个数
int BinaryTreeSize2(BTnode* root,int* psize);//求二叉树节点个数
int BinaryTreeDepth(BTnode* root);//求二叉树深度
BTnode* BinaryTreeFind(BTnode* root, btdatatype x);//在二叉树中查找
void BinaryTreeDestory(BTnode** root);//二叉树销毁
void leverorder(BTnode* root);//层序遍历

.c文件 

#define _CRT_SECURE_NO_WARNINGS
#include"tree.h"
#include"Queue.h"

BTnode* buynode(char x)
{
	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}

void preorder(BTnode* root)//前序遍历，中左右
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->data);
	preorder(root->left);
	preorder(root->right);
}
void inorder(BTnode* root)//中序遍历，左中右
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
		inorder(root->left);
		printf("%c ", root->data);
		inorder(root->right);
	}
}
void postorder(BTnode* root)//后序遍历，左右根
{
	if (root == NULL)
	{
		printf("NULL ");
		return;

	}
	postorder(root->left);
	postorder(root->right);
	printf("%c ", root->data);
	
}

int BinaryTreeSize2(BTnode* root,int* psize)//求二叉树节点个数
{
	
	if (root == NULL)
	{
		printf("%p\n", root);
		return 0;
	}
	(*psize)++;
	BinaryTreeSize2(root->left,psize);
	BinaryTreeSize2(root->right,psize);
	return *psize;
	
}
int BinaryTreeSize1(BTnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize1(root->left)
		+ BinaryTreeSize1(root->right);
}

int BinaryTreeDepth(BTnode* root)//求二叉树深度
{
	if (root == NULL)
	{
		return 0;
	}
	int leftdep = BinaryTreeDepth(root->left);
	int rightdep = BinaryTreeDepth(root->right);
	return 1 + (leftdep > rightdep ? leftdep : rightdep);
}

BTnode* BinaryTreeFind(BTnode* root, btdatatype x)//在二叉树中查找
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTnode* leftfind = BinaryTreeFind(root->left, x);
	if (leftfind)//如果左子树未找到
	{
		return leftfind;
	}
	BTnode* rightfind= BinaryTreeFind(root->right, x);
	if (rightfind)
	{
		return rightfind;
	}
	return NULL;
}
void BinaryTreeDestory(BTnode** root)//二叉树的销毁
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}
void leverorder(BTnode* root)//层序遍历
{
	QU q;
	QUinit(&q);
	QUpushi(&q, root);

	while (!QUempty(&q))//当队列不为时
	{
		//取队头，出队头
		BTnode* top = QUfront(&q);
		QUpop(&q);
		printf("%c ", top->data);
		//将队头非空左右孩子入列
		if (top->left)
			QUpushi(&q, top->left);
		if (top->right)
			QUpushi(&q, top->right);
	}
	
}

.c文件（测试）

#define _CRT_SECURE_NO_WARNINGS
#include"tree.h"
BTnode* creatbinarytree()
{
	
	
		BTnode* nodeA = buynode('A');
		BTnode* nodeB = buynode('B');
		BTnode* nodeC = buynode('C');
		BTnode* nodeD = buynode('D');
		BTnode* nodeE = buynode('E');
		BTnode* nodeF = buynode('F');

		nodeA->left = nodeB;
		nodeA->right = nodeC;
		nodeB->left = nodeD;
		nodeC->left = nodeE;
		nodeC->right = nodeF;

		return nodeA;
	

}
void test01()
{
	BTnode* root = creatbinarytree();
	preorder(root);
	/*if (BinaryTreeFind(root, 'F'))
	{
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}*/
}
void test02()
{
	BTnode* root = creatbinarytree();
    int size = 0;
	printf("size:%d\n", BinaryTreeSize1(root));
	printf("size:%d\n", BinaryTreeSize2(root,&size));
}
void test03()
{
	BTnode* root = creatbinarytree();
	leverorder(root);
}
int main()
{
	
	test01();
	//test02();
	/*test03();*/
	return 0;
}

本次的分享就到这里了，感谢阅读！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布