二叉树的链式结构实现

前言

     该篇是在二叉树介绍及堆-CSDN博客的基础上的。该篇会有点抽象大家要自己多画画图自己感受一下。现在我们开始吧！

     在学习二叉树基本操作时，我们需要先有一个现成的二叉树。来方便我们练习。因为现在我们对二叉树的理解也并不是很深入。在这里创建一个树是方便让我们理解。等我们学的差不多的时候，我们来真正的创建二叉树。

     下图是我创建二叉树的结构。

typedef int BTDataType;
 
typedef struct BinaryTreeNode
{
	BTDataType date;
	struct BinaryTreeNode* leftchild;
	struct BinaryTreeNode* rightchild;
}BTNode;
 
BTNode* CreateNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	node->date = x;
	node->leftchild = node->rightchild = NULL;
 
	return node;
}
//手搓二叉树
BTNode* HandRub()
{
	BTNode* node1 = CreateNode(1);
	BTNode* node2 = CreateNode(2);
	BTNode* node3 = CreateNode(3);
	BTNode* node4 = CreateNode(4);
	BTNode* node5 = CreateNode(5);
	BTNode* node6 = CreateNode(6);
 
	node1->leftchild = node2;
	node2->leftchild = node3;
	node1->rightchild = node4;
	node4->leftchild = node5;
	node4->rightchild = node6;
 
	return node1;
}

     在二叉树的介绍及堆这篇文章中的二叉树概念可以发现二叉树定义是递归式的，因此下面操作中基本都是按照该概念实现的。

遍历

     二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作一次。

二叉树的遍历有三种。

1. 前序遍历：先访问根节点，在遍历左子树，后遍历右子树。
2. 中序遍历：先遍历左子树，在访问根节点，后遍历右子树。
3. 后序遍历：先遍历左子树，在遍历右子树，后访问根节点。

     在遍历中假设遇到空指针则打印N。

前序遍历

     根据前面提到的前序遍历，可以知道会先访问1节点，然后在遍历1节点的左孩子也就是2节点。走到2节点时要重新进行前序遍历，所以会先访问2节点，然后在遍历2节点的左孩子节点也就是3节点。然后在访问3节点，然后遍历3节点的左孩子，但3节点没有左孩子。根据前序遍历它会遍历3节点的右孩子，但3节点没有右孩子。这时它会返回到2节点，遍历2节点的右孩子(2节点本身和左孩子都已经访问过了，根据前序遍历规则它会遍历2节点的右孩子)。2节点没有右孩子，它会返回到1节点的右孩子，然后在次遍历。右边与左边同理。

     不要看的它很复杂，实际上思想还是挺简单的。 

     上面遍历完之后的结果应该是：1 2 3 N N N 4 5 N N 6 N N。

     上面说的就很符合递归的特点，把一个大问题拆成与原问题相似，但规模较小的子问题。

//前序遍历
void preOrder(BTNode* ret)
{
	if (ret == NULL)//判断传入节点是否为空指针
	{
		printf("N ");
		return;
	}
	printf("%d ", ret->date);
	preOrder(ret->leftchild);
	preOrder(ret->rightchild);
}

     这里的ret == NULL 有两个作用，在下面提供的代码中类似这段的都有该功能

1. 判断传过来的树是不是空树。
2. 当左子树或右子树遍历完之后开始回归。

     验证一下我们上面自己写出的结果。

     可以发现我们自己写的和运行出来的结果没区别。这么复杂的过程用递归实现竟然这么简短，这就是递归的魅力！

中序遍历

     中序遍历和前序遍历原理是一样的，差别只是访问的次序不同，体现在代码上就上顺序的差异。

//中序遍历
void InOrder(BTNode* ret)
{
	if (ret == NULL)
	{
		printf("N ");
		return;
	}
 
	InOrder(ret->leftchild);
	printf("%d ", ret->date);
	InOrder(ret->rightchild);
}

后序遍历

     同样的，后序遍历和前序遍历原理是一样的，差别只是访问的次序不同，体现在代码上就上顺序的差异。

//后序遍历
void PostOrder(BTNode* ret)
{
	if (ret == NULL)
	{
		printf("N ");
		return;
	}
 
	PostOrder(ret->leftchild);
	PostOrder(ret->rightchild);
	printf("%d ", ret->date);
}

