当前位置:   article > 正文

二叉树的链式结构的实现_功能1:用链式构造一棵二叉树

功能1:用链式构造一棵二叉树

目录

前言 

一、手动创建一颗树

1、节点的定义

2、按照链接关系建一棵树

二、遍历操作

1、前序遍历

2、中序遍历

3、后续遍历

4、层序遍历

三、二叉树的其他操作

1、求节点个数

2、求叶子节点数

3、求二叉树第k层节点

4、查找二叉树中值为x的节点

5、求二叉树的深度or高度

6、判断一棵树是否是完全二叉树

7、二叉树的销毁 

四、二叉树的OJ题

1、单值二叉树

2、二叉树的前序遍历变型 

3、相同的树

4、对称二叉树

5、另一颗子树

6、通过前序遍历构建二叉树(清华大学)


前言 

 

一、手动创建一颗树

1、节点的定义

既然是链式二叉树必然就少不了每一个节点,这里我们以链式二叉树节点的定义,定义每一个结点,节点结构体内包含:数据域,左指针域和右指针域

  1. typedef int BTDataType;//重命名数据类型,方便以后更改需要储存的数据
  2. typedef struct BinaryTreeNode
  3. {
  4. BTDataType data;
  5. struct BinaryTreeNode* left;//指向左孩子
  6. struct BinaryTreeNode* right;//指向右孩子
  7. }BTNode;

2、按照链接关系建一棵树

随意给出一棵树如下图所示:

  1. //创造一个节点,值给为x,左右孩子置为NULL
  2. BTNode* BuyNode(BTDataType x)
  3. {
  4. BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
  5. if (tmp == NULL)
  6. {
  7. printf("malloc fail\n");
  8. exit(-1);
  9. }
  10. tmp->data = x;
  11. tmp->left = tmp->right = NULL;
  12. }
  13. BTNode* CreatBinaryTree()
  14. {
  15. //数据填入结点
  16. BTNode* node1 = BuyNode(1);
  17. BTNode* node2 = BuyNode(2);
  18. BTNode* node3 = BuyNode(3);
  19. BTNode* node4 = BuyNode(4);
  20. BTNode* node5 = BuyNode(5);
  21. BTNode* node6 = BuyNode(6);
  22. //将结点链接起来
  23. node1->left = node2;
  24. node1->right = node4;
  25. node2->left = node3;
  26. node4->left = node5;
  27. node4->right = node6;
  28. return node1;
  29. }

二、遍历操作

链式二叉树我们采用递推来定义的学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二树中的节点进行相应的操作,并且每个节点只操作一次。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

根据访问顺序的不同,遍历分为以下几种顺序:

①前序遍历:根->左子树->右子树

②中序遍历:左子树->根->右子树

③后续遍历:左子树->右子树->根

④层序遍历:从根节点开始,从上到下,从左到右依次遍历

1、前序遍历

访问根节点的操作发生在遍历其左右子树之前

动图演示

代码演示

  1. //前序遍历
  2. void PreOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return;
  6. printf("%d ", root->data);
  7. PreOrder(root->left);
  8. PreOrder(root->right);
  9. }

遍历结果:我们可以推出,跟随小白人的轨迹,从根节点开始,依次循环一周回到起点

得到:A B D H I E J C F K G

2、中序遍历

访问根节点的操作发生在遍历其左右子树之中

动图演示:

代码演示

  1. //中序遍历
  2. void InOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return;
  6. InOrder(root->left);
  7. printf("%d ", root->data);
  8. InOrder(root->right);
  9. }

遍历结果:我们可以推出二级结论,最后结果每个根节点的垂直落到地上最后一层,然后从左往右输出即可

得到:H D I B E J A F K C G

3、后续遍历

访问根节点的操作发生在遍历其左右子树之后

动图演示

 代码演示

  1. //后序遍历
  2. void PostOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return;
  6. PostOrder(root->left);
  7. PostOrder(root->right);
  8. printf("%d ", root->data);
  9. }

