前言
之前我们已经学习了树和二叉树的概念,以及二叉树的顺序实现方式--堆,今天我们尝试以链式结构实现二叉树的一些功能(前中后序遍历、层序遍历、统计节点个数和树的高度,以及判断是否为完全二叉树等)。
一、节点的定义
以链式结构实现二叉树,即使用类似链表的方式,将数据存放于一个节点中,该节点的指针域存放指向左孩子和右孩子节点的指针。节点的定义如下:
typedef int BTDataType; //定义二叉树节点 typedef struct BinaryTreeNode { BTDataType data;//存放的数据 struct BinaryTreeNode* leftchild;//指向左孩子的指针 struct BinaryTreeNode* rightchild;//指向右孩子的指针 }BTNode;
二、创建一棵二叉树
由于目前我们所学习的二叉树结构并非是自平衡的,使用固定方法插入数据的意义不大,所以我们就来手动创建一棵二叉树,后续针对这棵二叉树,验证我们实现的方法。
1. 创建新节点
创建新节点的方式与链表相同。注意新节点的两指针都制为空:
//创建新节点 BTNode* BTBuyNode(BTDataType n) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间 if (newnode == NULL)//内存申请失败,则直接退出程序 { perror("malloc"); exit(1); } newnode->data = n; newnode->leftchild = newnode->rightchild = NULL; return newnode; }
2. 手动创建二叉树
接下来,我们创建一些节点,然后将这些节点连接起来,形成一颗二叉树。
//手动创建二叉树 BTNode* CreateTree() { //创建6个节点 BTNode* n1 = BTBuyNode(1); BTNode* n2 = BTBuyNode(2); BTNode* n3 = BTBuyNode(3); BTNode* n4 = BTBuyNode(4); BTNode* n5 = BTBuyNode(5); BTNode* n6 = BTBuyNode(6); //连接节点 n1->leftchild = n2; n1->rightchild = n3; n2->leftchild = n4; n2->rightchild = n5; n3->rightchild = n6; //返回根节点 return n1; }
二叉树已经创建好了,我们画一下它的逻辑结构图:
三、方法的声明
关于二叉树我们要实现的方法声明如下:
//前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //层序遍历 void LevelOrder(BTNode* root); //二叉树节点个数 int BTSize(BTNode* root); //叶子节点个数 int BTLeafSize(BTNode* root); //第K层节点个数 int BTLevelKSize(BTNode* root, int k); //二叉树高度 int BTDepth(BTNode* root); //查找 BTNode* BTFind(BTNode* root, BTDataType n); //判断是否为完全二叉树 bool BTComplete(BTNode* root); //销毁二叉树 void BTDestroy(BTNode** proot);
四、方法的实现
接下来,我们一一介绍并尝试实现这些方法。
1. 前、中、后序遍历
前、中、后序遍历是二叉树最常见、最重要的遍历方式。这三种遍历方式都将二叉树分为三个部分:根节点、左子树、右子树。理解这三种遍历方式,会加深我们对函数递归的理解。接下来我们一一讲解。
1.1 前(先)序遍历
所谓前序遍历,指的是在遍历二叉树时,访问根节点的操作发生在左右子树之前。它的访问顺序是:
根节点-->左子树-->右子树
当访问到每一棵子树时,这棵子树也可以再分为根节点、左子树、右子树,然后继续遵循这一套访问方式。不难发现,这是一个递归的过程。递归结束的条件是访问到空指针,意味着该节点的左子树或右子树不存在。
我们就刚才创建好的那个二叉树,分析一下对其前序遍历的结果:
遍历逻辑看似十分复杂,但是它的代码写起来却非常简单。接下来我们实现前序遍历:
//前序遍历 void PreOrder(BTNode* root) { if (root == NULL)//访问到空指针就停止遍历 { return; } printf("%d ", root->data);//打印根节点数据 PreOrder(root->leftchild);//遍历左子树 PreOrder(root->rightchild);//遍历右子树 }
代入测试:
int main() { BTNode* root = CreateTree(); PreOrder(root); return 0; }
运行结果:
1.2 中序遍历
中序遍历指的是访问根节点的操作发生在左右子树之中。它的遍历顺序是:
左子树-->根节点-->右子树
对于左右子树,它的访问逻辑与前序遍历相同,也是递归的。接下来我们分析中序遍历结果:
当然,它的代码也十分简单:
//中序遍历 void InOrder(BTNode* root) { if (root == NULL)//访问到空指针就停止遍历 { return; } InOrder(root->leftchild);//遍历左子树 printf("%d ", root->data);//打印根节点数据 InOrder(root->rightchild);//遍历右子树 }
测试结果:
1.3 后序遍历
后序遍历的含义是访问根节点的操作发生在其左右子树之后。它的遍历顺序是:
左子树-->右子树-->根节点
它的递归遍历逻辑不言而喻。遍历分析如下:
代码一如既往的简单:
//后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { return; } PostOrder(root->leftchild);//遍历左子树 PostOrder(root->rightchild);//遍历右子树 printf("%d ", root->data);//打印根节点数据 }
测试结果:
2. 层序遍历
所谓层序遍历,通俗地讲,就是从上到下,从左到右逐层遍历。对于我们创建的二叉树,它的遍历结果应该是:1,2,3,4,5,6。
进行层序遍历操作,需要借助数据结构“队列”来实现。关于队列,在博主的另一篇文章中有所实现:
https://developer.aliyun.com/article/1634734?spm=a2c6h.13262185.profile.33.2ca12c70iTcquf
在实现层序遍历时,队列相关函数我们就直接调用了,不再重复实现(注意将队列的数据元素类型调整为二叉树的节点指针类型)。接下来讲讲层序遍历的方法:
1.首先将头节点存放于队列当中。
2.如果队列不为空,则读取一个节点的数据,并让该节点出队。
3.读取一个节点的数据之后,若该节点有左子节点,则将左子节点入队;有右子节点,则将右子节点入队。
4.重复第2步,直到队列为空为止。
我们画图表示一下遍历过程:
不难发现,从上到下出队的数据依次排成了1,2,3,4,5,6。接下来,我们尝试写代码实现该过程:
//层序遍历 void LevelOrder(BTNode* root) { Queue q;//创建队列 QInit(&q);//初始化队列 QPush(&q, root);//根节点入队 while (!QEmpty(&q))//队列不为空,进入循环 { BTNode* front = QFront(&q);//记录队头数据 printf("%d ", front->data);//读数据 QPop(&q);//出队 if (front->leftchild != NULL) { QPush(&q, front->leftchild);//若左孩子不为空,则左孩子入队 } if (front->rightchild != NULL) { QPush(&q, front->rightchild);//若右孩子不为空,则右孩子入队 } } QDestroy(&q);//销毁队列 }
测试结果:
3. 二叉树节点个数
接下来,我们写一个函数统计二叉树节点个数。它的实现方法十分简单,当一个节点有效时,返回1,之后递归判断该节点的左右孩子是否有效......最后将这些“1”相加即可。代码如下:
//二叉树节点个数 int BTSize(BTNode* root) { if (root == NULL)//访问到空指针,则结束 { return 0; } return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效,返回1,再与左右孩子的判断结果相加 }
递归示意图:
测试结果:
4. 叶子节点个数
在统计叶子节点时,需要注意:叶子节点是度为0的节点。所以我们在做节点判断时,要判断该节点的左右孩子是否为空。如果都为空,则它是一个叶子节点。实现代码如下:
//叶子节点个数 int BTLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件,返回1 { return 1; } return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加 }
递归示意图:
测试结果:
5. 第K层节点个数
在统计第K层节点的个数时,我们不仅需要判断节点的有效性,而且需要确定该节点所在的层数。至于层数该怎么确定呢?
首先来看一段代码:
int main() { int arr[10] = { 1,2,3,4,5,6,7,8,9,10 }; int k = 5; int i = 0; while (k != 1) { k--; i++; } printf("%d\n", arr[i]); return 0; }
运行结果:
在这里,我们使用了一种特殊的方式访问数组中的第五个元素。我们循环使k自减,当k的值为1时,下标 i 就走到了第五个元素的位置处。而对于二叉树第k层节点的统计,也是这个原理。在使用递归时,每次遍历下一层(左右孩子)并传入k-1这个值,当k值为1时,再做统计,就实现了统计第k层节点的功能。代码实现:
//第K层节点个数 int BTLevelKSize(BTNode* root, int k) { if (root == NULL)//访问到空,返回0 { return 0; } if (k == 1)//k值为1,做统计 { return 1; } return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子(下一层) }
递归示意图:
测试代码与结果:
int main() { BTNode* root = CreateTree(); int k = 0; scanf("%d", &k); printf("第%d层节点个数为:%d\n", k, BTLevelKSize(root, k)); }
6. 二叉树高度
二叉树的高度计算原理十分简单,和之前节点个数的统计相似,当访问了一个有效节点之后,说明层数至少为1。之后再去访问它的左子树和右子树是否有效...这里需要注意:有时候二叉树的左子树和右子树高度不相同,需要将最高的那棵子树计入到高度当中。
代码实现:
//二叉树高度 int BTDepth(BTNode* root) { if (root == NULL)//根节点为空则为0层 { return 0; } int leftDepth = BTDepth(root->leftchild);//统计左子树高度 int rightDepth = BTDepth(root->rightchild);//统计右子树高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度,再与根节点层数相加 }
递归示意图:
测试结果:
7. 查找
查找的思路也比较简单,只需要遍历根节点、左子树、右子树,若找到相应的值,则将该节点返回即可。代码如下:
//查找 BTNode* BTFind(BTNode* root, BTDataType n) { if (root == NULL)//访问到空则停止 { return NULL; } if (root->data == n)//找到了,返回该节点 { return root; } BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树 if (leftFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回 { return leftFind; } BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树 if (rightFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回 { return rightFind; } }
测试代码及结果:
int main() { BTNode* root = CreateTree(); int x = 0; while (1) { scanf("%d", &x); if (BTFind(root, x) != NULL) { printf("找到了\n"); } else { printf("找不到\n"); } printf("\n"); } }
8. 判断是否为完全二叉树
我们在进行层序遍历二叉树时,是按照从上到下,从左到右的顺序进行的。由于完全二叉树最后一层的节点需要从左到右依次排列,我们就可以对这棵二叉树进行层序遍历。
如果遍历结果当中有两个节点之间有空指针,就说明这两个节点不是从左到右依次排列的,这棵二叉树也就不是完全二叉树了;反之,如果节点之间没有空指针,则说明它就是一棵完全二叉树。这里需要注意:由于要判断空指针的存在,遍历时就需要将空指针也存入队列。
我们针对创建好的二叉树,画个图演示一下执行流程:
代码实现:
//判断是否为完全二叉树 bool BTComplete(BTNode* root) { Queue q; QInit(&q);//初始化队列 QPush(&q, root);//根节点入队 while (!QEmpty(&q))//队列不为空进入循环 { BTNode* front = QFront(&q);//记录队头 QPop(&q);//队头出队 if (front == NULL)//当读取到空指针时,跳出循环 { break; } QPush(&q, front->leftchild);//左孩子入队 QPush(&q, front->rightchild);//右孩子入队 } //此时,再次循环读取队头数据,若读取到非空节点,说明不是完全二叉树 while (!QEmpty(&q)) { BTNode* front = QFront(&q);//记录队头 QPop(&q);//队头出队 if (front != NULL) { //出现非空节点 QDestroy(&q);//销毁队列 return false; } } //读完了所有的空指针,还没有遇到非空节点,说明是完全二叉树 QDestroy(&q);//销毁队列 return true; }
测试代码与结果:
int main() { BTNode* root = CreateTree(); if (BTComplete(root)) { printf("是完全二叉树\n"); } else { printf("不是完全二叉树\n"); } }
9. 销毁二叉树
完成了这么多的工作之后,我们就要销毁这棵二叉树了。销毁二叉树的过程与后序遍历相似,先将左右子树销毁,然后销毁根节点。由于这里会改变根节点的值,所以需要传入二级指针。
代码如下:
//销毁二叉树 void BTDestroy(BTNode** proot) { if (*proot == NULL)//访问到空指针则回退 { return; } BTDestroy(&((*proot)->leftchild));//销毁左子树(leftchild是一级指针,函数接收二级指针所以要取地址) BTDestroy(&((*proot)->rightchild));//销毁右子树(rightchild是一级指针,函数接收二级指针所以要取地址) free(*(proot));//销毁根节点 *proot = NULL; }
五、程序全部代码
辅助数据结构--队列:
typedef BTNode* QDataType; //定义队列 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化 void QInit(Queue* pq); //判空 bool QEmpty(Queue* pq); //入队列 void QPush(Queue* pq, QDataType n); //出队列 void QPop(Queue* pq); //取队头数据 QDataType QFront(Queue* pq); //取队尾数据 QDataType QBack(Queue* pq); //获取队列有效元素个数 int QSize(Queue* pq); //销毁 void QDestroy(Queue* pq); //初始化 void QInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } //判空 bool QEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; } //入队列 void QPush(Queue* pq, QDataType n) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc"); exit(1); } newnode->data = n; newnode->next = NULL; if (QEmpty(pq)) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = pq->ptail->next; } pq->size++; } //出队列 void QPop(Queue* pq) { assert(pq && !QEmpty(pq)); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } //取队头数据 QDataType QFront(Queue* pq) { assert(pq && !QEmpty(pq)); return pq->phead->data; } //取队尾数据 QDataType QBack(Queue* pq) { assert(pq && !QEmpty(pq)); return pq->ptail->data; } //获取队列有效元素个数 int QSize(Queue* pq) { assert(pq); return pq->size; } //销毁 void QDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
二叉树:
typedef int BTDataType; //定义二叉树节点 typedef struct BinaryTreeNode { BTDataType data;//存放的数据 struct BinaryTreeNode* leftchild;//指向左孩子的指针 struct BinaryTreeNode* rightchild;//指向右孩子的指针 }BTNode; //前序遍历 void PreOrder(BTNode* root); //中序遍历 void InOrder(BTNode* root); //后序遍历 void PostOrder(BTNode* root); //层序遍历 void LevelOrder(BTNode* root); //二叉树节点个数 int BTSize(BTNode* root); //叶子节点个数 int BTLeafSize(BTNode* root); //第K层节点个数 int BTLevelKSize(BTNode* root, int k); //二叉树高度 int BTDepth(BTNode* root); //查找 BTNode* BTFind(BTNode* root, BTDataType n); //判断是否为完全二叉树 bool BTComplete(BTNode* root); //销毁二叉树 void BTDestroy(BTNode** proot); //创建新节点 BTNode* BTBuyNode(BTDataType n) { BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));//申请一个节点的空间 if (newnode == NULL)//内存申请失败,则直接退出程序 { perror("malloc"); exit(1); } newnode->data = n; newnode->leftchild = newnode->rightchild = NULL; return newnode; } //手动创建二叉树 BTNode* CreateTree() { //创建6个节点 BTNode* n1 = BTBuyNode(1); BTNode* n2 = BTBuyNode(2); BTNode* n3 = BTBuyNode(3); BTNode* n4 = BTBuyNode(4); BTNode* n5 = BTBuyNode(5); BTNode* n6 = BTBuyNode(6); //连接节点 n1->leftchild = n2; n1->rightchild = n3; n2->leftchild = n4; n2->rightchild = n5; n3->rightchild = n6; //返回根节点 return n1; } //前序遍历 void PreOrder(BTNode* root) { if (root == NULL)//访问到空指针就停止遍历 { return; } printf("%d ", root->data);//打印根节点数据 PreOrder(root->leftchild);//遍历左子树 PreOrder(root->rightchild);//遍历右子树 } //中序遍历 void InOrder(BTNode* root) { if (root == NULL)//访问到空指针就停止遍历 { return; } InOrder(root->leftchild);//遍历左子树 printf("%d ", root->data);//打印根节点数据 InOrder(root->rightchild);//遍历右子树 } //后序遍历 void PostOrder(BTNode* root) { if (root == NULL) { return; } PostOrder(root->leftchild);//遍历左子树 PostOrder(root->rightchild);//遍历右子树 printf("%d ", root->data);//打印根节点数据 } //层序遍历 void LevelOrder(BTNode* root) { Queue q;//创建队列 QInit(&q);//初始化队列 QPush(&q, root);//根节点入队 while (!QEmpty(&q))//队列不为空,进入循环 { BTNode* front = QFront(&q);//记录队头数据 printf("%d ", front->data);//读数据 QPop(&q);//出队 if (front->leftchild != NULL) { QPush(&q, front->leftchild);//若左孩子不为空,则左孩子入队 } if (front->rightchild != NULL) { QPush(&q, front->rightchild);//若右孩子不为空,则右孩子入队 } } QDestroy(&q);//销毁队列 } //二叉树节点个数 int BTSize(BTNode* root) { if (root == NULL)//访问到空指针,则结束 { return 0; } return 1 + BTSize(root->leftchild) + BTSize(root->rightchild);//节点有效,返回1,再与左右孩子的判断结果相加 } //叶子节点个数 int BTLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->leftchild == NULL && root->rightchild == NULL)//满足叶子节点的条件,返回1 { return 1; } return BTLeafSize(root->leftchild) + BTLeafSize(root->rightchild);//将左子树和右子树统计结果相加 } //第K层节点个数 int BTLevelKSize(BTNode* root, int k) { if (root == NULL)//访问到空,返回0 { return 0; } if (k == 1)//k值为1,做统计 { return 1; } return BTLevelKSize(root->leftchild, k - 1) + BTLevelKSize(root->rightchild, k - 1);//递归访问左右孩子(下一层) } //二叉树高度 int BTDepth(BTNode* root) { if (root == NULL)//根节点为空则为0层 { return 0; } int leftDepth = BTDepth(root->leftchild);//统计左子树高度 int rightDepth = BTDepth(root->rightchild);//统计右子树高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;//统计左右子树最大高度,再与根节点层数相加 } //查找 BTNode* BTFind(BTNode* root, BTDataType n) { if (root == NULL)//访问到空则停止 { return NULL; } if (root->data == n)//找到了,返回该节点 { return root; } BTNode* leftFind = BTFind(root->leftchild, n);//遍历左子树 if (leftFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回 { return leftFind; } BTNode* rightFind = BTFind(root->rightchild, n);//遍历右子树 if (rightFind != NULL)//若查找结果不是空,则说明找到了,将该节点带回 { return rightFind; } } //判断是否为完全二叉树 bool BTComplete(BTNode* root) { Queue q; QInit(&q);//初始化队列 QPush(&q, root);//根节点入队 while (!QEmpty(&q))//队列不为空进入循环 { BTNode* front = QFront(&q);//记录队头 QPop(&q);//队头出队 if (front == NULL)//当读取到空指针时,跳出循环 { break; } QPush(&q, front->leftchild);//左孩子入队 QPush(&q, front->rightchild);//右孩子入队 } //此时,再次循环读取队头数据,若读取到非空节点,说明不是完全二叉树 while (!QEmpty(&q)) { BTNode* front = QFront(&q);//记录队头 QPop(&q);//队头出队 if (front != NULL) { //出现非空节点 QDestroy(&q);//销毁队列 return false; } } //读完了所有的空指针,还没有遇到非空节点,说明是完全二叉树 QDestroy(&q);//销毁队列 return true; } //销毁二叉树 void BTDestroy(BTNode** proot) { if (*proot == NULL)//访问到空指针则回退 { return; } BTDestroy(&((*proot)->leftchild));//销毁左子树(leftchild是一级指针,函数接收二级指针所以要取地址) BTDestroy(&((*proot)->rightchild));//销毁右子树(rightchild是一级指针,函数接收二级指针所以要取地址) free(*(proot));//销毁根节点 *proot = NULL; }
总结
今天,我们学习了二叉树链式结构相关功能的实现,如遍历、统计节点个数、查找、销毁等。这些功能的实现加深了我们对递归的理解,并且让我们学会了使用数据结构作为辅助来解决问题。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