二叉树的创建销毁和如何层序遍历_二叉树的销毁

大家好！前面的二叉树的学习，我们都是先手动构建二叉树的，这篇就说一下如何真正的去构建一棵二叉树。而且，我还会说一下前面没有说的一种遍历方式：层序遍历。

如何层序遍历

我们要进行层序遍历，要借助一个数据结构——队列。
思路：
1.先把根入队列，借助队列先进先出的性质。
2.上一层节点出的时候，带下一层的节点进去。

下面，我举个例子：

首先，我将1放到队列中：

我们看队列不为空，我们将1取出来，然后把它的孩子2和4带进去。

我们看队列不为空，我们将2取出来，然后把它的孩子3带进去，NULL就不进去了。

我们看队列不为空，我们将4取出来，然后把它的孩子5和6带进去

队列不为空，我们将3取出来，它的孩子都是NULL，不进去

队列不为空，我们将5取出来，它的孩子都是NULL，不进去

队列不为空，我们将6取出来，它的孩子都是NULL，不进去

当队列为空就结束了。

代码如下：

判断二叉树是否是完全二叉树

我们知道完全二叉树前n-1层是满的，最后一层是连续的。
那我们该如何判断呢？用的就是上面层序遍历的思想。
解题思路：
1.层序遍历，NULL也进队列
2.遇到NULL以后，出队列中所有数据。如果全是NULL，就是完全二叉树，如果有非NULL，就不是。

就看上面举的例子：


你会发现，当遇到NULL时，后面还有5，6，那么就说明不是完全二叉树。

那么如果是这样的一个二叉树：

你就会发现当遇到NULL时，后面全是NULL：

这样，我们用代码来实现：

二叉树的创建

那么一个二叉树我们该如何真正的去创建呢？
我来举个例子：

假设，我们用前序遍历的方式来创建这个二叉树，#号代表NULL。
构建的二叉树应该是这个样子：

代码如下：

typedef struct BrinyTreeNode
{
    struct BrinyTreeNode* left;
    struct BrinyTreeNode* right;
    char data;
}BTNode;

BTNode* CreateTree(char* arr,int* pi)
{
    //当遇到NULL时，就返回
    if(arr[(*pi)]=='#')
    {
        (*pi)++;
        return NULL;
    }
	//如果不是NULL，就开辟节点的空间
    BTNode* root=(BTNode*)malloc(sizeof(BTNode));
    
    root->data=arr[(*pi)++];
 	//递归到左边右边，连接起来
    root->left=CreateTree(arr,pi);
    root->right=CreateTree(arr,pi);
    
    return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二叉树的销毁

二叉树的销毁只能是后序遍历，如果是前序和中序的话，那么根会先销毁，就找不到它的孩子了。

代码如下：

void BTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}
1
2
3
4
5
6
7
8
9
10
11

如果大家觉得有帮助，希望能够多多支持！谢谢大家！