南宁微网站开发,跨平台app开发框架,张家界做网站找哪家好,平昌移动网站建设文章目录 数据结构上机实验1.要求2.二叉树的实现2.1创建一颗二叉树2.2对这棵二叉树进行遍历2.3求二叉树的深度/节点数目/叶节点数目2.4计算二叉树中度为 1 或 2 的结点数2.5判断2棵二叉树是否相似#xff0c;若相似返回1#xff0c;否则返回0 3.全部源码测试#xff1a;Bina… 文章目录 数据结构上机实验1.要求2.二叉树的实现2.1创建一颗二叉树2.2对这棵二叉树进行遍历2.3求二叉树的深度/节点数目/叶节点数目2.4计算二叉树中度为 1 或 2 的结点数2.5判断2棵二叉树是否相似若相似返回1否则返回0 3.全部源码测试BinaryTree.htest.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);coutendl;
}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);coutendl;}//计算二叉树深度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#includeiostream
using namespace std;#includeBinaryTree.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;
}
