C语言二叉树

树的基本概念：

 度：一个节点含有的子节点的个数叫做这个节点的度。列如A的度就是2

叶子节点：没有子节点的节点，叫叶子。例如：D、G、H、F

父亲节点：有一个及以上的子节点的节点，叫父节点。

子节点：有一个爹，他就是子节点，子节点也能是别人的父节点。父节点也能是别人的子节点。

        就像你的爸爸，就是关于你的父节点，你自己就是关于你爸的子节点，你爸也是关于你爷爷的子节点。

兄弟节点 ：同一个爹，的两个及以上的节点叫兄弟节点。G,H就是兄弟节点，因为他们有同一个父节点。

树的度： 一个节点有最多的子节点个数，叫做整个数的度，看谁生的多，最多的就是度

如图,最多就是2，那么书的度就是2.

树的高度：从第一节点，开始为1，去数他的子节点连接起来后，最长的那个就是树高。

如图的书高就是4

祖先：就是一个子节点，爹的爹的爹的爹……。子节点上面的一串都是他的祖先包括他爹，直到开山先祖（也就是没有父节点的那个节点为止） ，A就是开山先祖，A，B，E都是G的祖先

        反之儿的儿的儿的儿的儿，就是子孙，每一个都是开山先祖的子孙。B，E，G都是A的子孙

两种树的表示方法

一、孩子兄弟表示法：在结构体里定义两个指针，一个用来指向子节点，一个用来指向同级节点。

二、双亲表示法：用数组实现，只存父亲节点的下标。

二叉树的基本概念

每个节点的子节点不超过两个的树，叫二叉树

特殊二叉树：

        满二叉树：每一个节点都有两个子节点（叶子除外）。

               节点个数计算：如果知道高度 h ，那么个数就是，2的h次方减1。诀窍在于，2的N次方等于，2的0次方一直加到2的N-1次方，再加一。

                比如：2的4次方等于16，他就等于，1(0次方)+2(1次方)+4(2次方)+8(3次方)+1=16

        完全二叉树：假设树的高度为4，只有第四层的节点不是满的。并且第四层的节点抽象来看从左往右必须是连续的，最左边不能为NULL就完了呗（不一定对）。

二叉树的性质：

        叶子节点个数，等于度为2的节点个数加一。如下图有4个叶子节点D G H F，度为2的节点有3个 A B E,加一刚好相等

        完全二叉树节点问题：

                如果一个完全二叉树的节点是 2n 个，也就是说节点个数是偶数，那么必然会有一个度为1的节点。

递归深度层序遍历

        

         前序： 根，左子树 ，右子树。每来到一个左子树也时是先访问根，再去看这个左子树的左子树

        解析：先访问 A 再访问左子树 B，再访问左子树 D，因为 D 为叶子节点，所以去看 B 的右子树 E，进来访问E后又去访问 G，G 为叶子访问完后，去看 E 的右子树访问E完后，访问H，H为叶子。关键的来了。此时我们B这个左子树就算访问完了，就得去看A的右子树了。

        简化版顺序：A B D E G H C F（有效节点顺序） 

        完整版：A , B , D, NULL , NULL , E , G , NULL , NULL , H , NULL , NULL , (当找到左子树的右叶子时，就可以去找右子树的叶子了) ，C  , NULL , F , NULL , NULL 

最终也是成功通过

创建的测试代码

