数据结构第九讲：二叉树

这一讲我们要实现二叉树的链式结构，二叉树结构体中包含了数据、指向左孩子节点的指针和指向右孩子节点的指针，在这一讲中，我们将要体会的递归的暴力！！！

1.实现链式结构二叉树

1.1二叉树的节点结构

//二叉树的节点结构
typedef int BinaryTreeDataType;typedef struct BinaryTreeNode
{BinaryTreeDataType data;//保存数据struct BinaryTreeNode* left;//指向左孩子节点struct BinaryTreeNode* right;//指向右孩子节点
}BTNode;

1.2创建二叉树节点

也就是为二叉树创建节点，并将节点进行初始化

//创建二叉树节点
BTNode* BuyBTNode(int val)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");return NULL;}newnode->data = val;newnode->left = newnode->right = NULL;return newnode;
}

1.3前中后序遍历

接下来我们要实现的是二叉树的遍历：

二叉树的遍历操作分为三种：前序遍历、中序遍历、后序遍历：

可以看出：这里区分的前中后其实就是根节点遍历的顺序
我们先总体看三种遍历的不同：

接下来我们来实现三种遍历，注意：三种遍历方法的代码实现非常简单，主要是思路的体会，三种方法都是使用的递归的思想：

1.3.1前序遍历

//前序遍历
//函数传入的是树的根节点
void PreOrder(BTNode* root)
{if (root == NULL){return;}//将节点的数据进行打印printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

对于递归，return之后只是一个递归函数终止，然而形参的值不变，函数会继续向下执行，形成一个全新的递归函数：

1.3.2中序遍历

//中序遍历
void InOrder(BTNode* root)
{//也就是左根右进行遍历if (root == NULL){return;}//先对左边的数据进行读取，其实就是将左边的节点当成是根节点进行传入InOrder(root->left);//先打印根节点的值，然后再检查右节点是否为空printf("%d ", root->data);//当右节点不为空时，它会按照从上向下的顺序一直走到右节点的尽头//当然，当有右节点中存在左节点时，会先走左节点的循环，因为左节点的循环在上//而且会一下走到左节点的尽头，然后从下往上遍历左节点InOrder(root->right);
}

1.3.3后序遍历

//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}//仍然是先走到最后一个左节点PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

1.3.4总结

1.4二叉树结点的个数

1.4.1错误示范

根据我们之前所讲，那么我们应该会有一个初步的思路，我们先实现一下：

//二叉树结点个数
//先定义一个变量sz
int sz = 0;
int BTSize(BTNode* root)
{if (root == NULL){return 0;}//每循环一次，那么就将sz++一次++sz;BTSize(root->left);BTSize(root->right);return sz;
}

这时打印的结果也是非常beautiful啊，和预想的一样，但是，当我们这样时：

//二叉树结点个数
int size = BTSize(n1);
printf("%d ", size);//6
size = BTSize(n1);
printf("%d ", size);//12

我们就会惊奇地发现：结点的次数竟然会随着函数调用次数的增加而成倍地增长！原因就是使用了全局变量，全局变量在函数使用后不会销毁，那么我们就要进行更改了：

1.4.2实现方法

//二叉树结点个数
int BTSize(BTNode* root)
{if (root == NULL){return 0;}//返回左节点的个数和右节点的个数return 1 + BTSize(root->left) + BTSize(root->right);
}

1.5二叉树叶子结点的个数

//二叉树叶子结点个数
int BTLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}//这里的返回值也会参与加法运算，所以会呈现出累加的效果//也就是说，返回值会存储到BTLeafSize(root->left)或另一个函数中，然后再进入加法运算//返回左边的树的叶子节点个数 + 右边的树的叶子结点个数return BTLeafSize(root->left) + BTLeafSize(root->right);
}

对于递归，先搞清总体思路，如上边的：返回左边的树的叶子节点个数 + 右边的树的叶子结点个数，然后再想清楚结束条件，如：当左节点和右节点都为0时返回1，此时会发现递归已经写完了！！！

1.6二叉树第k层结点的个数

//二叉树第k层结点的个数
int BTLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//返回条件：当k = 1时if (k == 1){return 1;}//返回左边的二叉树第k层的节点个数和右边二叉树第k层的结点个数return BTLevelKSize(root->left, k - 1) + BTLevelKSize(root->right, k - 1);
}

