C语言典例|【数据结构】二叉树--链式结构链表|数据结构|c语言|c语言笔记

普通二叉树增删查改没有价值，单纯为了存储数据，不如使用线性表。
学习普通二叉树是为更好的控制它的结构，为后续学习更加复杂的搜索二叉树打基础。
平衡二叉树：AVL树，红黑树。

二叉树的概念：
1.空树
2.非空：根节点，根结点的左子树，根结点的右子树组成。
二叉树的概念：
1.空树
2.非空：根节点，根结点的左子树，根结点的右子树组成。

文章图片

根据概念可知：二叉树定义是递归的，因此后续基本操作按照递归进行。
二叉树的遍历前序，中序，后续遍历

文章图片

模拟遍历
1.前序遍历（先根遍历）：根左子树右子树
123456

文章图片

2.中序遍历（中根遍历）：左子树，根结点，右子树
321546

文章图片

3.后序遍历（后根遍历）：左子树，右子树，根
325641

文章图片

层序遍历：124356

模拟实现二叉树遍历构建链式结构

typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; //左树节点 struct BinaryTreeNode* right; //右数节点 BTDataType data; //节点值 }BTNode; BTNode* BinaryTreeFind(BTNode* root, BTDataType x); BTNode* BuyBTNode(BTDataType x) { //malloc节点 BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { printf("malloc failed!\n"); exit(-1); } BTNode* node = tmp; node->left = node->right = NULL; node->data = https://www.it610.com/article/x; return node; } //手动创建链式二叉树 BTNode* CreatBinaryTree() { BTNode* node1 = BuyBTNode(1); BTNode* node2 = BuyBTNode(2); BTNode* node3 = BuyBTNode(3); BTNode* node4 = BuyBTNode(4); BTNode* node5 = BuyBTNode(5); BTNode* node6 = BuyBTNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }

1.前序遍历
基本思路：根 - 左数- 右数

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

文章图片

文章图片

2.中序遍历
左子树 - 根结点- 右子树

//中序遍历 void InOrder(BTNode* tree) { if (tree == NULL) { printf("NULL "); return; } InOrder(tree->left); printf("%d ", tree->data); InOrder(tree->right); }

文章图片

文章图片

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

//后序遍历 void NextOrder(BTNode* tree) { if (tree == NULL) { printf("NULL "); return; } NextOrder(tree->left); NextOrder(tree->right); printf("%d ", tree->data); }

文章图片

4.求节点个数

【C语言典例|【数据结构】二叉树--链式结构】a.遍历＋计数

第一种：

1.遍历+计数 void BTSize(BTNode* tree, int* pCount) { if (tree == NULL) return; (*pCount)++; BTSize(tree->left,pCount); BTSize(tree->right, pCount); }

第二种：
定义一个全局遍历的计数器或者static定义一个静态局部变量。

int count = 0; int BTSize(BTNode* tree) { //static int count = 0; if (tree == NULL) return count; count++; BTSize(tree->left); BTSize(tree->right); return count; }

但这有一个致命的错误，多次调用返回的节点个数会错误。

文章图片

文章图片

原因：全局变量和静态局部变量都没办法没初始化为0。

b.分治：
分治思想：将复杂的问题分成规模更小的子问题，子问题再分为更小的子问题，……
方法：计算完左子树的节点个数再加上右节点的个数。
思想：递归

//分治 /*把复杂的问题，分成更小规模的子问题，子问题再分为更小的子问题……*///左子树算完再算右数再加上根节点 int BTSize(BTNode* tree) { if (tree == NULL) return 0; return BTSize(tree->left) + BTSize(tree->right) + 1; }

5.求叶子节点的个数

分治：计算完左树再计算完右树。

代码：

//求叶子结点的个数 //分治 int BTreeLeafSize(BTNode* tree) { if (tree == NULL) return 0; if (tree->left == NULL && tree->right == NULL) return 1; return BTreeLeafSize(tree->left) + BTreeLeafSize(tree->right); }

6.求第k层节点的个数

思路：将第k-1层的作为父亲节点，递推。

//第k层节点的个数int BTreeLevelSize(BTNode* tree,int k) { assert(k >= 1); if (tree == NULL) return 0; if (k == 1) return 1; //找到k-1层作为父亲节点，计算即可 return BTreeLevelSize(tree->left,k-1) + BTreeLevelSize(tree->right,k-1); }

7.问树高几何？

分治：计算左子树高度和右子树高度作比较，大的那个+1

//求树高几何？ int BTreeDepth(BTNode* tree) { //分治，左数算出高来，右数算出高来，比较取其大者 if (tree == NULL) return 0; return BTreeDepth(tree->left) > BTreeDepth(tree->right) ? BTreeDepth(tree->left) + 1 : BTreeDepth(tree->right) + 1; }

8.二叉树查找值为x的节点

思路：1）考虑分治思想，先递归左树，再递归右树。

2）找到就返回对应节点地址，炸藕到就返回NULL

3）判断返回的是为NULL 还是对应的节点。

//二叉树查找为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; //前序遍历 if (root->data =https://www.it610.com/article/= x) return root; //先遍历左树 BTNode* ret1 = BinaryTreeFind(root->left,x); if (ret1) return ret1; //遍历右树 BTNode* ret2 = BinaryTreeFind(root->right, x); if (ret2) return ret2; return NULL; }

9.层序遍历

思路：根据层序遍历的特性，可以使用队列解决。
当取出上一层的数据的时候，将上一层对应的left 和 right 入队列。

注意：C由于没有库，要取出我们之前自己实现的队列的文件，添加在该项目的相应位置。
记得在Queue.h上加入

文章图片

入队列的时候，入的是二叉树的一整个结构体，不单单是data
代码：

//层序遍历 /*根据层序遍历的特性，考虑将数据入队列，可以根据队列的性质，实现层序遍历当取出上一层数据的时候，将left 和 right 节点依次入队列*/ void LevelOrder(BTNode* tree) { //创建队列 Queue q; QueueInit(&q); //树不为空，入队列 if (tree) { QueuePush(&q,tree); } //将数据入队列。 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"); //销毁队列 QueueDestory(&q); }

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

思路：判断还是以队列为基础，层序遍历为辅。
入队列时，NULL也入队列，当出队列的时候遇到NULL时，开始将剩下的队列数据除队列，当剩下的数据中只有NULL时，则说明其是完全二叉树，否则就不是。

画图：

文章图片

这棵树就不是完全二叉树。
代码：

//判断二叉树是否为完全二叉树 /*以队列为基础，层序遍历为辅助，当遇到NULL时，将剩下的数据都出队列，当剩下的数据中只有NULL，则说明是完全二叉树，否则就不是文强案二叉树*/bool BTreeComplete(BTNode* root) { Queue q; QueueInit(&q); //若不为空，入队列 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //为空时跳出 if (front == NULL) break; //入队列 QueuePush(&q, front->left); QueuePush(&q, front->right); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) return false; } return true; }

11.销毁树