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

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

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

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

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

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

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

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

//一些基本知识点

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

增加一个度为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;
}