数据结构上机实验——二叉树的实现、二叉树遍历、求二叉树的深度/节点数目/叶节点数目、计算二叉树度为1或2的节点数、判断二叉树是否相似

2023-10-29 17:36
文章标签 二叉树 遍历 实现 计算 数据结构 深度 判断 是否 实验 节点 上机 数目 相似 度为

本文主要是介绍数据结构上机实验——二叉树的实现、二叉树遍历、求二叉树的深度/节点数目/叶节点数目、计算二叉树度为1或2的节点数、判断二叉树是否相似，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 数据结构上机实验
    • 1.要求
    • 2.二叉树的实现
      • 2.1创建一颗二叉树
      • 2.2对这棵二叉树进行遍历
      • 2.3求二叉树的深度/节点数目/叶节点数目
      • 2.4计算二叉树中度为 1 或 2 的结点数
      • 2.5判断2棵二叉树是否相似，若相似返回1，否则返回0
    • 3.全部源码
      • 测试：
      • BinaryTree.h
      • test.cpp

数据结构上机实验

1.要求

   建立一棵二叉树，试编程实现二叉树的如下基本操作。
   1.创建一棵一棵二叉算法。
   2.对这棵二叉树进行遍历：先序或中序或后序，分别输出结点的遍历序列。
   3.求二叉树的深度/节点数目/叶节点数目。（选做一个）
   4.计算二叉树中度为1 的结点数；
   5.计算二叉树中度为2 的结点数。
   6.判断2棵二叉树是否相似，若相似返回1，否则返回0

            

2.二叉树的实现

  二叉树的介绍
在这里插入图片描述
  

2.1创建一颗二叉树

  我们现在可以简单实现一个二叉树的结构，其中包括一个二叉树节点（BNode）和一个二叉树（BTree）类。

  我们定义了一个名为BNode的结构体，它代表二叉树的节点。每个节点包含一个数据元素（data，其类型为int）和两个指向其左右子节点的指针（left和right）。

  然后定义了一个名为BTree的类，它包含一个私有成员变量_root，这是一个指向BNode的指针。这个指针表示了树的根节点。这个类还包含一个默认的构造函数，该构造函数将_root初始化为nullptr，即没有初始的根节点。

#define BTDataType int//定义二叉树节点
typedef struct BTreeNode
{BTDataType data;struct BTreeNode* left;struct BTreeNode* right;
}BNode;//定义二叉树
class BTree
{
public://构造函数BTree(){_root = nullptr;}private:BNode* _root;
};

  
输入字符递归创建二叉树：
  我们先使用引用接受一个 BNode*类型的参数 root。这样我们就可以在函数内部，直接对 root 进行操作，最后返回给tmp，再赋给_root。

  这个函数首先从标准输入读取一个字符 val。如果 val 是 . ，则 root 被设置为 nullptr，表示该节点为空。如果 val 不是 .，则创建一个新的 BNode 对象，其 data 成员的值为 val 减去字符 ‘0’ 的 ASCII 值（这样可以获得一个整数），然后递归地创建这个新节点的左子树和右子树。最后，_BTCreate 返回，控制权回到调用该函数的代码。

//递归创建二叉树
void _BTCreate(BNode*& root)
{char val;cin >> val;if (val == '.') root = nullptr;else{root = new BNode(val - '0');_BTCreate(root->left);_BTCreate(root->right);}
}//递归创建二叉树
void BTCreate()
{BNode* tmp;_BTCreate(tmp);_root = tmp;
}

  

2.2对这棵二叉树进行遍历

在这里插入图片描述

前序遍历：

  我们创建_PreOrder(BNode* root)这个函数是用来前序遍历。它的顺序是：先访问根节点，然后访问左子树，最后访问右子树。

  如果 root 是 nullptr（即当前节点为空），它将输出 “NULL” 并返回。如果 root 非空，它会输出当前节点的数据（root->data），然后递归地对左子树和右子树进行前序遍历。

  由于二叉树的前序遍历是一个递归算法，为了可以将根节点不断的更新，并且递归。 我们需要封装一下，对于后面需要递归的函数，我们都需要将根节点作为参数，进行递归操作。

