数据结构——二叉树

好，上一篇我们已经讲过了堆，也已经了解了二叉树的基础知识后，我们今天来实现二叉树的相关代码。

由于初始二叉树，由于现在对二叉树结构掌握还不够深入，为了降低学习成本，此处我们来手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

 

我们已经了解了树的结构基本是下面框架了：

所以我们可以根据上面框架写出以下的结构代码：

定义 

typedef int BTDataType;
typedef struct BinaryTreeNode
{数据BTDataType data;充当左子树struct BinaryTreeNode* left;充当右子树struct BinaryTreeNode* right;
}BTNode;

 

在编写简单的二叉树之前，我们首先得知道下面的类型定义：

以上面这幅图来举例：

简单来说，这几个用到的都要递归的方法。

注意说明：若根左右子树没有数字，即为空的话，用NULL来显示（更直观地看出其中的结论）。

1.前序遍历：根->左子树->右子树。

1）按照上图的例子，这里得到的顺序就是：

1，2，3，NULL,NULL,NULL,4,5,NULL,NULL,6,NULL,NULL.

为什么呢？现在我们来具体讲解：

把它分别看作整体，即上面划分出来的。

因为，它的顺序是根，左子树，右子树

首先，1就是根，接着到2是1的左子树，而2又是单独的根。

是不是有得按照它规定的顺序来，根2的左子树是3，3又是单独的根，再寻找3的左子树，即NULL

然后到找3的右子树==NULL，这是不是就意味着2的左子树找完了，之后，才到2的右子树==NULL

完了，到1的右子树==4，4是单独的根，到找4左子树==5，5是单独根，找5左子树==NULL，

到5右子树==NULL,完了就回到4的右子树6，6是单独根，找6左子树==NULL，6的右子树==NULL

最后返回最开始==结束。

根据上面颜色我们可以发现：每种颜色文字出现的顺序都是：根->左子树->右子树

同时，同种颜色不相邻--->这就是递归的原因。其实这也可以发现明白递归的一下规律了。

 

2.中序遍历：左子树->根->右子树：

有了上面的具体讲解，这里就不过多的讲解了，下面给出它的顺序，可以自己来验证一下：

NULL,3,NULL,2,NULL,1,NULL,5,NULL,4,NULL,6,NULL

 

3.后序遍历：左子树->右子树->根

同样：

NULL,NULL,3,NULL,2,NULL,NULL,5,NULL,NULL,6,4,1

 

层序遍历：一层一层算过去

1，2，3，4，5，6

 

好了，了解了之后，我们来用代码实现一下。

我们还是得malloc一下

BuyNode部分

BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

这相当于初始化嘛，先malloc，创建好开始的。相当于：

 

初步之后，我们开始搭建树的结构了。

CreatTree部分

BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node3->right = node7;return node1;
}

即

搭建好树的结构后，再想要是前序还是中序或是后序都变得非常简单了。

前序遍历：

void PreOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}

但是呢，如果有疑惑的话，不妨我们画出它的递归展开图：

上面就是它递归的全过程。

这里是不是就是前序的规则得出：

1，2，4，NULL,NULL,5,NULL,NULL,3,6,NULL,NULL,7,NULL,NULL.

上面我们写的对了。

 

中序遍历

void InOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

它的递归展开图：

 

后序遍历 

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

同样的递归图，就不一一画了，可以试试画，你会更清楚的。

 

求节点的个数

怎么求呢？

就以学校的关系来举例吧：

一个校长要求算出整个学校的人数总数，那么会有：

1）校长亲自去一个一个班去数人头个数。

2）吩咐各级领导统计，逐级上报。

这样上报人数明显更加方便，对吧？

同样方法一，就像是第一种情况，能不能干？可以干，但是效率太低了。 

方法一：

int size = 0;
void TreeSize(BTNode* root)
{if (root == NULL)return;++size;TreeSize(root->left);TreeSize(root->right);
}

如果不想把size弄外面的话也可以下面：

void TreeSize(BTNode* root, int* psize)
{if (root == NULL)return;++(*psize);TreeSize(root->left, psize);TreeSize(root->right, psize);
}

所以我们第二种方法：

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

加1是要把它本身也要加上。

它的递归展开图可以看出它的全过程。 

 

求树的高度

比如说上图： 得出：

当前树的高度=左右子树高的那个+1

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

有人可能会写出这样的一种代码，它虽然行，但是效率低。

