数据结构------二叉树简单介绍及实现

如果不是满二叉树或者完全二叉树，就要用链式存储

//搜索二叉树：左子树的所有值比根小，右子树的所有值比根大

// 实现查找，最多找高度次（类似二分法）

//二分查找存在的问题：排序；必须对数组操作，插入删除不方便。

//同一个函数不同的值递归占用的空间是一样的，因为销毁了之后再接着用

//不能递归的深度太深，不然会导致栈溢出

//这段二叉树的递归代码编译完了之后是一份指令，这份指令会自己调用自己，不断建立栈帧，然后销毁栈帧

//一些基本知识点

满二叉树每层节点个数构成一个等比数列

增加一个度为1的节点，一定减少一个度为0的节点。增加一个度为2的节点，一定增加一个度为0的，减少一个度为1的。因为0变到1再变到2。

//由性质3得：

//注意：完全二叉树度为1的节点只可能为1或0

//用满二叉树公式来推，计算一个大概的范围

//根据前序.中序序列写出二叉树

//前序确定根，中序分割左右子树

//一定注意7是右子树，因为中序是左根右

//递归的逻辑过程

//递归的物理过程

//通过ebp（高地址，用来保存主调函数的下一行指令）和esp（低地址，不断建立栈帧开辟空间）

//static静态变量只初始化一次，在多次调用的时候会出现问题，可以改为指针或全局变量（最好不要用），全局变量每次使用的时候记得进行初始化

//求节点个数采用分治思想：分而治之，上一层来指挥下一层

//求叶子节点个数：

//这样写就出错了，当该树为空或者没有左/右结点的时候，访问空指针的下一个节点就崩溃了

//所以应该单独讨论节点为空的时候

//求二叉树高度：

//错误做法：效率问题，超出时间限制

计算左/右子树高度值，左边递归到6，6的左右节点都为0，然后6的值为1。

然后回溯到3，3的左子树返回0，右子树返回1，相比较右子树高度大，即计算右子树高度+1，又因为此时并没有保存6的高度为1这个值，还要继续计算3的右子树6的左子树和右子树的高度值再比较然后再回溯到3，把值+1赋值给3这个节点。

然后3向上回溯到2，2的左子树的高度值为2，右子树高度值为0，相比较应该取左子树的高度值。但此时这个值并没有保存下来，应该再计算3的高度值，此时3的高度值未知，要比较3的左右子树的高度值......（计算方法同上一段）

//综述：节点深度越深，该节点计算次数成倍数增加

//正确做法（把值记录下来）：

//总的代码：

//实现二叉树
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;

	return node;
}

BTNode* CreatBinaryTree()
{
	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(6);


	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	node5->right = node7;

	return node1;
}

//遍历只需要注意顺序就好，打印的都是data
//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

int fun(int n)
{
	if (n == 0)
		return 0;

	return fun(n - 1) + n;
}

// 错误示范
//错因：不能用静态变量，因为如果调用多次这个函数的话，size是一直累加的
//     不能计算出每一次调用时的节点个数
//int TreeSize(BTNode* root)
//{
//	static int size = 0;
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//
//	return size;
//}
//以下两种解法太复杂
//解法1：把它变成全局变量，并且要注意在每次主函数中调用该函数之前要把size初始化为零
//int size = 0;
//int TreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	else
//		++size;
//
//	TreeSize(root->left);
//	TreeSize(root->right);
//
//	return size;
//}
//解法2：把size的指针传进去，通过指针解引用再++来改变size的值
//void TreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//		return 0;
//	else
//		++(*psize);
//
//	TreeSize(root->left, psize);
//	TreeSize(root->right, psize);
//}

//求节点个数
//采用分治递归的思想
//1.该节点不存在：节点数为零
//2.该节点存在，节点数=左子树节点数+右子树节点数+1
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 :
		TreeSize(root->left) + TreeSize(root->right) + 1;
}

//求叶子节点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left)
		+ TreeLeafSize(root->right);
}

//求深度（树高）
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ?
		leftHeight + 1 : rightHeight + 1;
}

// 有效率问题
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	return TreeHeight(root->left) > TreeHeight(root->right) ?
		TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

//int fmax(int x, int y)
//{
//	return x > y ? x : y;
//}

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

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");

	InOrder(root);
	printf("\n");

	//递归太深导致栈溢出
	//printf("%d\n", fun(10000));

	/*int size = 0;
	TreeSize(root, &size);
	printf("TreeSize:%d\n",size);

	size = 0;
	TreeSize(root, &size);
	printf("TreeSize:%d\n", size);*/

	printf("TreeSize:%d\n", TreeSize(root));
	printf("TreeLeafSize:%d\n", TreeLeafSize(root));
	printf("TreeHeight:%d\n", TreeHeight(root));

	return 0;
}