c语言——二叉树

//二叉树
typedef int BTDataType;
typedef struct BTNode
{
	BTDataType val;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;
BTNode* Creat_Node()
{
	BTNode* Node1 = BuyNode(1);
	BTNode* Node2 = BuyNode(2);
	BTNode* Node3 = BuyNode(3);
	BTNode* Node4 = BuyNode(4);
	BTNode* Node5 = BuyNode(5);
	BTNode* Node6 = BuyNode(6);
	//BTNode* Node7 = BuyNode(7);
	Node1->left = Node2;
	Node1->right = Node4;
	Node2->left = Node3;
	Node4->left = Node5;
	Node4->right = Node6;
	//Node6->right = Node7;
	return Node1;
}

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
	}
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

接下来依次介绍

1. 求二叉树大小

代码实现：

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

或者：

int BT_Size(BTNode* root)
{
	return root == NULL ? 0 : BT_Size(root->left) +
		BT_Size(root->right) + 1;
}

2. 求叶子结点个数

叶子结点有一个特点，那么就是左节点与右节点全为空，只要抓住这一点特点，利于递归，还是很好实现的。

int BT_Leaf_Size(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BT_Leaf_Size(root->left) +
		BT_Leaf_Size(root->right);
}

3.求深度

求二叉树深度可以转化为求左子树的深度，与右子树的深度，然后比比谁的大，然后左子树深度求法又可以分为，求左子树的左子树与右子树的深度，以此类推。

需要注意的是：需要每次存储每次递归的大小，优化时间

int BT_Depth_Size(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int left_Depth_Size = BT_Depth_Size(root->left);
	int right_Depth_Size = BT_Depth_Size(root->right);
	return left_Depth_Size > right_Depth_Size ?
		BT_Depth_Size(root->left) + 1 : 
		BT_Depth_Size(root->right) + 1;
}

4.求第k层的结点个数

思路就是首先我们要先找到第k层所在位置，然后每找到一个就利用递归然会去1；

int BT_Size_Levre_k(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BT_Size_Levre_k(root -> left, k - 1) +
		BT_Size_Levre_k(root -> right, k - 1);
}

5.寻找值为k的结点

需要注注意的是需要存储每次递归的ret，优化时间

BTNode* BTFind_Data_k(BTNode* root, int k)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->val == k)
	{
		return root;
	}
	BTNode* ret1 = BTFind_Data_k(root->left, k);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BTFind_Data_k(root->right, k);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}

6.层序遍历打印

前序： 根->左子树->右子树

void Prev_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	Prev_Order(root->left);
	Prev_Order(root->right);
}

中序： 左子树->根->右子树

void In_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	In_Order(root->left);
	printf("%d ", root->val);
	Prev_Order(root->right);
}

后序： 左子树->右子树->根

void Post_Order(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	In_Order(root->left);
	Prev_Order(root->right);
	printf("%d ", root->val);
}

层序：一层一层打印

层序打印需要运用到栈，这里不提供栈的实现了，只提供实现层序打印的代码

void Lever_Order(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->val);
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
}

7. 判断二叉树是否是完全二叉树

检查是否为完全二叉树，也是利用栈的知识来实现，因为在层序遍历的时候，是出完一层的时候也会在进完下一层，并且顺序是完全按照一层一层从左到右

所以实现思路就为，先找到第一个为空的结点，然后查看他后面的结点是不是为空，如果为空，那么就为完全二叉树，反之不是。

bool BinaryTreeComplete(BTNode* root)
{
	//层序遍历，从第一个为空开始，向后看是否为空
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	//检查后面是否为空  ，有非空即不是完全二叉树
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			return false;
		}
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	return true;
}

8.销毁

void BinaryTreeDestory(BTNode* root)//后序顺序释放
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

还有一些结论：

1：二叉树第i层上的结点数目最多为2i-1(i>=1)

2：深度为k的二叉树至多有2^(k) - 1个结点（k>=1）,叶子节点为 2^(k - 1)

3：包含n个结点的二叉树的高度至少为( log2(n) )+1

4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

5：leftchild=parent*2+1; rightchild=parent*2+2;

6: parent=(child-1)/2;

7: 令度为0，的结点个数为N0,度为2的个数为N2

那么N0=N2+1；

原文地址:https://blog.csdn.net/2301_81265915/article/details/138220501 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1785136015242039296.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部