//前序遍历
void _PreOrder(BNode* root)
{if (root == nullptr){cout << "NULL" << " ";return;}cout << root->data << " ";_PreOrder(root->left);_PreOrder(root->right);
}//前序遍历
void PreOrder()
{_PreOrder(_root);cout << endl;
}

  
中序遍历：

  我们创建 _InOrder(BNode* root) 来进行中序遍历，它的顺序是：先访问左子树，然后访问根节点，最后访问右子树。

  如果 root 是 nullptr，表示当前节点为空，输出 “NULL” 并返回。如果 root 非空，先递归地遍历左子树，然后输出当前节点的数据 root->data，最后递归地遍历右子树。

//中序遍历
void _InOrder(BNode* root)
{if (root == nullptr){cout << "NULL" << " ";return;}_InOrder(root->left);cout << root->data << " ";_InOrder(root->right);
}//中序遍历
void InOrder()
{_InOrder(_root);cout << endl;
}

  
后序遍历：

  我们创建 _PostOrder(BNode* root) 函数来进行进行后序遍历，它的顺序是：先访问左子树，然后访问右子树，最后访问根节点。

  如果 root 是 nullptr，表示当前节点为空，输出 “NULL” 并返回。如果 root 非空，先递归地遍历左子树，然后递归地遍历右子树，最后输出当前节点的数据 root->data。

//后序遍历
void _PostOrder(BNode* root)
{if (root == nullptr){cout << "NULL" << " ";return;}_PostOrder(root->left);_PostOrder(root->right);cout << root->data << " ";
}//后序遍历
void PostOrder()
{_PostOrder(_root);cout<<endl;
}

  

2.3求二叉树的深度/节点数目/叶节点数目

计算二叉树深度：

  我们使用递归的方式来实现计算二叉树的深度。二叉树的深度可以定义为左子树和右子树深度的最大值加1。

  函数接受的参数root 是 NULL，即当前节点为空，那么返回深度为0。否则，递归地计算左子树和右子树的深度，并返回其中较大的一个，并加上1（当前节点的深度）。

//计算二叉树深度
int _BTDepth(BNode* root)
{if (root == NULL){return 0;}else{int left_Height = _BTDepth(root->left) + 1;int right_Height = _BTDepth(root->right) + 1;if (left_Height >= right_Height) return left_Height;else return right_Height;}
}//计算二叉树深度
int	BTDepth()
{return _BTDepth(_root);
}

  
计算二叉树节点数目：

  我们递归实现_Num_Of_TreeNode来计算二叉树的节点数目。

  首先我们接收一个指向二叉树节点的指针 root 作为参数。如果 root 是 NULL（也就是说，当前节点不存在），函数返回0。否则，则说明该二叉树的节点存在，函数返回1（对于当前节点） 加上左子树和右子树的节点数目。这是通过递归调用 _Num_Of_TreeNode 函数得到的。

//计算二叉树节点数目
int _Num_Of_TreeNode(BNode* root)
{if (root == NULL){return 0;}else{return 1 + _Num_Of_TreeNode(root->left) + _Num_Of_TreeNode(root->right);}
}//计算二叉树节点数目
int Num_Of_TreeNode()
{return _Num_Of_TreeNode(_root);
}

  
计算二叉树叶子节点的数目:

  我们同样创建递归函数 _Num_Of_LeafNode来计算二叉树的叶子节点。

  我们接收一个指向二叉树节点的指针 root 作为参数。如果 root 是 NULL（也就是说，当前节点不存在），函数返回0。否则，函数首先递归地计算左子树和右子树的叶子节点数量，分别存储在 left_Num 和 right_Num 中。

  注意：如果 left_Num 和 right_Num 的和为0，这意味着当前节点是叶子节点，因此返回1。 如果 left_Num 和 right_Num 的和不为0，这意味着当前节点不是叶子节点，因此返回 left_Num 和 right_Num 的和。

