二叉链的四种排序且递归的运用 --二叉树

本文主要是介绍二叉链的四种排序且递归的运用 --二叉树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

三种排序的遍历

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = malloc(sizeof(BTNode));
	node->_data = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}
//构造
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');

	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node3->_left = node5;
	node3->_right = node6;
	return node1;
}
//前序遍历
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);
}
void TestTree()
{
	BTNode* root = CreatBinaryTree();
	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);

}
int main()
{
	//TestHeap();
	// TestTopk();
	TestTree();

	return 0;
}

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

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//创建节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}
//创建树
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode('A');
	BTNode* node2 = BuyNode('B');
	BTNode* node3 = BuyNode('C');
	BTNode* node4 = BuyNode('D');
	BTNode* node5 = BuyNode('E');
	BTNode* node6 = BuyNode('F');
	BTNode* node7 = BuyNode('G');

	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node3->left = node5;
	node3->right = node6;
	node4->left = node7;
	return node1;
}
// 二叉树节点个数
// 1、遍历  -- 全局变量
//int size = 0;
//void BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return;
//	else
//		++size;
//
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//}

// 2、遍历  -- 局部变量
//void BinaryTreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//		return;
//	else
//		++(*psize);
//
//	BinaryTreeSize(root->left, psize);
//	BinaryTreeSize(root->right, psize);
//}

// 3、分治
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1
		+ BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right);
}

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	else
	{
		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);
}

// 二叉树深度/高度
int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)
//	{
//		return NULL;
//	}
//
//	if (root->data == x)
//	{
//		return root;
//	}
//  //要是编译不过的话，要把BTNode换为struct BinaryTreeNode
//	BTNode* left = BinaryTreeFind(root->left, x);
//	if (left)
//		return left;
//	BTNode* right = BinaryTreeFind(root->right, x);
//	return right;
//}

 //二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (root == NULL)
//		return NULL;
//	
//	if (root->data == x)
//		return root;
//
//	BTNode* retLeft = BinaryTreeFind(root->left, x);
//	if (retLeft)
//	{
//		return retLeft;
//	}
//	//左边没找到才到右边找
//	BTNode* retRight = BinaryTreeFind(root->right, x);
//	if (retRight)
//	{
//		return retRight;
//	}
//
//	return NULL;//左右树都没找到返回空
//
//	//return BinaryTreeFind(root->right, x);
//}

int main()
{
	//全局变量算节点个数应注意的点
	//因为size为全局变量所以算两次节点的个数的时候需要重复令size为0
	//不然第二次算的节点树会是两倍（累加）
	/*BTNode* root = CreatBinaryTree();
	int size1 = 0;
	BinaryTreeSize(root, size1);
	printf("BinaryTreeSize:%d\n", size1);

	int size2 = 0;
	BinaryTreeSize(root, size2);
	printf("BinaryTreeSize:%d\n", size2);

	PreOrder(root);*/
	//局部变量算节点个数应注意的点
	//局部变量传的时候要传指而不是传值
	//传值的时候通过算的size为0来算出
	/*BTNode* root = CreatBinaryTree();
	int size1 = 0;
	BinaryTreeSize(root, &size1);
	printf("BinaryTreeSize:%d\n", size1);

	int size2 = 0;
	BinaryTreeSize(root, &size2);
	printf("BinaryTreeSize:%d\n", size2);

	PreOrder(root);*/
	//分治算节点个数
	//和递归比较--分治带返回值
	BTNode* root = CreatBinaryTree();
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
	printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
	printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));
	printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));

	/*BTNode* ret = BinaryTreeFind(root, 'V');
	if (ret)
	{
		printf("找到了\n");
	}
	else
	{
		printf("没有找到\n");
	}*/
	return 0;
}

第k层节点的个数

这篇关于二叉链的四种排序且递归的运用 --二叉树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！