【数据结构】链式二叉树的实现和思路分析及二叉树OJ

【数据结构】链式二叉树的实现和思路分析及二叉树OJ

🔥个人主页：大白的编程日记

🔥专栏：数据结构

---

前言

哈喽，各位小伙伴大家好！上期讲的是用顺序表实现二叉树。今天咱们用链表的方式实现我们的二叉树。也就是链式结构。话不多说，咱们进入正题！向大厂冲锋！

一.链式二叉树的定义及结构

• 树的定义
  我们链式二叉树用结构体定义。结构体内包含节点的数据。然后还有指向左右孩子节点的结构体指针

typedef int DataType;
typedef struct BinaryTreeNode
{DataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

• 节点的创建

节点的创建我们需要malloc一个结构体。检查节点是否开辟成功。然后将节点数据赋值为X即可。再将左右指针指向空。最后返回开辟好的节点。

BTNode* BuyNode(int x)//创建树的节点
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");exit(1);}node->a = x;node->left = 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);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

这样一颗树二叉树就构建好了。

二.链式二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉
树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历
是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

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

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为
根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

任何一颗树都要分成根 左子树 右子树去按顺序遍历。
左右子树的访问又看成一颗树继续按照顺序去遍历。

2.1前序遍历

前序遍历访问顺序就是 根 左子树 右子树。
然后子树继续按照 根 左子树 右子树访问。
那我们先把一棵树的按照根 左子树 右子树拆分

• 代码实现
  我们前序遍历一颗树时分为两种情况
  一：树为空。那就不用访问了直接return结束。
  二：树不为空。那就先访问根节点(这里我们直接打印)。然后还需要继续左右子树前序遍历，那我们就递归函数解决。

void PrevOrder(BTNode* p)//前序遍历
{if (p == NULL){printf("N ");return;}printf("%d ", p->a);PrevOrder(p->left);PrevOrder(p->right);
}

• 逻辑分析
  逻辑上我们就是将一颗树的前序遍历分为根的访问和左子树的遍历和右子树。
  左右子树的遍历又看成一棵树的前序遍历。所以我们递归左右子树即可。

• 逻辑过程

我们都知道函数的调用需要在栈上开辟栈帧。
但是需要注意的是左子树开辟的栈帧函数调用结束销毁后
仍然存在内存中，调用右子树开辟的栈帧是重复利用左子树的栈帧。
所以函数的栈帧会重复利用。

2.2中序遍历

以此类推，中序就先递归左子树 再访问根 再递归右子树即可。

void InorOrder(BTNode* p)//中序遍历
{if (p == NULL){printf("N ");return;}InorOrder(p->left);printf("%d ", p->a);InorOrder(p->right);
}

2.3后序遍历

以此类推，中序就先访问根 递归左子树 再递归右子树即可。

void PostOrder(BTNode* p)//后序遍历
{if (p == NULL){printf("N ");return;}PostOrder(p->left);PostOrder(p->right);printf("%d ", p->a);
}

• 验证

2.4层序遍历

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

• 思路分析

上一层带下一层即可完成层序遍历。

• 代码实现

void TreeLevelOrder(BTNode* p)//层序遍历
{Queue pq;QueueInit(&pq);//初始化队列if(p)QueuePush(&pq, p);//第一层入队列while (!QueueEmpty(&pq))//队列不为空{BTNode* head = QueueFron(&pq);//取出队头数据QueuePop(&pq);//出队列printf("%d ", head->a);//访问if (head->left){QueuePush(&pq, head->left);//左孩子入队列}if (head->right){QueuePush(&pq, head->right);//右孩子入队列}}QueueDestroy(&pq);//销毁队列
}

三.链式二叉树功能函数

我们链式二叉树的实现不只是实现遍历而已。
我们还需要对二叉树实现求节点个数，树的高度等等。

3.1节点个数

• 遍历计数

我们很容易想到走一个遍历然后不为空用size++记录个数即可。
这确实是一种方法。那具体代码如何实现呢？

int TreeSize(BTNode* p)//树的节点个数
{int size;if (p == NULL){return 0;}size++;TreeSize(p->left);TreeSize(p->right);return  size;
}

这样写对吗？不对因为size是局部变量。每次函数调用size都会置为0.
这样就不能把节点个数累加起来。size之会累加第一次。

那我们是不是把他static改成静态让他的生命周期是全局的
这样每次size++都是同一个size就可以了呢？

int TreeSize(BTNode* p)//树的节点个数
{static int size=0;if (p == NULL){return 0;}size++;TreeSize(p->left);TreeSize(p->right);return  size;
}

我们发现结果确实是6。那我在调用一次呢？

我们发现第二次调用是12。为什么呢？因为局部静态变量只会初始化一次。
所以第二次调用6+6就是12.

int size;
int TreeSize(BTNode* p)//树的节点个数
{if (p == NULL){return 0;}size++;TreeSize(p->left);TreeSize(p->right);return  size;
}

那我们只能用全局的size然后每次函数调用前都要手动置0.

• 分治递归
  我们可以用递归的思想把大问题拆分成小问题解决。
  

int TreeSize(BTNode* p)//树的节点个数
{if (p == NULL){return 0;}return  TreeSize(p->left)+TreeSize(p->right)+1;
}

3.2第k层节点的个数

现在我们要求树的第k层节点的个数。我们该怎么求呢？
还是用递归的思想。

把问题转化为下一层第k-1层的递归求解即可。

int TreeLevelKSize(BTNode* p, int k)//第k层的节点
{if (p == NULL){return 0;}if (k == 1){return 1;}return TreeLevelKSize(p->left, k - 1)+TreeLevelKSize(p->right, k - 1);
}

3.3查找值为x的节点

现在我们要查找值为x的节点。一棵树可能有多个节点值为x。我们就返回找到的第一个节点即可。

利用递归分治的思想。将一棵树x节点的查找分为根节点 左子树 右子树的查找即可。

• 代码实现

BTNode* TreeFind(BTNode* p, int x)//查找值为k的节点
{if (p == NULL){return NULL;}if (p->a == x){return p;}BTNode* ret1 = TreeFind(p->left, x);BTNode* ret2 = TreeFind(p->right, x);return ret1 == NULL ? ret2 : ret1;
}

我们这样写对吗？
其实也算对。但是这样有小问题就是不管左子树存不存在x节点。都会去再查找右子树。这样就效率不太高。

BTNode* TreeFind(BTNode* p, int x)//查找值为k的节点
{if (p == NULL){return NULL;}if (p->a == x){return p;}BTNode* ret1 = TreeFind(p->left, x);if (ret1 != NULL){return ret1;}BTNode* ret2 = TreeFind(p->right, x);if (ret2 != NULL){return ret2;}return NULL;
}

所以我们最好对左子树的返回值检查一下。
如果不为空说明找到。直接return返回节点即可。

3.4树的销毁

那树如何销毁呢？

把树的销毁看成根的销毁 左右子树的销毁。
左右子树又是树的销毁 递归即可。

void TreeDestroy(BTNode* p)//树的销毁
{if (p == NULL){return ;}TreeDestroy(p->left);//销毁左子树TreeDestroy(p->right);//销毁右子树free(p);//销毁根节点
}

• 判断完全二叉树
  现在我们要判断一棵树是否时完全二叉树如何判断呢？
  
  我们只需要走一个层序遍历。然后出队列时孩子节点入队列即可。
• 代码实现

bool FullTree(BTNode* p)//判断是否满二叉树
{Queue pq;QueueInit(&pq);if (p)QueuePush(&pq, p);while (!QueueEmpty(&pq))//入队列{BTNode* head = QueueFron(&pq);QueuePop(&pq);//出队列if (head == NULL){break;}QueuePush(&pq, head->left);//左孩子入队列QueuePush(&pq, head->right);//右孩子入队列}while (!QueueEmpty(&pq)){BTNode* head = QueueFron(&pq);QueuePop(&pq);if (head)//找是否有非空节点{QueueDestroy(&pq);return false;}}QueueDestroy(&pq);return true;
}

四.二叉树OJ

4.1二叉树遍历

• 题目
  二叉树遍历
  
• 思路分析
  

这里我们还是用递归的方式。
根据前序遍历的思想构建树。然后走中序遍历即可。

• 代码实现

#include <stdio.h>
typedef char DataType;
typedef struct BinaryTreeNode {DataType a;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;
void InorOrder(BTNode* p)//中序遍历
{if (p == NULL){return;}InorOrder(p->left);printf("%c ", p->a);InorOrder(p->right);
}
BTNode* CreatTree(char* p, int* i) //构建树
{ //前序遍历if (p[*i] == '#')//不为空{(*i)++;return NULL;}BTNode* ret = (BTNode*)malloc(sizeof(BTNode));//创建一个节点if (ret == NULL){perror("malloc fali");exit(1);}ret->a = p[(*i)++];//赋值ret->left = CreatTree(p, i);//左节点ret->right = CreatTree(p, i);//右节点return ret;//返回节点}
int main() {char s[100];scanf("%s", &s);int i = 0;BTNode* ret = CreatTree(s, &i);//构建二叉树InorOrder(ret);//中序遍历return 0;
}

4.2左子叶之和

• 题目
  左子叶之和

• 思路分析
  
  这里我们还是用递归的思想将树的左子叶之和分为
  左子树左子叶+右子树左子叶之和即可。

• 代码实现

int sumOfLeftLeaves(struct TreeNode* root){if(root==NULL){return 0;}if(root->left&&(root->left->left==NULL&&root->left->right==NULL)){return root->right==NULL?root->left->val:sumOfLeftLeaves(root->right)+root->left->val;}return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
}

后言

这就是链式二叉树的实现以及二叉树OJ。这是数据结构中比较难也是重点内容。
大家一定要好好消化。今天就分享到这。感谢各位的耐心垂阅!咱们下期见！拜拜~