//计算二叉树叶子节点的数目
int _Num_Of_LeafNode(BNode* root)
{if (root == NULL){return 0;}else{int left_Num = _Num_Of_LeafNode(root->left);int right_Num = _Num_Of_LeafNode(root->right);if (left_Num + right_Num == 0){return 1;}else{return left_Num + right_Num;}}
}//计算二叉树叶子节点的数目
int Num_Of_LeafNode()
{return _Num_Of_LeafNode(_root);
}

  

2.4计算二叉树中度为 1 或 2 的结点数

  
计算度为1的节点个数：

  二叉树的递归函数大差不差，我们对于求不同的节点，只要加以它们的性质判断即可。

  如果二叉树的节点度为2，说明它们均有左右节点。 所以，此时函数返回的是左子树和右子树中1度节点的总和。

  只有右节点: 如果一个节点只有右子节点，那么它是1度节点。 因此，这个分支计算了右子树中的1度节点数量，并加上1（表示当前节点）。

  只有左节点: 与上述逻辑类似，如果一个节点只有左子节点， 那么它也是1度节点。这个分支计算了左子树中的1度节点数量，并加上1（表示当前节点）。

  无左右节点: 如果一个节点既没有左子节点也没有右子节点，那么它不是1度节点。函数返回0。

//计算度为1的节点个数
int _Num_Of_Degree_1(BNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right != NULL || root->left != NULL && root->right == NULL){return 1 + _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);}return  _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);
}//计算二叉树节点数目
int Num_Of_TreeNode()
{return _Num_Of_TreeNode(_root);
}

  
计算度为2的节点个数：

  和上面一样，我们实现计算一个二叉树中度为2的节点的数量。度为2的节点是指有两个子节点的节点。

  如果 root 的左右子节点都不为空(root->left != NULL and root->right != NULL)，则说明当前节点的度为2，返回1（对于当前节点）加上左子树和右子树的度为1的节点数量之和。

  只有右子节点不为空，则只返回右子树的度为1的节点数量。

  只有左子节点不为空，则只返回左子树的度为1的节点数量。

  左右子节点都为空，则当前节点不是度为2的节点，返回0。

//计算度为2的节点个数
int _Num_Of_Degree_2(BNode* root)
{if (root == NULL){return 0;}else if(root->left != NULL && root->right != NULL)//均有左右节点{return 1 + _Num_Of_Degree_2(root->left) + _Num_Of_Degree_2(root->right);}return _Num_Of_Degree_2(root->right)+ _Num_Of_Degree_2(root->left);
}//计算度为2的节点个数
int Num_Of_Degree_2()
{return _Num_Of_Degree_2(_root);
}

  

2.5判断2棵二叉树是否相似，若相似返回1，否则返回0

  这个函数是用来判断两棵二叉树是否相似的。相似二叉树的定义是：如果两棵二叉树的结构相同，即它们的左子树和右子树都是相似的，那么这两棵二叉树就是相似的。

  这个函数使用递归的方式进行检查。首先，如果两个节点都为空，那么它们显然是相似的。然后，如果两个节点都不为空，并且它们的左子树和右子树都是相似的，那么这两个节点也是相似的。 最后，如果以上条件都不满足，那么这两个节点就不相似。

//判断二叉树是否相似
int Is_Similar(BNode* t1, BNode* t2)
{if (t1 == NULL && t2 == NULL){return 1;}else if (t1 && t2 && Is_Similar(t1->left, t2->left)&& Is_Similar(t1->right, t2->right)){return 1;}else{return 0;}
}

            

3.全部源码

测试：

在这里插入图片描述
在这里插入图片描述
  

在这里插入图片描述
在这里插入图片描述

BinaryTree.h