遍历结果:我们同样可以推出二级结论:将所有的结点看做葡萄一样,然后遍历就像在剪葡萄一样,从下往上,从左往右,必须先把左子树上的葡萄剪完后,才能剪右子树上的葡萄

得到:H I D J E B K F G C A

4、层序遍历

层序遍历就是从根节点开始,从上往下,从左往右,一层一层的遍历即可

 

 代码如下:

  1. //层序遍历 队列的类型是二叉树节点的指针
  2. void BinaryTreeLevelOrder(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return;
  6. Queue q;
  7. QueueInit(&q);
  8. QueuePush(&q,root);
  9. while (!QueueEmpty(&q))
  10. {
  11. BTNode* front = QueueFront(&q);
  12. QueuePop(&q);
  13. printf("%d ",front->data);
  14. //带孩子进入队列
  15. if (front->left)
  16. {
  17. QueuePush(&q,front->left);
  18. }
  19. if (front->right)
  20. {
  21. QueuePush(&q, front->right);
  22. }
  23. }
  24. printf("\n");
  25. QueueDestroy(&q);
  26. }

层序遍历结果:1  2    4     3   5   6 

这里我们是用队列实现的层序遍历,借助队列先进先出的性质,当前层数据出队列的时候带入下一层数据。

思路:1、先入根

           2、当前节点出队列,把当前节点的左右孩子带入队列,遇到孩子为空(NULL)不管

           3、当对列为空时,遍历结束

注意:队列中要存放该节点的指针(而不是值),才能带入下一层节点

三、二叉树的其他操作

1、求节点个数

由于链式二叉树是递归定义的,我们可以采用分治的思想:

①若为空,则结点总个数为0

②若不为空,则总结点数=左子树结点数+右子树结点数+1(自己) 

代码如下

  1. //二叉树的节点个数
  2. int BinaryTreeSize(BTNode* root)
  3. {
  4. return root == NULL ? 0 :
  5. BinaryTreeSize(root->left)
  6. + BinaryTreeSize(root->right) + 1;//左+右+自己(+1)
  7. }

2、求叶子节点数

也是采用分治思想

①如果根为空,直接返回

②如果左右孩子都为空,意味着只有自己一个节点,返回1

③总叶子节点数=左子树叶子节点数+右子树叶子节点数

  1. /二叉树的叶子节点数
  2. int BinaryTreeLeafSize(BTNode* root)
  3. {
  4. if (root == NULL)//空树无叶子结点
  5. return 0;
  6. if (root->left == NULL && root->right == NULL)//是叶子结点
  7. return 1;
  8. //叶子结点的个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数
  9. return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  10. }

3、求二叉树第k层节点

利用分治思想

思路:
相对于根结点的第k层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。

  1. //二叉树第k层节点数
  2. int BinaryTreeKLevelSize(BTNode* root, int k)
  3. {
  4. if (k < 1 || root == NULL)//空树或输入k值不合法
  5. return 0;
  6. if (k == 1)//第一层结点个数
  7. return 1;
  8. //相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和
  9. return BinaryTreeKLevelSize(root->left, k - 1) + BinaryTreeKLevelSize(root->right, k - 1);
  10. }

4、查找二叉树中值为x的节点

思路:

①先判断根结点是否是目标结点。
②再去左子树中寻找。
③最后去右子树中寻找。

  1. //二叉树中查找值为k的节点
  2. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
  3. {
  4. if (root == NULL)//空树
  5. return NULL;
  6. if (root->data == x)//先判断根结点
  7. return root;
  8. BTNode* leftret = BinaryTreeFind(root->left, x);//在左子树中找
  9. if (leftret)
  10. return leftret;
  11. BTNode* rightret = BinaryTreeFind(root->right, x);//在右子树中找
  12. if (rightret)
  13. return rightret;
  14. return NULL;//根结点和左右子树中均没有找到
  15. }

5、求二叉树的深度or高度

思路:

1.若为空树,则深度为0。
2.若不为空,则树的最大深度 = 左右子树中深度较大的树的高度 + 1。

采用分治思想

  1. // 二叉树深度/高度
  2. int BinaryTreeDepth(BTNode* root)
  3. {
  4. if (root == NULL)
  5. {
  6. return 0;
  7. }
  8. //return BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ? BinaryTreeDepth(root->left) + 1 : BinaryTreeDepth(root->right) + 1;
  9. int leftDepth = BinaryTreeDepth(root->left);
  10. int rightDepth = BinaryTreeDepth(root->right);
  11. return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
  12. }

6、判断一棵树是否是完全二叉树

这里和二叉树的层序遍历很像,但是有着些不同点: 

代码如下:

  1. //判断二叉树是否是完全二叉树
  2. bool isCompleteTree(BTNode* root)
  3. {
  4. Queue q;
  5. QueueInit(&q);//初始化队列
  6. if (root != NULL)
  7. QueuePush(&q, root);
  8. while (!QueueEmpty(&q))//当队列不为空时,循环继续
  9. {
  10. BTNode* front = QueueFront(&q);//读取队头元素
  11. QueuePop(&q);//删除队头元素
  12. if (front == NULL)//当读取到空指针时,停止入队操作
  13. break;
  14. QueuePush(&q, front->left);//出队元素的左孩子入队列
  15. QueuePush(&q, front->right);//出队元素的右孩子入队列
  16. }
  17. while (!QueueEmpty(&q))//读取队列中剩余的数据
  18. {
  19. BTNode* front = QueueFront(&q);
  20. QueuePop(&q);
  21. if (front != NULL)//若队列中存在非空指针,则不是完全二叉树
  22. {
  23. QueueDestroy(&q);//销毁队列
  24. return false;
  25. }
  26. }
  27. QueueDestroy(&q);//销毁队列
  28. return true;//若队列中全是空指针,则是完全二叉树
  29. }

7、二叉树的销毁 

二叉树销毁时,也是一边遍历,一边销毁,但是二叉树销毁的顺序有一点不同,是采用后续遍历销毁的,就是:左子树->右子树->根,最后来销毁根。

  1. //二叉树的销毁
  2. void BinaryTreeDestroy(BTNode* root)
  3. {
  4. if (root == NULL)
  5. return;
  6. BinaryTreeDestroy(root->left);
  7. BinaryTreeDestroy(root->right);
  8. free(root);
  9. }

四、二叉树的OJ题

1、单值二叉树

解题思想:单值二叉树要树的每个节点的值都要相同

同样采用分治思想:①根的左孩子和根的值比较

                                 ②根的右孩子和根的值比较

                                 ③分别以左右孩子再为根,再比较

                                 ④空树也是单值二叉树

代码如下:

  1. bool isUnivalTree(struct TreeNode* root)
  2. {
  3. if(root==NULL)
  4. return true;
  5. if(root->left&&root->left->val!=root->val)
  6. return false;
  7. if(root->right&&root->right->val!=root->val)
  8. return false;
  9. return isUnivalTree(root->left)&&isUnivalTree(root->right);
  10. }

2、二叉树的前序遍历变型 

3、相同的树

 解题思想:判断两棵树相同要树形相同而且节点的值要相同

同样采用分治思想:从根开始分为4种情况

①两树根都是为空

②两树中有一个为空

③都不为空

④根相同了,再分别比较左右子树的值

  1. bool isSameTree(struct TreeNode* p, struct TreeNode* q)
  2. {
  3. //根都为空
  4. if(p==NULL&&q==NULL)
  5. return true;
  6. //根有一个为空
  7. if(p==NULL||q==NULL)
  8. {
  9. return false;
  10. }
  11. //根都不为空,就比较值
  12. if(p->val!=q->val)
  13. return false;
  14. //最后分别比较左右子树的值
  15. return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
  16. }

4、对称二叉树