用遍历结果推树的结构

     已知1 2 3 4 5 7 6是前序遍历结果，3 2 1 5 7 4 6是中序遍历结果。求该二叉树的结构。

     由前序遍历结果可知1是根节点，由中序遍历规则可以分开该树的左子树和右子树。

     左子树结构：看前序遍历1之后是2，由前序遍历的特点先根在左后右，得2是1的左孩子，由前序遍历的特点得3是2的左孩子，3由于下一个是4它在右子树中，所以2没有右孩子且3是叶子。

     右子树结构：因为下一个是4，所以4是1的右孩子。由中序遍历的先左在根后右。可以判断4的左子树是57，右子树是6。前序遍历中4之后是5，所以5是4的左孩子

7是5的右孩子。为什么？如果7是5的左孩子那么在前序遍历中7会在5之前。

     最后的结构如下：

     如果没看懂上面写的那就对二叉树遍历理解不太好。

节点个数

总节点数

     最简单的方式就是传一个Size来计数。然后用遍历一遍即可。要判断传入节点是否为空指针。

     注意：这里要传Size的地址（函数每次调用会开辟一个栈帧，里面会存放函数的内容，其中就有Size。当函数调用完后栈帧会被销毁掉，Size保留的数据会被销毁，如果这样Size就无法起到它的作用）。

void TreeSize(BTNode* root, int* Size)
{
	if (root == NULL)
		return;
 
	(*Size)++;
	TreeSize(root->leftchild, Size);
	TreeSize(root->rightchild, Size);
}

     上面的写法可以实现目的，那能不能不创建Size来实现呢？其实是可以的。

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

     我在这里就只写了左子树，右子树与它相似大家可以自己试试。大家要结合图好好的理解感受一下。

     

叶子节点数

     什么时候是叶子节点呢？

     大家想一下叶子节点有什么特点，它没有孩子这就说明了它的左孩子和右孩子是相同的（在创建节点时默认左孩子和右孩子都为NULL）。这就是判断是否为叶节点的判断条件。

    求叶子节点个数和求节点个数的思想是一致的。其实也就遍历一遍，只不过加了额外的判断条件。

     要判断传入节点是否为空指针。如果判断条件如果成立就返回1，否则就继续。

int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return root->leftchild == root->rightchild ? 1 : TreeLeafSize(root->leftchild) + TreeLeafSize(root->rightchild);
}

第k层节点数

     在这里要先认定第一层的高度为1不是0（有些书上会把第一层的高度认为是0）。

     假设我们要第二层的节点数。

     由上图可知，当k == 1时即到了该层 。其它的就和上面的求叶子节点个数一样了。

     我们需要的是第1层，当k小于1就没必要在继续了返回就行了。还有要判断传入节点是否为空指针。

int TreeNodeSize(BTNode* root, int k)
{
	if (k < 1 || root == NULL)
		return 0;
 
	return k == 1 ? 1 : TreeNodeSize(root->leftchild, k - 1) + TreeNodeSize(root->rightchild, k - 1);
}

查找值为x的节点

     先找根节点再在左子树中找后在右子树中找。这和前序遍历很像。只是在前序遍历的基础上加了点限制条件。

     在遍历左子树和右子树时，要记录一下返回值，别你找到了没带回来，这就尴尬了。

     要判断传入的节点是否为空。遇到要找的值那就一直返回，直到跳出该函数。在此之前要加个判断返回的该节点不为NULL。如果没找到那就返回NULL。

BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;
	if (root->date == x)
		return root;
 
	BTNode* ret1 = TreeFind(root->leftchild, x);
	if (ret1)
		return ret1;
	BTNode* ret2 = TreeFind(root->rightchild, x);
	if (ret2)
		return ret2;
 
	return NULL;
}

创建二叉树

     好了，经过上面知识的学习相信大家对二叉树有了一定的理解，现在让我们创建二叉树吧！

     我们要创建一个数组，用来存放值和空指针。为什么要存放空指针呢？如果不存放那就有可能是任意一种遍历。在这里我将用#来表示空指针。传入的是数组，数组需要下标来找数据，所以在传参时要传下标的地址（其原因和求节点数传地址的道理是一样的）。

     这里我用输入是前序遍历的情况来表示(下面的代码仅适用于前序遍历输入)。

     要先判断是否为空，后让下标加加，加加时不要写在判断条件上，因为如果不是空的话在判断之后下标会加加那就少了一个值。然后创建节点再把值放进去后加加，然后构建左子树怎么做呢？让节点的左孩子调用该函数即可。右子树的构建同理。最后返回创建节点即可。

BTNode* CreateTree(char* arr, int* i)
{
    if(arr[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    TNode* root = (TNode*)malloc(sizeof(TNode));
    root->val = arr[(*i)++];
    root->left = CreateTree(arr, i);
    root->right = CreateTree(arr, i);
 
    return root;
}

---