#pragma once#define BTDataType int//定义二叉树节点
typedef struct BTreeNode
{BTDataType data;struct BTreeNode* left;struct BTreeNode* right;BTreeNode() {data = -1;left = nullptr;right = nullptr;}BTreeNode(const int& _data){data = _data;left = nullptr;right = nullptr;}
}BNode;//定义二叉树
class BTree
{
public://构造函数BTree(){_root = nullptr;}//析构函数~BTree(){DestroyTree(_root);}//递归创建二叉树void BTCreate(){BNode* tmp;_BTCreate(tmp);_root = tmp;}//前序遍历void PreOrder(){_PreOrder(_root);cout << endl;}//中序遍历void InOrder(){_InOrder(_root);cout << endl;}//后序遍历void PostOrder(){_PostOrder(_root);cout<<endl;}//计算二叉树深度int	BTDepth(){return _BTDepth(_root);}//计算二叉树节点数目int Num_Of_TreeNode(){return _Num_Of_TreeNode(_root);}//计算二叉树叶子节点的数目int Num_Of_LeafNode(){return _Num_Of_LeafNode(_root);}//计算度为1的节点个数int Num_Of_Degree_1(){return _Num_Of_Degree_1(_root);}//计算度为2的节点个数int Num_Of_Degree_2(){return _Num_Of_Degree_2(_root);}//判断二叉树是否相似int Is_Similar(BNode* t1, BNode* t2){if (t1 == NULL && t2 == NULL){return 1;}else if (t1 && t2 && Is_Similar(t1->left, t2->left) && Is_Similar(t1->right, t2->right)){return 1;}else{return 0;}}//取根节点BNode*& GetRoot(){return _root;}private://递归创建二叉树void _BTCreate(BNode*& root){char val;cin >> val;if (val == '.') root = nullptr;else{root = new BNode(val - '0');_BTCreate(root->left);_BTCreate(root->right);}}//前序遍历void _PreOrder(BNode* root){if (root == nullptr){cout << "NULL" << " ";return;}cout << root->data << " ";_PreOrder(root->left);_PreOrder(root->right);}//中序遍历void _InOrder(BNode* root){if (root == nullptr){cout << "NULL" << " ";return;}_InOrder(root->left);cout << root->data << " ";_InOrder(root->right);}//后序遍历void _PostOrder(BNode* root){if (root == nullptr){cout << "NULL" << " ";return;}_PostOrder(root->left);_PostOrder(root->right);cout << root->data << " ";}//计算二叉树深度int _BTDepth(BNode* root){if (root == NULL){return 0;}else{int left_Height = _BTDepth(root->left) + 1;int right_Height = _BTDepth(root->right) + 1;if (left_Height >= right_Height) return left_Height;else return right_Height;}}//计算二叉树节点数目int _Num_Of_TreeNode(BNode* root){if (root == NULL){return 0;}else{return 1 + _Num_Of_TreeNode(root->left) + _Num_Of_TreeNode(root->right);}}//计算二叉树叶子节点的数目int _Num_Of_LeafNode(BNode* root){if (root == NULL){return 0;}else{int left_Num = _Num_Of_LeafNode(root->left);int right_Num = _Num_Of_LeafNode(root->right);if (left_Num + right_Num == 0){return 1;}else{return left_Num + right_Num;}}}//计算度为1的节点个数int _Num_Of_Degree_1(BNode* root){if (root == NULL){return 0;}if (root->left == NULL && root->right != NULL || root->left != NULL && root->right == NULL){return 1 + _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);}return  _Num_Of_Degree_1(root->left) + _Num_Of_Degree_1(root->right);}//计算度为2的节点个数int _Num_Of_Degree_2(BNode* root){if (root == NULL){return 0;}else if(root->left != NULL && root->right != NULL)//均有左右节点{return 1 + _Num_Of_Degree_2(root->left) + _Num_Of_Degree_2(root->right);}return  _Num_Of_Degree_2(root->left) + _Num_Of_Degree_2(root->right);}//销毁二叉树void DestroyTree(BNode*& root) {if (root == NULL) {return;}BNode* lroot = root->left;BNode* rroot = root->right;delete root;if (lroot != NULL){DestroyTree(lroot);}if (rroot != NULL){DestroyTree(rroot);}}private:BNode* _root;
};

            

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
using namespace std;#include"BinaryTree.h" void binary_Test()
{BTree bt1;BTree bt2;cout << "输入第一棵树的前序遍历（空树请用 . 代替）:";bt1.BTCreate();cout << "输入第二棵树的前序遍历（空树请用 . 代替）:";bt2.BTCreate(); cout << "第一棵树的前序遍历为:";bt1.PreOrder();cout << "第一棵树的中序遍历为:"; bt1.InOrder();	cout << "第一棵树的后序遍历为:"; bt1.PostOrder();cout << "第一棵树的深度为:" << bt1.BTDepth() << endl;cout << "第一棵树中的节点数:" << bt1.Num_Of_TreeNode() << endl;cout << "第一棵树中的叶子节点数:" << bt1.Num_Of_LeafNode() << endl;cout << "第一棵树中度为1的节点数:" << bt1.Num_Of_Degree_1() << endl;cout << "第一棵树中度为2的节点数:" << bt1.Num_Of_Degree_2() << endl;cout << endl;cout << "第二棵树的前序遍历为:";bt2.PreOrder();cout << "第二棵树的中序遍历为:";bt2.InOrder();cout << "第二棵树的后序遍历为:";bt2.PostOrder();cout << "第二棵树的深度为:" << bt2.BTDepth() << endl;cout << "第二棵树中的节点数:" << bt2.Num_Of_TreeNode() << endl;cout << "第二棵树中的叶子节点数:" << bt2.Num_Of_LeafNode() << endl;cout << "第二棵树中度为1的节点数:" << bt2.Num_Of_Degree_1() << endl;cout << "第二棵树中度为2的节点数:" << bt2.Num_Of_Degree_2() << endl;cout << "两棵树是否相似:" << bt1.Is_Similar(bt1.GetRoot(), bt2.GetRoot());
}int main()
{binary_Test();return 0;
}

