阅读量:0
数据结构第九讲：二叉树
这一讲我们要实现二叉树的链式结构，二叉树结构体中包含了数据、指向左孩子节点的指针和指向右孩子节点的指针，在这一讲中，我们将要体会的递归的暴力！！！
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); //如果存在不为空的数据，返回false if (top) { Destory(&q); return false; } } Destory(&q); return true; } 