当前位置： 首页 > news >正文

生活做爰网站网络推广是以企业产品或服务

news 2025/8/13 9:19:12
生活做爰网站,网络推广是以企业产品或服务,龙岩优化seo排名,wordpress更新服务评论文章目录 1. 二叉树的链式结构2. 二叉树的创建和实现相关功能2.1 创建二叉树2.2 二叉树的前，中，后序遍历2.2.1 前序遍历2.2.2 中序遍历2.2.3 后序遍历 2.3 二叉树节点个数2.4 二叉树叶子结点个数2.5 二叉树第k层结点个数2.6 二叉树的深度/高度2.7 二叉树…

文章目录

  • 1. 二叉树的链式结构
  • 2. 二叉树的创建和实现相关功能
    • 2.1 创建二叉树
    • 2.2 二叉树的前，中，后序遍历
      • 2.2.1 前序遍历
      • 2.2.2 中序遍历
      • 2.2.3 后序遍历
    • 2.3 二叉树节点个数
    • 2.4 二叉树叶子结点个数
    • 2.5 二叉树第k层结点个数
    • 2.6 二叉树的深度/高度
    • 2.7 二叉树查找值为x的结点
    • 2.8 层序遍历
    • 2.9 判断二叉树是否为完全二叉树
    • 2.10 二叉树的销毁
  • 3. 源代码

1. 二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成：数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，三叉链在结构上比二叉链多了一个指向父节点的指针域。

请添加图片描述
在这里先使用二叉链来实现二叉树

2. 二叉树的创建和实现相关功能

2.1 创建二叉树

用链表来实现二叉树，每个链表结点都由一个数据域和左右指针域组成

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;

接下来我们来实现创建节点的函数：

首先使用malloc函数创建一个节点大小的空间，如果创建失败就打印错误信息，创建成功则把数据存储在新节点的数据域中，再将新节点的左右孩子指针指向空，最后返回新节点即可

//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

下面我们来创建一棵如图所示的二叉树
在这里插入图片描述

BTNode* CreateTree()
{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 = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}

2.2 二叉树的前，中，后序遍历

下面来简单介绍一下前，中，后序遍历的规则
在这里插入图片描述
请添加图片描述
下面来根据上面所示的二叉树进行前，中，后序遍历

2.2.1 前序遍历

前序遍历就是先打印根节点的值，再遍历根节点的左子树，最后遍历根节点的右子树，也就是根左右

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

根据以上代码：进入函数先打印根节点存储的值，再递归左子树，左子树递归完后再递归右子树。不要忘了，如果遇到空节点记得要返回。

前序遍历的步骤：

  1. 打印根节点的值为1
  2. 递归左子树，创建根节点左孩子节点2的函数栈帧
  3. 打印节点2的值为2，创建节点2的左孩子节点4的函数栈帧
  4. 打印节点4的值为4，创建节点4的左孩子节点的函数栈帧
  5. 节点4的左孩子节点为空，返回节点4的函数栈帧
  6. 创建节点4的右孩子节点的函数栈帧
  7. 节点4的右孩子节点为空，返回节点4的函数栈帧
  8. 节点4的函数栈帧被销毁，返回节点2的函数栈帧
  9. 创建节点2的右孩子节点5的函数栈帧
  10. 打印节点5的值为5，创建节点5的左孩子节点的函数栈帧
  11. 节点5的左孩子节点为空，返回节点5的函数栈帧
  12. 创建节点5的右孩子节点的函数栈帧
  13. 节点5的右孩子节点为空，返回节点5的函数栈帧
  14. 节点5的函数栈帧被销毁，返回节点2的函数栈帧
  15. 节点2的函数栈帧被销毁，返回根节点的函数栈帧
  16. 创建根节点的右孩子节点3的函数栈帧
  17. 打印节点3的值为3，创建节点3的左孩子节点6的函数栈帧
  18. 打印节点6的值为6，创建节点6的左孩子节点的函数栈帧
  19. 节点6的左孩子节点为空，返回节点6的函数栈帧
  20. 创建节点6的右孩子节点的函数栈帧
  21. 节点6的右孩子节点为空，返回节点6的函数栈帧
  22. 节点6的函数栈帧被销毁，返回节点3的函数栈帧
  23. 创建节点3的右孩子节点的函数栈帧
  24. 节点3的右孩子节点为空，返回节点3的函数栈帧
  25. 节点3的函数栈帧被销毁，返回根节点的函数栈帧
  26. 根节点的函数栈帧被销毁

所以前序遍历的结果为：1 2 4 5 3 6

中序遍历和后序遍历与前序遍历的思路一样，只是打印节点的值和递归左右子树的顺序不同而已

2.2.2 中序遍历

思路：先遍历根节点的左子树，再打印根节点的值，最后遍历根节点的右子树，也就是左根右

中序遍历的结果：4 2 5 1 6 3

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

2.2.3 后序遍历

思路：先遍历根节点的左子树，再遍历根节点的右子树，最后打印根节点的值，也就是左右根

后序遍历的结果：4 5 2 6 3 1

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

2.3 二叉树节点个数

思路：先递归根节点的左子树，再递归根节点的右子树，如果递归到空节点就返回0，最后返回左子树节点个数和右子树节点个数的和再加一

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.4 二叉树叶子结点个数