这篇关于数据结构上机实验——二叉树的实现、二叉树遍历、求二叉树的深度/节点数目/叶节点数目、计算二叉树度为1或2的节点数、判断二叉树是否相似的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/302242。

相关文章

C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...
Java实现检查多个时间段是否有重合

Java实现检查多个时间段是否有重合

《Java实现检查多个时间段是否有重合》这篇文章主要为大家详细介绍了如何使用Java实现检查多个时间段是否有重合,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录流程概述步骤详解China编程步骤1：定义时间段类步骤2：添加时间段步骤3：检查时间段是否有重合步骤4：输出结果示例代码结语作
阅读更多...
Java判断多个时间段是否重合的方法小结

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
Java覆盖第三方jar包中的某一个类的实现方法

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下：需要在
阅读更多...
如何使用Java实现请求deepseek

如何使用Java实现请求deepseek

《如何使用Java实现请求deepseek》这篇文章主要为大家详细介绍了如何使用Java实现请求deepseek功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1.deepseek的api创建2.Java实现请求deepseek2.1 pom文件2.2 json转化文件2.2
阅读更多...
python使用fastapi实现多语言国际化的操作指南

python使用fastapi实现多语言国际化的操作指南

《python使用fastapi实现多语言国际化的操作指南》本文介绍了使用Python和FastAPI实现多语言国际化的操作指南,包括多语言架构技术栈、翻译管理、前端本地化、语言切换机制以及常见陷阱和... 目录多语言国际化实现指南项目多语言架构技术栈目录结构翻译工作流1. 翻译数据存储2. 翻译生成脚本
阅读更多...
如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python如何实现PDF隐私信息检测

Python如何实现PDF隐私信息检测

《Python如何实现PDF隐私信息检测》随着越来越多的个人信息以电子形式存储和传输,确保这些信息的安全至关重要,本文将介绍如何使用Python检测PDF文件中的隐私信息,需要的可以参考下... 目录项目背景技术栈代码解析功能说明运行结php果在当今，数据隐私保护变得尤为重要。随着越来越多的个人信息以电子形
阅读更多...
使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置（可选）启动服务应用场景
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2