【数据结构】二叉树链式结构的实现

1.前置说明

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

代码如下：

typedef int BTDataType;
typedef struct BinaryTreeNode
{
 BTDataType _data;
 struct BinaryTreeNode* _left;
 struct BinaryTreeNode* _right;
}BTNode;
 
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);
 
 node1->_left = node2;
 node1->_right = node4;
 node2->_left = node3;
 node4->_left = node5;
 node4->_right = node6;

 return  node1;
}

 二叉树是：

1. 空树

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

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。 

2.二叉树的遍历

前序、中序以及后序遍历 

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

 这里我们通常将二叉树分为三个部分  根 左子树 右子树

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序遍历递归图解：

使用递归 相当于函数栈帧不断创建 最后一个一个销毁 

前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 2 5 6 4 1 

这里为了方便理解 以前序为例 ： 我们按照 根 左子树 右子树 这样理解 ， 第一个根为 1，打印1，往左子树走，遇到第二个根为 2，打印2，继续往左子树走，遇到第三个根为 3，打印3，继续往左子树走 ，此时为空 ，为空此时往回走，3 的右子树也为空，在往回走，2的右子树为空，继续往回走，此时遍历1的右子树 ，以同样的方法继续遍历。

 代码实现

使用递归实现，重在理解递归函数栈帧的创建与销毁 

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);
}

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

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

3.二叉树结点个数

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

4.二叉树叶子结点个数

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);
}

5.二叉树的高度

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;
}

6.二叉树第k层结点个数

int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	// 子问题
	return TreeLevelKSize(root->left, k - 1)
		+ TreeLevelKSize(root->right, k - 1);
}

7.二叉树查找值为x的结点

BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
		return root;

	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

   初学者使用递归实现二叉树功能时，多画图理解可以解决大部分问题，二叉树的问题大部分情况要记得考虑空树的状况。