解题思想:从根开始垂直作一条垂线(轴对称),让左右子树都相同(树形和值相同)

代码如下:

  1. bool _isSymmetricTree(struct TreeNode* root1,struct TreeNode* root2)
  2. {
  3. if(root1==NULL&&root2==NULL)
  4. return true;
  5. if(root1==NULL||root2==NULL)
  6. return false;
  7. if(root1->val!=root2->val)
  8. return false;
  9. return _isSymmetricTree(root1->left,root2->right)
  10. &&_isSymmetricTree(root1->right,root2->left);
  11. }
  12. bool isSymmetric(struct TreeNode* root)
  13. {
  14. if(root==NULL)
  15. return true;
  16. return _isSymmetricTree(root->left,root->right);
  17. }

5、另一颗子树

解题思想:用root的每一个子树都和subRoot比较一下

 

代码如下:

  1. bool isSameTree(struct TreeNode* p, struct TreeNode* q)
  2. {
  3. //根都为空
  4. if(p==NULL&&q==NULL)
  5. return true;
  6. //根有一个为空
  7. if(p==NULL||q==NULL)
  8. {
  9. return false;
  10. }
  11. //根都不为空,就比较值
  12. if(p->val!=q->val)
  13. return false;
  14. //最后分别比较左右子树的值
  15. return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
  16. }
  17. bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
  18. {
  19. if(root==NULL)
  20. return false;
  21. if(isSameTree(root,subRoot))
  22. return true;
  23. return isSubtree(root->left,subRoot)
  24. ||isSubtree(root->right,subRoot);
  25. }

6、通过前序遍历构建二叉树(清华大学)

题目描述:

 我们先前序遍历把这棵树给建出来:

解题思想:

①若该字符不是#,则我们先构建该值的结点,然后递归构建其左子树和右子树。
②若该字符是#,则说明该位置之下不能再构建结点了,返回即可。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef struct TreeNode
  4. {
  5. struct TreeNode* left;
  6. struct TreeNode* right;
  7. char data;
  8. }TreeNode;
  9. //创建树
  10. TreeNode* CreateTree(char* str, int* pi)
  11. {
  12. if(str[*pi] == '#')//
  13. {
  14. (*pi)++;
  15. return NULL;
  16. }
  17. //不是NULL,构建结点
  18. TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  19. root->left = NULL;
  20. root->right = NULL;
  21. root->data = str[*pi];
  22. (*pi)++;
  23. //递归构建左子树
  24. root->left = CreateTree(str, pi);
  25. //递归构建右子树
  26. root->right = CreateTree(str, pi);
  27. return root;
  28. }
  29. //中序遍历
  30. void Inorder(TreeNode* root)
  31. {
  32. if(root == NULL)
  33. return;
  34. Inorder(root->left);
  35. printf("%c ", root->data);
  36. Inorder(root->right);
  37. }
  38. int main()
  39. {
  40. char str[100];
  41. scanf("%s", str);
  42. int i = 0;
  43. TreeNode* root = CreateTree(str, &i);
  44. Inorder(root);
  45. return 0;
  46. }

PS:本篇博客中的前序,中序,后续遍历的动图借鉴了一下这位博主的精品文章

数据结构——二叉树先序、中序、后序及层次四种遍历(C语言版)_正弦定理的博客-CSDN博客_二叉树的先序,中序,后序遍历c语言数据结构——二叉树先序、中序、后序三种遍历二叉树先序、中序、后序三种遍历三、代码展示:二叉树先序、中序、后序三种遍历先序遍历:3 2 2 3 8 6 5 4中序遍历:2 2 3 3 4 5 6 8后序遍历: 2 3 2 4 5 6 8 3三种遍历不同之处在,输出数据放在不同之处三、代码展示:#include<stdio.h>#include<stdlib.h>typedef struct Tree{ inthttps://blog.csdn.net/chinesekobe/article/details/110874773 谢谢大家!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/233045
推荐阅读
相关标签
  

闽ICP备14008679号