int main()
{
	BTNode* t1 = (BTNode*)malloc(sizeof(BTNode));
	if (t1 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t1->data = 'A';
	t1->left = NULL;
	t1->right = NULL;
	BTNode* t2 = (BTNode*)malloc(sizeof(BTNode));
	if (t2 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t2->data = 'B';
	t2->left = NULL;
	t2->right = NULL;
	BTNode* t3 = (BTNode*)malloc(sizeof(BTNode));
	if (t3 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t3->data = 'C';
	t3->left = NULL;
	t3->right = NULL;
	BTNode* t4 = (BTNode*)malloc(sizeof(BTNode));
	if (t4 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t4->data = 'D';
	t4->left = NULL;
	t4->right = NULL;
	BTNode* t5 = (BTNode*)malloc(sizeof(BTNode));
	if (t5 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t5->data = 'E';
	t5->left = NULL;
	t5->right = NULL;
	BTNode* t6 = (BTNode*)malloc(sizeof(BTNode));
	if (t6 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t6->data = 'F';
	t6->left = NULL;
	t6->right = NULL;
	BTNode* t7 = (BTNode*)malloc(sizeof(BTNode));
	if (t7 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t7->data = 'G';
	t7->left = NULL;
	t7->right = NULL;
	BTNode* t8 = (BTNode*)malloc(sizeof(BTNode));
	if (t8 == NULL)
	{
		perror("malloc::fail");
		return EOF;
	}
	t8->data = 'H';
	t8->left = NULL;
	t8->right = NULL;
	t1->left = t2;
	t1->right = t3;
	t2->left = t4;
	t2->right = t5;
	t3->left = NULL;
	t3->right = t6;
	t5->left = t7;
	t5->right = t8;
	PrevOrder(t1);
}

递归解析：（只讲前序），观看顺序就是从左往右看，注意连线和粉红色字体就行。

中序：左子树 ，根 ，右子树

        从D开始访问，完了回到B（根）访问B，再去看右子树，进去之后先访问G再是E，再去看右子树H，访问完后，来到C，左子树为空掠过访问C，再去看右子树，F的两个都是空，访问F。

        简化版顺序：D B G E H A C F

        完整版为：NULL D NULLL B NULL G NULL E NULL H NULL （A的左子树）,A NULL C NULL F NULL 。（A的右子树）

    

    后序： 左子树，右子树 ，根

二叉树计算：

        节点计算：我们把二叉树的左右节点叫做左子树和右子树，即使他是一个叶子，也叫左右子树，我们要有左右子树的这种观念，递归下去看的是一棵树，而不只是单纯的一个节点。

int NodeSize(BTNode* root)//求节点个数
{
	if (root == NULL)//判断节点为空嘛？
	{
		return 0;//为空返回0 
	}
	else
	{	//不为空返回1+他的左子树的节点个数，以及右子树节点个数
		return 1 + NodeSize(root->left) + NodeSize(root->right);
	}
}

如果这个节点不为空，则会去看左子树的节点个数，和右子树的节点个数

        叶子节点：

int TreeLeafSize(BTNode* root)//叶子的个数
{
	if (root == NULL)//解决空树
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;

	}//看这个节点是不是叶子，是就返回1不是就来到else
	else
	{	//去看他的左右子树的统计个数
		return TreeLeafSize(root->left) + TreeLeafSize(root->right);

	}
		
}

为叶子节点时开始返回，根会记录下左右子树有几个叶子节点。

深度计算：

int maxDepth(BTNode* root)//求树的深度
{
	if (root == NULL)
		return 0;
	else
	{
		int left = maxDepth(root->left);//记录左子树深度
		int right = maxDepth(root->right);//记录右子树的深度

		if (left > right)
		{
			return 1 + left;//如果说左子树的深度大于右子树，返回左子树的深度再+1,
							//+1表示根的这一层
		}
		else
			return 1 + right;//这样就只会得到一边的深度另一边抛弃
							 //就算是度为0的子树也会返回1；
	}
}

深度为：1（代表根这一层）+左右子树深度更大的那一个

平衡树判断：

 用深度函数，计算出深度，然后判断

bool isbalance(BTNode* root)
{
	if (root == NULL)
		return true;
	int left = maxDepth(root->left);
	int right = maxDepth(root->right);//左右子树的深度

	if ((left - right < 2) && (left - right > -2))//判断
		return true;
	else
		return false;
	
}