• 售前

  • 售后

热门帖子
入门百科

【学习笔记】二叉树(c语言)

[复制链接]
123457015 显示全部楼层 发表于 2022-1-13 02:00:48 |阅读模式 打印 上一主题 下一主题
1.树

1.1树的性质

树是一种非线性的数据结构,他是由n(n >= 0)个有限结点组成一个具有层次关系的集合。把他叫做树是因为他看起来向一颗倒挂的树,也就是说他是根在上,叶在下的。
1.2树的相关概念

节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I...等节点为叶节点
非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G...等节点为分支节点
双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林;
1.3树的性质

   树有一个特殊的结点叫做根结点,根节点没有前驱结点
  
除根结点外,其余结点被分成M(M>0)个互不相交的集合T1\T2.....\Tm,其中每个集合Ti(1val = x;        newnode->left = NULL;        newnode->right = NULL;}[/code] 3.2.2前序遍历

  1. typedef char BTDataType;
  2. typedef struct BTNode {
  3.         BTDataType val;
  4.         struct BTNode* left;
  5.         struct BTNode* right;
  6. }BTNode;
复制代码
3.2.3中序遍历

  1. BTNode* CreatTreeNode(BTDataType x)                                        //创建二叉树结点
  2. {
  3.         BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  4.         assert(newnode);
  5.         newnode->val = x;
  6.         newnode->left = NULL;
  7.         newnode->right = NULL;
  8. }
复制代码
3.2.4后序遍历

  1. void PrevOrder(BTNode* root)                                                //前序遍历
  2. {
  3.         if (root == NULL)                                //遇到结点为NULL返回
  4.         {
  5.                 printf("NULL ");
  6.                 return;
  7.         }
  8.         printf("%c ", root->val);                //打印根数据
  9.         PrevOrder(root->left);                        //令左孩子为根进行前序遍历
  10.         PrevOrder(root->right);                        //令右孩子为根进行前序遍历
  11. }
复制代码
3.2.5二叉树结点个数

  1. void InOrder(BTNode* root)                                                        //中序遍历
  2. {
  3.         if (root == NULL)                                //遇到结点为NULL返回
  4.         {
  5.                 printf("NULL ");
  6.                 return;
  7.         }
  8.         InOrder(root->left);                        //打印根数据
  9.         printf("%c ", root->val);                //令左孩子为根进行中序遍历
  10.         InOrder(root->right);                        //令右孩子为根进行中序遍历
  11. }
复制代码
3.2.6二叉树叶结点个数

  1. void PostOrder(BTNode* root)                                                //后序遍历
  2. {
  3.         if (root == NULL)                                //遇到结点为NULL返回
  4.         {
  5.                 printf("NULL ");
  6.                 return;
  7.         }
  8.         PostOrder(root->left);                        //令左孩子为根进行后序遍历       
  9.         PostOrder(root->right);                        //令右孩子为根进行后序遍历
  10.         printf("%c ", root->val);                //打印根数据
  11. }
复制代码
3.2.7第k层结点个数

  1. int TreeSize(BTNode* root)                                                        //结点个数
  2. {
  3.         if (root == NULL)
  4.         {
  5.                 return 0;
  6.         }
  7.         return TreeSize(root->left) + TreeSize(root->right) + 1;
  8.         //优化
  9.         //return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
  10. }
复制代码
3.2.8二叉树最大深度

  1. int BinaryTreeLeafSize(BTNode* root)                                //叶结点个数
  2. {
  3.         if (root == NULL)
  4.         {
  5.                 return 0;
  6.         }
  7.         if (root->left == NULL && root->right == NULL)
  8.         {
  9.                 return 1;
  10.         }
  11.        
  12.         return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
  13. }
复制代码
3.2.9二叉树查找

  1. int BinaryTreeLevelKSize(BTNode* root, int k)                //第k层结点个数
  2. {
  3.         if (root == NULL)
  4.         {
  5.                 return 0;
  6.         }
  7.         if (k == 1)
  8.         {
  9.                 return 1;
  10.         }
  11.         return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
  12. }
复制代码
3.3二叉树头文件

文件:“Binary_Tree.h”
  1. int MaxDepth(BTNode* root)                                //二叉树最大深度
  2. {
  3.         if (root == NULL)
  4.         {
  5.                 return 0;
  6.         }
  7.         int leftdepth = MaxDepth(root->left);
  8.         int rightdepth = MaxDepth(root->right);
  9.         return leftdepth > rightdepth ? leftdepth+1 : rightdepth+1;
  10. }
复制代码
3.4二叉树功能测试

文件:“test.c”
  1. BTNode* BinaryTreeFind(BTNode* root, BTDataType x)        //二叉树查找
  2. {
  3.         if (root == NULL)
  4.         {
  5.                 return NULL;
  6.         }
  7.         if (root->val == x)
  8.         {
  9.                 return root;
  10.         }
  11.         BTNode* left = BinaryTreeFind(root->left, x);
  12.         if (left)
  13.         {
  14.                 return left;
  15.         }
  16.         BTNode* right = BinaryTreeFind(root->right, x);
  17.         if (right)
  18.         {
  19.                 return right;
  20.         }
  21.         return NULL;
  22. }
复制代码

写在最后
笔记时间:2022_01_11


来源:https://blog.caogenba.net/Zero__two_/article/details/122432444
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作