1.7二叉树的深度/高度

要想在递归的过程中对数据逐渐进行增大，必须要让return返回的值被接收，而且参与递归运算，这里是创建变量进行存储，还可以使用递归函数进行存储，如：1+BTDeapth(root->right)（这里是瞎写，仅代表一个格式）

//二叉树的深度/高度
int BTDepth(BTNode* root)
{if (root == NULL){return 0;}int leftdepth = BTDepth(root->left);int rightdepth = BTDepth(root->right);//要想在递归的过程中对数据逐渐进行增大，必须要让return返回的值被接收，而且参与递归运算//这里是创建变量进行存储//还可以使用递归函数进行存储，如：1+BTDeapth(root->right)（这里是瞎写，仅代表一个格式）return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}

1.8二叉树查找值为x的结点

//二叉树查找值为x的结点
BTNode* BTFind(BTNode* root, BinaryTreeDataType x)
{if (root == NULL){return NULL;}//返回条件：当数据是我们想要的数据时，就进行返回if (root->data == x){return root;}BTNode* left = BTFind(root->left, x);if (left){//这里要十分注意的是：//这里的return表示的是整个函数的返回，上面的return代表的是递归函数的返回//原因就在于使用了一个值来接受递归函数的返回值，使得递归函数结束递归了//如果这里不适用变量来接受的话，函数将会错误返回return left;}BTNode* right = BTFind(root->right, x);if (right){return right;}return NULL;
}

1.9二叉树的销毁

//二叉树的销毁
//因为销毁要改变指针的指针的指向，所以这里传的是二级指针
void BTDestory(BTNode** root)
{if (*root == NULL){return;}//这里的传参要注意：因为是二级指针接收，所以传入的应该是一级指针的地址//直接遍历所有结点，然后一一删除即可BTDestory(&(*root)->left);BTDestory(&(*root)->right);free(*root);*root = NULL;
}

2.二叉树的层序遍历

2.1什么是层序遍历

层序遍历就是按照层数，从左到右一次对数据进行遍历：

2.2层序遍历的实现

2.2.1实现思路

对于递归，它会一直执行下去，直到遇到结束条件，然而，这个算法中，并不支持递归的使用，因为我们想不出来什么结束条件能够成立，所以这时我们就想到了其它的方法：队列！！！

下面我们来看实现方法：

2.2.2先创建一个队列

恰巧我们刚刚学过了队列，所以我们完全可以将之前写的队列代码拿过来，但是要注意的是，之前我们所实现的队列中保存的值为int类型，但是现在因为插入的值为BTNode*类型，所以还要将类别进行更改：

//结点结构体
//尽管我们之前已经使用typedef将结构体的名字改变成了BTNode*
//这里仍然需要加上struct，否则编译器会识别不出来，万一是一个变量名呢对不对
typedef struct BTNode* QueueDataType;typedef struct QueueNode
{//和链表一样，也需要结点进行链接QueueDataType val;struct QueueNode* next;
}QueueNode;

2.2.3代码的实现

//二叉树层序遍历
void LevelOrder(BTNode* root)
{//先创建一个队列Queue q;//队列初始化Init(&q);//将二叉树链表入队列QueuePush(&q, root);//循环，当队列为空时结束循环,当队列不为空时进行循环while (!QueueEmpty(&q)){//将一个结点出队列BTNode* ret = QueueFront(&q);printf("%d ", ret->data);QueuePop(&q);//如果有左右结点的话，按顺序入队列if (ret->left){QueuePush(&q, ret->left);}if (ret->right){QueuePush(&q, ret->right);}}Destory(&q);
}

3.判断是否为完全二叉树

3.1解题思路

这一道题目仍然是应用队列的知识：

3.2代码实现

//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* n1)
{//先创建一个队列Queue q;Init(&q);//先将二叉树中的数据全部插入到队列中//先将对头元素插入到队列中QueuePush(&q, n1);while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){break;}//如果top不为空，将top的左孩子结点和右孩子结点入队，这样就保障了NULL结点的入队QueuePush(&q, top->left);QueuePush(&q, top->right);}//入队完成之后，检查队列中的数据，不能够存在一个NULL数据while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);//如果存在不为空的数据，返回falseif (top){Destory(&q);return false;}}Destory(&q);return true;
}