数据结构——二叉树链式结构的实现(上)

二叉树概念

再看二叉树基本操作前，再回顾下二叉树的概念，

二叉树是：

1. 空树

2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的 

二叉树构成：根 左子树 右子树构成的。

前序遍历是 ：根 左子树 右子树

中序遍历是 ：左子树 根 右子树

后序遍历是：左子树 右子树 根

根据上面的插图 前序遍历应该是: 1 2 3 N N N 4 5 N N 6 N N

那么你能试着说出中序和后序吗？

中序和后序如下图所示，你看你写对了吗？

我们学习普通链式二叉树的增删查改是没有意义的，因为我们现在学习普通链式二叉树是为了以后的搜索二叉树和AVL 红黑树打基础的，还有就是很多二叉树的题，都是出在普通链式二叉树结构。

这是一个普通的搜索二叉树，二叉树的左子树比根小，右子树比根大。

如果搜索二叉树走中序遍历，就是个有序二叉树。

二叉树的构建

 在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。(注意：下述代码并不是创建二叉树的方式 )

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct BinaryTree
{
	struct BinaryTree* _left;
	struct BinaryTree* _right;
	int val;
}BTNode;
 
 
BTNode* buynode(int x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
 
	return newnode;
}
int main()
{
	BTNode* newnode1 = buynode(1);
	BTNode* newnode2 = buynode(2);
	BTNode* newnode3 = buynode(3);
	BTNode* newnode4 = buynode(4);
	BTNode* newnode5 = buynode(5);
	BTNode* newnode6 = buynode(6);
 
	newnode1->_left = newnode2;
	newnode2->_left = newnode3;
	newnode1->_right = newnode4;
	newnode4->_left = newnode5;
	newnode4->_right = newnode6;
 
    return 0;
}

二叉树的遍历 

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

前序遍历

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->_left);
	PreOrder(root->_right);
}

是不是觉得很简单？我们先运行下结果

跟我们之前预测的一模一样，为了更好的了解前序遍历，我画一下递归图。

 

中序遍历

就是把代码换个顺序就变成了中序遍历，为了深刻理解递归过程，建议像上面一样，自己画个递归过程理解。

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%d ", root->val);
	InOrder(root->_right);
}

运行结果

 

后序遍历

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%d ", root->val);
}

 运行结果

前序 中序 后序遍历结果

求节点个数以及高度等

二叉树的节点个数

很多人可能都是想这么求节点个数的，但其实是错误的方法，因为size是局部变量 出了作用域就销毁了 根本求不出正确节点个数。

那么我们加上static 让它变成静态变量呢？

可以求出正确答案，因为静态变量在静态区，全局变量也在静态区，相当于一个全局变量，出了作用域并不会被销毁，而且只会走一次初始化，因此答案是正确的。

但有一个问题，如果我要再次调用这个函数求节点个数呢？

答案就会是错误的，因为静态变量只会走一次初始化。

解决办法也有，就是在前面把size设为全局变量 再次调用时归为0即可 答案还是6，但这种方法太low了。 

正确的求节点个数代码

//节点个数
int Treesize(BTNode* root)
{
	return root == NULL ? 0 : 1 + Treesize(root->_left) + Treesize(root->_right);
}

 思路：比如学校里面要统计在校人数，校长不可能一个个问每个人+1+1+1......，而是布置任务，给辅导员或者班主任，班主任或者辅导员会布置给班长去统计各班学生个数，班长汇报给辅导员或班主任，班主任或者辅导员汇报给校长，校长最后在汇报结果加上自己，就是学校在校总人数。

二叉树的叶子节点个数

叶子节点就是度为0的节点。

首先要判断根为不为空

再判断根节点的左右结点存不存在即可。

//叶子结点
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);
}

二叉树第k层的节点个数

//第K层结点个数
int TreeKlevelsize(BTNode* root, int k)
{
	assert(k > 0);
 
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKlevelsize(root->_left, k - 1) + TreeKlevelsize(root->_right, k-1);
}

 

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef struct BinaryTree
{
	struct BinaryTree* _left;
	struct BinaryTree* _right;
	int val;
}BTNode;
 
 
BTNode* buynode(int x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->val = x;
	newnode->_left = NULL;
	newnode->_right = NULL;
 
	return newnode;
}
 
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->_left);
	PreOrder(root->_right);
}
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	InOrder(root->_left);
	printf("%d ", root->val);
	InOrder(root->_right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf(" NULL ");
		return;
	}
	PostOrder(root->_left);
	PostOrder(root->_right);
	printf("%d ", root->val);
}
 
//节点个数
int Treesize(BTNode* root)
{
	return root == NULL ? 0 : 1 + Treesize(root->_left) + Treesize(root->_right);
}
	
//叶子结点
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);
}
//第K层结点个数
int TreeKlevelsize(BTNode* root, int k)
{
	assert(k > 0);
 
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeKlevelsize(root->_left, k - 1) + TreeKlevelsize(root->_right, k-1);
}
int main()
{
	BTNode* newnode1 = buynode(1);
	BTNode* newnode2 = buynode(2);
	BTNode* newnode3 = buynode(3);
	BTNode* newnode4 = buynode(4);
	BTNode* newnode5 = buynode(5);
	BTNode* newnode6 = buynode(6);
 
	newnode1->_left = newnode2;
	newnode2->_left = newnode3;
	newnode1->_right = newnode4;
	newnode4->_left = newnode5;
	newnode4->_right = newnode6;
 
	PreOrder(newnode1);
	printf("\n");
	InOrder(newnode1);
	printf("\n");
	PostOrder(newnode1);
	printf("\n");
	printf("Treesize:%d\n", Treesize(newnode1));
	printf("Treeleafsize:%d\n", Treeleafsize(newnode1));
	printf(" TreeKlevelsize:%d\n", TreeKlevelsize(newnode1,3));
 
 
	
	return 0;
}