为什么呢？这相当于你每次当每级人员把自己级的数据报给上级领导后，他没有记录下来，等到他要真正记录上报给他上级时，忘了数据，又要重新问，而你之前上报时也没有记录下来，也忘记了，这样每个人都忘记了，所以会造成每次一个级的领导要的时候，又要重新来一遍。这样的数据累计起来就非常多了。

所以，真正的是要把每次的数据记录下来，避免效率低下。

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

 

求在k层的个数

 

当前树第k层个数=左子树的第k-1层个数+右子树的第k-1层个数

 

int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1)+ TreeKLevel(root->right, k - 1);
}

递归展开图： 

 

 Find部分

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* lret = TreeFind(root->left, x);if (lret)   //返回的不为空就进return lret;BTNode* rret = TreeFind(root->right, x);if (rret)return rret;return NULL;
}

它的递归展开图：

找下图中的6数字

 

层序遍历

这里需要用到队列的代码，因为，之前在堆那里讲到我们树实质是数组

而队列的规则：先进先出，    这符合我们的层序遍历。

这里，我们就只要把之前写过的Queue队列的代码形成文件，拿过来就可以了 。

但是呢：需要注意的是：

一定一定要更改*********不然就会错！！！！！（问就是我没改，找了好久没找到！！！！）

因为你不同类型了，现在是树，之前只是整形

原来的
//typedef int  QDatatype; 
改后的
typedef struct BinaryTreeNode*  QDatatype;typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;

这里的原理就是：

出一层，带入下一层

void LevelOrder(BTNode* root)
{Queue q;//初始化QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){注意： 这里不是int*BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if(front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}QueueDestroy(&q);
}

解读：

1.首先，肯定是要把一开始的根push进去队列

2.正式进入循环（不为空）

3.要记录下对头的数据，防止之后Pop删除之后，找不到，而无法打印出这个数字。

4.接着Push左子树，右子树。

5.队列要进行开始初始化，结束要销毁，防止内存泄漏。

 

判断是否是完全二叉树

 

这里的方法也是要使用到队列的知识点

我们之前了解过，完全二叉树的概念：除了最后一层，都是满的二叉树，且最后一层从做开始，是连续的，中间不能为空。

按照这种情况，我们不妨有以下思路：

利用层序遍历，（出一层，带入下一层），直到出现空的前一个数，再进行循环，如果后面空中出现了非空，则证明不是。

如上图，5和6出完之后，剩下的全都是空，说明它是完全二叉树的。 

bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);//层序遍历while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}// 判断是不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 后面有非空，说明非空节点不是完全连续if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

 

最后给出代码：

test部分

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>#include "Queue.h"typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node2->right = node7;return node1;
}void PreOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}void InOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}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;
}int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1)+ TreeKLevel(root->right, k - 1);
}// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;BTNode* lret = TreeFind(root->left, x);if (lret)return lret;BTNode* rret = TreeFind(root->right, x);if (rret)return rret;return NULL;
}void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if(front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}printf("\n");QueueDestroy(&q);
}// 判断二叉树是否是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if (root)QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}// 判断是不是完全二叉树while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);// 后面有非空，说明非空节点不是完全连续if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}// 二叉树销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
}int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");/*size = 0;TreeSize(root);printf("TreeSize:%d\n", size);size = 0;TreeSize(root);printf("TreeSize:%d\n", size);*//*int size1 = 0;TreeSize(root, &size1);printf("TreeSize:%d\n", size1);int size2 = 0;TreeSize(root, &size2);printf("TreeSize:%d\n", size2);*/printf("TreeSize:%d\n", TreeSize(root));printf("TreeSize:%d\n", TreeSize(root));printf("TreeSize:%d\n", TreeSize(root));printf("TreeHeight:%d\n", TreeHeight(root));printf("TreeKLevel:%d\n", TreeKLevel(root, 3));printf("TreeKLevel:%d\n", TreeKLevel(root, 4));printf("TreeFind:%p\n", TreeFind(root, 5));printf("TreeFind:%p\n", TreeFind(root, 50));LevelOrder(root);printf("TreeComplete:%d\n", TreeComplete(root));TreeDestory(root);root = NULL;return 0;
}

Queue.c部分

#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDatatype x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);/*QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL)pq->tail = NULL;*/if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

    Queue.h部分

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef struct BinaryTreeNode*  QDatatype;typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);

每次鸡汤部分： 

最后，新的一年，希望大家都学有所成，勇敢飞。