二叉树的链式结构

 1.实现链式结构二叉树

用链表来表示⼀棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 ， 其结构如下：

Tree.h //定义二叉树的链式结构 //二叉树结点的结构 //二叉树一个结点有两个指针，指向左子树和右子树 typedef int BTDateTypde; typedef struct BinaryTreeNode {     BTDateTypde data;     struct BinaryTreeNode* left;     struct BinaryTreeNode* right; }BTNode;

二叉树的创建方式比较复杂，为了更好的步入到⼆叉树内容中，我们先手动创建⼀棵链式二叉树。 

text.c //创建结点的结构 //由于创建一个结点需要一直申请新结点，我们可以创建一个函数（BuyNode（））来专门申请新结点 #include"Tree.h" BTNode* BuyNode(BTDateTypde x) {     BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));     if (newnode == NULL)     {         perror("malloc fail!");         exit(1);     }     newnode->data = x;     newnode->left = newnode->right = NULL;     return newnode; } void creatTreeNode() {     BTNode* node1 = BuyNode(1);     BTNode* node2 = BuyNode(2);     BTNode* node3 = BuyNode(3);     BTNode* node4 = BuyNode(4);     node1->left = node2;     node1->right = node3;     node2->left = node4; } int main() {     creatTreeNode();     return 0; }

调试结果：

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根结点、根结点的左子树、根结点的右子树组成的。

根结点的左子树和右子树分别是由子树结点、子树结点的左子树、子树结点的右子树组成的，因此

二叉树定义是递归式的,后序链式二叉树的操作中基本都是按照该概念实现的。

1.1 前中后序遍历

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式。

1.1.1 遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前

访问顺序为：根结点、左子树、右子树（根左右）

2）中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）

访问顺序为：左子树、根结点、右子树（左根右）

3）后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后

访问顺序为：左子树、右子树、根结点（左右根）

1.1.2 代码实现

链式二叉树就是一个递归结构。

前序遍历思想和打印结果

思路：root结点为1的结点，向下走，1的左孩子节点为2，再向下走，到2的结点，2的结点左孩子为4，向下走，到4结点，4的结点左孩子为空，此时左孩子空节点的函数栈帧销毁，返回结点4中函数PreOrder（root->right)，相当于进入结点4，此时4的右孩子为空，此时右孩子空节点的函数栈帧销毁，返回结点4中，此时4的函数栈帧中的代码已经走完，返回3......循环往复。（这里可以看绵姐的课再看看）

 中序遍历思想和打印结果

思想：root结点为1的结点，进入1的函数栈帧，进行代码的递归创建函数栈帧，也就是2结点的栈帧， 进行递归......循环往复。

后续遍历思想和打印结果

思想：root结点刚开始为1，然后进行递归，一步一步进行代码的实现......到右子树的时候，进入3这一结点，创建一个新的函数栈帧，相当于创建一个新的图中的代码，开始遍历，打印结果。 

1.2 结点个数以及高度等

// 二 叉树结点个数 int BinaryTreeSize(BTNode* root); // 二 叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root); // 二 叉树第 k 层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //二 叉树的深度  / 高 度 int BinaryTreeDepth (BTNode* root); // 二 叉树查找值为 x 的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二 叉树销毁 void BinaryTreeDestory (BTNode** root);

1.2.1 二叉树结点个数

int BinaryTreeSize(BTNode* root);

此时,若再次调用此函数，得到的结果为8，相当于size是第一次调用该函数的值。

 有同学会想，假如把size放在函数里面不就行了。其实是不行的，因为每次函数调用都会为形参开辟一个空间，因此要传的话要传地址。

正确的代码应该是如下所示：

 这张图是函数实现中的代码

 这张图是函数测试中的代码

 其实这种方法也不行，虽然结果是正确的。

正确代码如下：

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

思想：从1结点进入，返回的值是1+left（结点数）+right（右节点数），首先先递归到4，左右指数都是0，此时的值就是1，返回到结点2......

 此时，就算是运行两个这个代码也都是4，并且不需要初始化。

 1.2.2  二叉树叶子结点个数

int BinaryTreeLeafSize(BTNode* root);

代码实现：

思路：进入结点1，逐层递归，递归到4的结点的时候，如果4结点的左子树和右子树都为空，就返回值1，返回到节点2.....

1.2.3 二叉树第k层结点个数

int BinaryTreeLevelKSize(BTNode* root, int k);

代码实现：

思路：进入结点1，递归，并且K的值也在一直减1，一直递归到第K层的结点，当结点4下一左右结点为空时，返回0，不为空时返回1......

1.2.4 二叉树的深度/高度

int BinaryTreeDepth (BTNode* root);

 代码实现：

思路：刚开始进入结点1，向下运行代码，递归值用一个整数接收， 用一个三目操作符，哪个子树的值大，就返回哪个结点的值加1，1表示这个结点。

1.2.5 二叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); 

代码实现：

思路：进入结点1，运行函数，然后找结点，当值不为索要找的值时，递归，当找到结点时， 根据代码返回该结点，返回该节点定义的 find ，然后继续运行代码，继续返回该  find ，直到递推到结点1，然后就得到该结点了。

1.2.6 二叉树销毁（销毁左子树+销毁右子树+销毁根节点）

void BinaryTreeDestory (BTNode** root);

代码实现：

思路： 因为要改变结点的值，所以要传地址。刚开始进入结点1，递归到4，然后销毁......

若此时node1为NULL，说明销毁完成。 

2. 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第⼀层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

实现层序遍历需要额外借助数据结构：队列

// 层序遍历 void LevelOrder(BTNode* root) {     Queue q;     QueueInit(&q);     QueuePush(&q, root);     while (!QueueEmpty(&q))     {         BTNode* top = QueueFront(&q);         printf("%c ", top->data);         QueuePop(&q);         if (top->_left)         {             QueuePush(&q, top->_left);         }         if (top->_right)         {             QueuePush(&q, top->_right);         }     }     QueueDesTroy(&q); }

4.4 判断是否为完全二叉树

bool BinaryTreeComplete(BTNode* root) {     Queue q;     QueueInit(&q);     QueuePush(&q, root);     while (!QueueEmpty(&q))     {         BTNode* top = QueueFront(&q);         QueuePop(&q);         if (top == NULL)         {             break;         }         QueuePush(&q, top->left);         QueuePush(&q, top->right);     }     while (!QueueEmpty(&q))     {         BTNode* top = QueueFront(&q);             QueuePop(&q);         if (top != NULL)         {             QueueDesTroy(&q);             return false;         }     }     QueueDesTroy(&q);     return true; }

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