二叉树的C语言实现及遍历

前言

树是一种十分重要的基础数据结构。很多实际问题都会抽象成树来解决。而这篇文章要讲的二叉树则是树中最基本又很重要的一种特殊树。它只的是每个节点的度不大于2的树。

基于二叉树还有很多衍生的树。查找树，红黑树，平衡树等等等等。

基础思路

二叉树可以很形象的看做是一个递归的产物。所以二叉树的问题，基本都可以用递归来解决。无论一颗二叉树是什么样子的。他都可以看做三部分：本节点，左子树，右子树。
左子树也可以看成本节点，左子树，右子树。这样的结构。

就像图片上这样。所以一个树的节点需要三部分。保存本节点的数据。指向左节点（左子树），指向右节点（右子树）。当不存在左节点（左子树）或者右节点（右子树）时，则指向空就好。
于是我们就可以构造一个二叉树所需要的节点。

typedef struct TreeNode
{
	BTtype _val;
	struct TreeNode* _left;
	struct TreeNode* _right;
}BinaryTreeNode;

当然，根据需要一个节点也可以保存很多数据，比如一个学生的姓名学号生日电话等等等。

二叉树的建立

二叉树有很多种搭建方法。在不同的场景可以有用不同的方法。虽然二叉树是一种非线性的结构。我们依然可以使用数组来保存。

如果将根节点看做第零个节点的话，他的左孩子节点的下标等于父节点的下标的二倍加一，右孩子节点的下标等于父节点的下标的二倍加二。这样比较简单我就不贴代码了。
我们还是利用在上面建的节点。利用链式构成二叉树。我们确定一个根节点。然后让比根节点小的去左节点，比根节点大的去右节点。这样构成的树是一颗二叉查找树。当我们用中序遍历时，遍历结果就是升序的。

BinaryTreeNode* InitTree(BTtype *a,int nums)  //建树
{
	BinaryTreeNode* root;
	root = NULL;
	BinaryTreeNode* cur,*prev;
	for (int i = 0; i < nums; ++i)
	{
		BinaryTreeNode* newnode = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
		newnode->_val = a[i];
		newnode->_left = NULL;
		newnode->_right = NULL;
		if (NULL == root)   //说明这是树的第一个节点。
		{
			root = cur = newnode;
		}
		else     //执行else说明这棵树是有根节点的。
		{
			while (TRUE)
			{
				if (cur != NULL)   // 当前位置已经有节点了，所以要继续向下找位置
				{
					prev = cur;
					if (newnode->_val < cur->_val)  //向左子树移动
					{
						cur = cur->_left;
					}
					else if (newnode->_val > cur->_val)  //向右子树移动
					{				
						cur = cur->_right;
					}
				}
				else   //说明当前节点可以是空的 可以保存
				{
					if (prev->_val > newnode->_val)
						prev->_left = newnode;
					else
						prev->_right = newnode;
					break;
				}
			}
			cur = root;    //节点保存完毕， 需要返回root重新开始判断下一个节点往哪里保存。
		}
	}
	return root;
}

二叉树的遍历

我们提到了二叉树很形象的是递归的产物。 所以二叉树的问题用递归的思想会很方便处理。我们假设现在有一颗只有这样一颗只有三个节点的二叉树。

二叉树的遍历又有三种顺序：

• 前序遍历： 根节点，左节点 ，右节点
• 中序遍历：左节点，根节点，右节点
• 后序遍历: 左节点，右节点，根节点

而我们每遍历一个节点时，使用的方法都是一样的，所以我们只需要利用递归的想法。例如前序遍历： 先用前序遍历左子树，然后输出根节点，在用前序遍历右子树。当程序进入“前序遍历左子树”时，依然会满足这个逻辑。这样就可以完成二叉树的递归遍历。

void InOrder(BinaryTreeNode *root)    //中序遍历
{
	if (root != NULL)
	{
		InOrder(root->_left);
		printf("%d\n",root->_val);
		InOrder(root->_right);
	}
}
void PrevOrder(BinaryTreeNode *root)   // 前序遍历
{
	if (NULL != root)
	{
		printf("%d\n",root->_val);
		PrevOrder(root->_left);
		PrevOrder(root->_right);
	}
}
void PostOrder(BinaryTreeNode* root)  // 后序遍历
{
	if (NULL != root)
	{
		PostOrder(root->_left);
		PostOrder(root->_right);
		printf("%d\n", root->_val);
	}
}

在解决其他树的问题的时候也是这样的，掌握递归的思想会很有效的解决一些树的问题。但是，虽然递归是一个很好地解决问题的途径。但是递归会带来一些问题。比如没递归一次就需要重新开辟一片内存来跑函数。所以如果不能确定的控制递归的结束条件。递归就会无穷尽的下去。或者当递归层数很多时，代码的效率会很低。也很浪费内存。所以一些地方甚至会要求请尽量不要递归。当然，递归依然是一个处理问题的有效手段。
像求一颗树的节点个数，叶子节点个数，翻转二叉树等等问题上，递归依然可以让我们很快速的写出代码。

nt TreeSize(BinaryTreeNode *root)  //求树大小
{
	if (root == NULL)
		return 0;
	return TreeSize(root->_right)+TreeSize(root->_left)+1;

}

int TreeLeafSize(BinaryTreeNode *root)   //叶子数
{
	if (root == NULL)
		return 0;
	if (root->_left == NULL && root->_right == NULL)
		return 1;
	return TreeLeafSize(root->_left) + TreeLeafSize(root->_right);
	
}
int maxDepth(struct TreeNode* root)   //  二叉树深度
{

	int left, right;
	if (!root)
		return 0;
	left = maxDepth(root->_left);
	right = maxDepth(root->_right);
	return left > right ? left + 1 : right + 1;
}
struct TreeNode* invertTree(struct TreeNode* root) {  //翻转二叉树

	if (root != NULL)
	{
		struct TreeNode* newnode;
		newnode = root->_left;
		root->_left = root->_right;
		root->_right = newnode;
		invertTree(root->_left);
		invertTree(root->_right);
	}
	return root;
}