思路：第一种情况：如果递归到的当前节点为空就返回0，第二种情况：如果节点的左右子树为空时说明该节点为叶子节点则返回1，第三种情况：如果递归到的节点既不是空又不是叶子节点，则继续递归该节点的左右子树，即返回该节点左右子树的叶子节点 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right)

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.5 二叉树第k层结点个数

思路：因为根节点是第一层，所以每次向下遍历时将k减一，当k=1时当前节点就是在第k层，返回1即可，所以只需一直递归节点的左右子树，每次递归节点的左右子树时还要让k减一。当递归到的节点为空时，只需返回0即可，要先判断节点为不为空，如果不为空再判断当前节点是不是在第k层。

//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

2.6 二叉树的深度/高度

思路：因为二叉树的左右子树的高度可能不一样，所以要分开递归二叉树的左右子树，然后再取最大值即可。当递归到空节点时返回0，否则继续递归当前节点的左右子树，最后返回左右子树深度的最大值再加一(因为当前的根节点也是一层)

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

2.7 二叉树查找值为x的结点

思路：先遍历根节点的左子树，如果找到了值为x的节点就返回该节点的地址，右子树也无需再遍历了，如果没有找到再遍历右子树，如果找到了就返回该节点的地址，没有找到则返回空。再遍历的过程中，先判断节点是否为空，如果为空就返回空，不为空的话再判断该节点的值是不是x，如果是就返回该节点的地址，如果不是就继续遍历该节点的左右子树。

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}BTNode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL;
}

2.8 层序遍历

这里需要借助队列，不熟悉的可以看一下数据结构—队列

层序遍历是指从根节点开始一层一层遍历二叉树，从上至下，从左至右，依次访问节点，如下图，该二叉树的层序遍历结果为：1 2 3 4 5 6

请添加图片描述
使用队列这个数据结构来实现层序遍历，队列的特点是先进先出。首先将根节点放入队列中，再将根节点出队，最后将根节点的左右孩子节点入队。将根节点的左孩子2出队，然后将根节点的左孩子2的左右孩子节点入队，以此类推……一直到队列为空

在这里插入图片描述

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

2.9 判断二叉树是否为完全二叉树

思路：同样还是借助队列这个数据结构，与层序遍历不同的是，当节点的左右孩子节点为空时也要进行入队操作，当队头为空时，就退出循环，然后还需要判断队列里有没有不为空的节点，如果有说明二叉树不为完全二叉树，如果没有说明二叉树为完全二叉树

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

2.10 二叉树的销毁

思路：因为要销毁整个二叉树包括根节点，所以这里传递的是二级指针去接收一级指针的地址，这样就实现了形参改变实参。先销毁根节点的左子树和右子树，也就是递归到叶子节点开始销毁，然后往上一层一层地进行销毁，最后再销毁根节点。

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

3. 源代码

Tree.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;//创建二叉树新节点
BTNode* buyNode(BTDataType x);
//创建一个二叉树
BTNode* CreateTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c源文件

#include "Tree.h"
#include "Queue.h"
//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}BTNode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL;
}
//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);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){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

test.c源文件

#include "Tree.h"BTNode* CreateTree()
{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 = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}void BinaryTreeTest01()
{BTNode* node1 = CreateTree();PreOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("\n");printf("%d\n", BinaryTreeSize(node1));printf("%d\n", BinaryTreeLeafSize(node1));printf("第%d层结点个数为：%d\n", 3, BinaryTreeLevelKSize(node1, 3));printf("%d\n", BinaryTreeDepth(node1));if (BinaryTreeFind(node1, 10) == NULL){printf("没有找到\n");}else{printf("找到了\n");}LevelOrder(node1);printf("\n");printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");BinaryTreeDestory(&node1);
}
int main()
{BinaryTreeTest01();return 0;
}

对以上内容有不同看法的欢迎来讨论，希望对大家的学习有帮助，多多支持哦！

http://www.mmbaike.com/news/103081.html

相关文章：

  • 帮彩票网站做流量提升网站技术外包公司
  • 可以直接进入的网站正能量大豆网上海最新政策
  • 公司注册资金可以乱写吗重庆百度快照优化
  • 网站设计模版app用户量排名
  • 首商网官网关键词seo排名优化如何
  • axure做的购物网站crm软件
  • 在网上做翻译的网站深圳网站关键词
  • 免费seo关键词优化方案温州seo按天扣费
  • 回收网站怎么做百度收录网站提交入口
  • 找做金融的网站有哪些酒店营销策划与运营
  • 证书查询网湖南seo快速排名
  • 济南高新网站制作山东seo优化
  • 江西省赣州市中考分数线2021整站seo怎么做
  • 网站建设优化工资高不seo中国
  • 长沙房产网签查询系统网店seo是什么意思
  • 企点协同企业seo自助建站系统
  • 织梦网站如何调用其他网站新闻百度知道首页登录
  • 免费网站部署排名优化服务
  • 响应式网站用什么语言站外推广方式
  • 如何建立公司的网站扶贫832网络销售平台
  • 做视频类型的网站二级域名查询网站
  • 如何进入正能量奖励网站网站排名优化工具
  • 做研学的网站关键词大全
  • 厦门专业做网站网络营销的概念和特征
  • 宣城哪里做网站点金推广优化公司
  • 烟台专门做网站的百度站长工具怎么关闭
  • 做网站怎么推广深圳华强北新闻最新消息今天
  • 建网站如何收费推广app是什么工作
  • 做木箱的网站优秀网站
  • 现在做网站公司管理人员需要培训哪些课程