数据结构之链式结构二叉树的实现（初级版）

本文内容将主会多次用到函数递归知识！！！

本节内容需要借助画图才能更好理解！！！

和往常一样，还是创建三个文件

这是tree.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef char btdatatype;
//定义二叉树结点结果
typedef struct binarytreenode
{
	btdatatype data;
	struct binarytreenode* left;
	struct binarytreenode* right;
}btnode;

//前序遍历
void preorder(btnode* root);
//中序遍历
void InOrder(btnode* root);
//后序遍历
void PostOrder(btnode* root);

// ⼆叉树结点个数
int BinaryTreeSize(btnode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(btnode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(btnode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(btnode* root);
// ⼆叉树查找值为x的结点
btnode* BinaryTreeFind(btnode* root, btdatatype x);
// ⼆叉树销毁
void BinaryTreeDestory(btnode** root);

这是tree.c

​
#include"tree.h"
//先序遍历--根左右
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 BinaryTreeSize(btnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(btnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(btnode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right, k - 1);
	//从上往下索引，索引一层就k-1
}
//⼆叉树的深度/⾼度  ？？？
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);
}
// ⼆叉树查找值为x的结点
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;
}
//传二级指针可以这样简单理解，销毁即把指向这一空间的指针（地址）置为NULL，而我们的root是一个一级指针，要将其销毁，则需要将其地址置为NULL，故传二级指针
void BinaryTreeDestory(btnode** root)
{
	if (*root == NULL)
	{
		return;
	}BinaryTreeDestory(&((*root)->right));
	
	BinaryTreeDestory(&((*root)->left));
	free(*root);
	*root = NULL;
}
​

这是test.c

​
#include"tree.h"
btnode* buynode(btdatatype x)
{
	btnode* node = (btnode*)malloc(sizeof(btnode));
	assert(node);
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//手动构造一棵二叉树
btnode* createtree()
{
	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 test()
{
	btnode* root = createtree();
	preorder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");

	printf("size:%d\n", BinaryTreeSize(root));
	printf("size:%d\n", BinaryTreeSize(root));

	printf("leaf size:%d\n", BinaryTreeLeafSize(root));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 2));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 3));
	printf("k size:%d\n", BinaryTreeLevelKSize(root, 1));
	printf("depth:%d\n", BinaryTreeDepth(root));
	btnode* find = BinaryTreeFind(root, 'A');
	if (find == NULL)
	{
		printf("not found!");
	}
	else
	{
		printf("we've found it!");
	}
    BinaryTreeDestory(&root);
}
int main()
{
	test();
	return 0;
}

​

说明：

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