AI 助理

你好，我是AI助理，可以解答问题、推荐解决方案等

开发者社区 大数据与机器学习 文章 正文
大数据与机器学习
内容
活动
关注

基本二叉树与排序二叉树（C++源码）

2025-10-01 243
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
蒋星熠Jaxonic
简介： 本程序实现二叉树基本操作与二叉排序树应用。支持前序建树、四种遍历、求深度、叶子数、第K层节点数及查找功能；并实现二叉排序树的构建、中序输出与查找比较次数统计，分析不同插入顺序对树形态和查找效率的影响。

​
一、基本二叉树
//1、 二叉树的基本操作（必做题）
//
//（1） 根据二叉树的前序遍历序列，构建二叉树；
//
//（2） 实现二叉树的层序遍历、前序遍历、中序遍历和后序遍历；
//
//（3） 求二叉树的深度；
//
//（4） 求二叉树中叶子节点数量；
//
//（5） 求二叉树第K层结点数量；
//
//（6） 在二叉树中查找值为x的结点，若找到则返回结点指针，找不到则返回NULL

include

include

using namespace std;

template
struct Node
{
DataType TreeData;
Nodeleft;
Noderight;
};

//void AddNode(int data)
//{
// BTNode *s=new BTNode;
// s->left=NULL;
// s->right=NULL;
// s->data=data;
//}

//也可以把创建头结点root封装在一个函数里，将创建的root地址传到私有变量root中，也具有安全性。

template
class MyTree
{
public:
MyTree(){root=Create();}
~MyTree(){Release(root);}
void PreOrder(){PreOrder(root);};//前序遍历
void InOrder(){InOrder(root);};//中序遍历
void PostOrder(){PostOrder(root);};//后序遍历
void LevelOrder();//层序遍历
int TreeLength(){TreeLength(root);};//求树的深度
int TreeLeaf(){TreeLeaf(root);};//树的叶子结点个数
int TreeKNum(int k){TreeKNum(root,k);}; //树第k层结点个数
Node FindX(DataType x){FindX(root,x);};
private:
NodeCreate();
void Release(Nodebt);
void PreOrder(Nodebt);
void InOrder(Nodebt);
void PostOrder(Nodebt);
int TreeLength(Noderoot);
int TreeLeaf(Noderoot) ;
int TreeKNum(Noderoot,int k) ;
Node FindX(Noderoot,DataType x);
Noderoot;
};

template
Node MyTree::Create()//根据二叉树的前序遍历序列，构建二叉树
{
Nodebt;
char ch;
cout<<"请输入数据：";
cin>>ch;
if(ch=='#')
{
bt=nullptr;
}
else
{
bt=new Node;
bt->TreeData=ch;
bt->left=Create();
bt->right=Create();
}
return bt;
}

template
void MyTree::Release(Node*bt)
{
if(bt==nullptr)
return;
else{
Release(bt->left);
Release(bt->right);
delete bt;
}
}

//前序遍历
template
void MyTree::PreOrder(Node*bt)
{
if(bt==nullptr)
return;
else{
cout<TreeData<<" ";
PreOrder(bt->left);
PreOrder(bt->right);
}
}

//中序遍历
template
void MyTree::InOrder(Node*bt)
{
if(bt==nullptr)
return;
else{ 

 InOrder(bt->left); cout<<bt->TreeData<<" "; InOrder(bt->right); }

}

//后序遍历
template
void MyTree::PostOrder(Node*bt)
{
if(bt==nullptr)
return;
else{ 

 PostOrder(bt->left); PostOrder(bt->right); cout<<bt->TreeData<<" "; }

}

//层序遍历
template
void MyTree::LevelOrder()
{
NodeQ[100],q=nullptr;
int front=-1,rear=-1;
if(root==nullptr)
return;
Q[++rear]=root;
while(front!=rear)
{
q=Q[++front];
cout<TreeData<<" ";
if(q->left!=nullptr)
Q[++rear]=q->left;
if(q->right!=nullptr)
Q[++rear]=q->right;
}
}

//求二叉树的深度
template
int MyTree::TreeLength(Node*root)
{
if (root==nullptr) return 0;
int maxleft=TreeLength(root->left);
int maxright=TreeLength(root->right);
return max(maxleft,maxright)+1;

}

//求二叉树中叶子节点数量
template
int MyTree::TreeLeaf(Node*root)
{
if(root==nullptr)
return 0;
else{ 

 int count1=TreeLeaf(root->left); int count2=TreeLeaf(root->right); if(root->left==nullptr&&root->right==nullptr) { return count1+count2+1; } else return count1+count2; }

}

//求二叉树第K层结点数量
template
int MyTree::TreeKNum(Node*root,int k)
{
if(root==NULL)
return 0;
if(k==1)
return 1;
int left=TreeKNum(root->left,k-1);
int right=TreeKNum(root->right,k-1);

return left+right;

}

//在二叉树中查找值为x的结点，若找到则返回结点指针，找不到则返回NULL
template
Node MyTree::FindX(Noderoot,DataType x)
{
if(root==nullptr)
return nullptr;
if(root->TreeData==x)
return root;
Noderet1=FindX(root->left,x) ;
if(ret1)
return ret1;
Noderet2=FindX(root->right,x) ;
if(ret2)
return ret2;

return nullptr;

}

int main()
{
MyTreeT;
cout<<"该二叉树的前序遍历序列是：";
T.PreOrder();
cout<<endl;
cout<<"该二叉树的中序遍历序列是：";
T.InOrder();
cout<<endl;
cout<<"该二叉树的后序遍历序列是：";
T.PostOrder();
cout<<endl;
cout<<"该二叉树的层序遍历序列是：";
T.LevelOrder();
cout<<endl;
cout<<"该二叉树的深度是："<<T.TreeLength() <<endl;
cout<<"该二叉树的叶子数量是："<<T.TreeLeaf()<<endl;

for(int i=0;i<T.TreeLength();i++) { cout<<"该二叉树第"<<i+1<<"层结点数量是："<<T.TreeKNum(i+1)<<endl; } char x; cout<<"请输入你要查找的值："; cin>>x; if(T.FindX(x)==nullptr) cout<<"没找到"; else cout<<"找到了,结点地址为："<<T.FindX(x); return 0;

}

伪代码说明：

//伪代码：
//定义模板结构体 Node，包含：
// 数据类型 TreeData
// 指向左子节点的指针 left
// 指向右子节点的指针 right
//
//定义模板类 MyTree，包含：
// 私有成员变量 root，类型为 Node
//
// 构造函数 MyTree()：
// 调用 Create() 方法初始化 root
//
// 析构函数 ~MyTree()：
// 调用 Release() 方法释放 root 及其子节点
//
// 成员函数：
// void PreOrder()：前序遍历树，调用 PreOrder(root)
// void InOrder()：中序遍历树，调用 InOrder(root)
// void PostOrder()：后序遍历树，调用 PostOrder(root)
// void LevelOrder()：层序遍历树
// {
// 使用一个队列来辅助遍历。
// 首先将根节点入队，然后进入一个循环，每次从队列中取出一个节点，输出其值，并将其左右子节点（如果存在）依次入队。循环直到队列为空。
// }
// int TreeLength()：返回树的深度，调用 TreeLength(root)
// int TreeLeaf()：返回树的叶子节点数量，调用 TreeLeaf(root)
// int TreeKNum(int k)：返回树第 k 层节点数量，调用 TreeKNum(root, k)
// Node FindX(DataType x)：查找值为 x 的节点，调用 FindX(root, x)
//
// 私有成员函数：
// Node Create()：根据用户输入的前序遍历序列构建二叉树
// {
// 初始化MyTree对象，调用Create()函数创建一个空的或根据输入构建的二叉树，并将根节点指针root指向这个新创建的树。
// }
// void Release(Node bt)：释放二叉树 bt 的所有节点
// {
// 释放MyTree对象所占用的内存资源，即递归地删除二叉树中的所有节点。
// }
// void PreOrder(Node bt)：前序遍历二叉树 bt
// void InOrder(Node bt)：中序遍历二叉树 bt
// void PostOrder(Node bt)：后序遍历二叉树 bt
// int TreeLength(Node root)：计算二叉树 root 的深度
// {
// 递归地计算左子树和右子树的深度，并返回较大值加1（加上当前节点）。
// }
// int TreeLeaf(Node root)：计算二叉树 root 的叶子节点数量
// {
// 递归计算左子树和右子树中的叶子节点个数，
// 如果当前节点是叶子节点（即没有左右子节点），则计数加1。
// }
// int TreeKNum(Node root, int k)：计算二叉树 root 第 k 层的节点数量
// {
// 递归计算左子树和右子树中第K-1层节点的个数之和（因为当前节点是第1层，所以要减1）。当K为1时，直接返回1（因为任何非空树的根节点都在第1层）。
// }
// Node FindX(Node root, DataType x)：在二叉树 root 中查找值为 x 的节点
// {
// 递归地在左子树和右子树中查找，如果找到值为x的节点，则返回该节点的指针；如果左右子树都没有找到，则返回nullptr
// }
//
//主函数 main()：
// 创建 MyTree 类型的对象 T
// 输出 T 的前序、中序、后序和层序遍历序列
// 输出 T 的深度和叶子节点数量
// 对于从 1 到树深度的每一层，输出该层的节点数量
// 提示用户输入要查找的值 x
// 调用 FindX(x) 查找值 x，输出查找结果

二、排序二叉树
//2、 二叉树的应用：二叉排序树（必做题）
//
//问题描述：二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点值均不大于根节点值；
//2. 若右子树非空，则右子树上所有节点值均不小于根节点值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个值各不相同的节点。
//
//（1）构建二叉排序树，即按给定顺序将结点插入一个初始为空树的二叉排序树中。
//
//（2）输出二叉排序树的中序遍历序列。
//
//（3）根据二叉排序树的性质，实现二叉排序树的结点查找功能，即查找某个值为key的结点否在二叉排序树中，若找到则输出查找过程中结点比较次数，若找不到则输出“Not Found”。
//
//（4）对于相同的数据元素集合，请分析在数据元素顺序不同的情况下，构建的二叉排序树是否相同，对节点查找操作的性能有何影响。

include

include

using namespace std;

template
struct Node
{
DataType TreeData;
Nodeleft;
Noderight;
};

template
class MyTree
{
public:
MyTree(){root=nullptr;}
~MyTree(){Release(root);}
void InsertNode(DataType x);
void InOrder(){InOrder(root);};//中序遍历
int FindX(DataType x){FindX(root,x);};

private: void Release(Node<DataType>*bt); void InOrder(Node<DataType>*bt); int FindX(Node<DataType>*root,DataType x); Node<DataType>*root;

};

template
void MyTree::Release(Node*bt)
{
if(bt==nullptr)
return;
else{
Release(bt->left);
Release(bt->right);
delete bt;
}
}

template
void MyTree::InsertNode(DataType x)
{
if(root==nullptr)
{
Node*newnode=new Node;
newnode->TreeData =x;
newnode->left=nullptr;
newnode->right=nullptr;
root=newnode;
return;
}

Node<DataType>*location=root; Node<DataType>*prev=nullptr; while(location!=nullptr) { prev=location; if(x<location->TreeData) { location=location->left; } else { location=location->right; } } if(x < prev->TreeData) { Node<DataType>*newnode=new Node<DataType>; newnode->TreeData =x; newnode->left=nullptr; newnode->right=nullptr; prev->left=newnode; } else { Node<DataType>*newnode=new Node<DataType>; newnode->TreeData =x; newnode->left=nullptr; newnode->right=nullptr; prev->right=newnode; }

}

template
void MyTree::InOrder(Node*bt)
{
if(bt==nullptr)
return;
else
{
InOrder(bt->left );
cout<TreeData <<" ";
InOrder(bt->right );
}

}

template //只要用到递归都需要root形参
int MyTree::FindX(Node*root,DataType x)
{
int count=0;
while(x!=root->TreeData)
{
if(xTreeData)
{
root=root->left;
count++;
}
if(x>root->TreeData)
{
root=root->right;
count++;
}
}

if(root==nullptr) return 0; return count+1;

}

int main()
{
MyTreeT;
T.InsertNode(5) ;
T.InsertNode(10) ;
T.InsertNode(6) ;
T.InsertNode(3) ;
T.InsertNode(15) ;
T.InsertNode(20) ;
T.InsertNode(11) ;
T.InOrder() ;

cout<<endl; int x; cout<<"请输入你要查找的值："; cin>>x; if(T.FindX(x)==0) cout<<"Not Found"; else cout<<"找到了,查找比较次数为："<<T.FindX(x); return 0;

}

伪代码说明：

//伪代码：
//定义结构体 Node：
// 包含：
// 数据域 TreeData
// 指向左子节点的指针 left
// 指向右子节点的指针 right
//
//定义类 MyTree：
// 包含：
// 私有成员：
// 指向根节点的指针 root
//
// 公有成员：
// 构造函数 MyTree()，初始化 root 为 nullptr
// 析构函数 ~MyTree()，释放所有节点
// 插入节点的方法 InsertNode(数据类型 x)
// 中序遍历的方法 InOrder()
// 查找节点的方法 FindX(数据类型 x)，返回查找过程中的比较次数，如果未找到则返回 0
//
//私有成员函数：
// 释放树的方法 Release(Node bt)
// 中序遍历的方法 InOrder(Node bt)
// 查找节点的方法 FindX(Node* root, 数据类型 x)
//
//
//实现 MyTree 的成员函数：
//
//释放树：
// 如果节点 bt 为空，则返回
// 否则：
// 递归释放左子树
// 递归释放右子树
// 删除当前节点
//
//插入节点：
// 如果根节点为空，则创建新节点并设为根节点
// 否则：
// 找到插入位置的前一个节点 prev
// 根据 x 的值决定插入到 prev 的左子树还是右子树
//
//中序遍历：
// 如果节点 bt 为空，则返回
// 否则：
// 递归中序遍历左子树
// 访问当前节点（输出 TreeData）
// 递归中序遍历右子树
//
//查找节点：
// 初始化计数器 count 为 0
// 在树中查找 x，比较 x 与当前节点的 TreeData：
// 如果 x 小于 TreeData，则移动到左子节点，count 加 1
// 如果 x 大于 TreeData，则移动到右子节点，count 加 1
// 如果找到 x，则返回 count + 1
// 如果未找到（即 root 为 nullptr），则返回 0
//
//主函数 main()：
// 创建 MyTree 实例 T
// 向 T 中插入一系列节点（5, 10, 6, 3, 15, 20, 11）
// 对 T 进行中序遍历并输出结果
// 提示用户输入要查找的值 x
// 调用 FindX 方法查找 x
// 根据返回值输出查找结果（找到或未找到，以及比较次数）

​

文章标签：
C++
关键词：
C++源码
二叉树C++
排序C++
来 源：
开发者社区 > 大数据与机器学习 > 文章 > 正文

大数据与机器学习
蒋星熠Jaxonic
目录
相关文章
ephemerals__
|
8月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map（附源码）
本文基于红黑树的实现，模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改，实现了两种容器的功能。主要步骤包括：1) 修改红黑树节点结构以支持不同数据类型；2) 使用仿函数适配键值比较逻辑；3) 实现双向迭代器支持遍历操作；4) 封装`insert`、`find`等接口，并为`map`实现`operator[]`。最终，通过测试代码验证了功能的正确性。此实现减少了代码冗余，展示了模板与仿函数的强大灵活性。
ephemerals__
229 2
RossyYan
|
10月前
|
Java C++
【C++数据结构——树】二叉树的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数（简单示例，手动构建） TreeNode*create
RossyYan
282 12
RossyYan
|
10月前
|
C++
【C++数据结构——树】二叉树的性质（头歌实践教学平台习题）【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树，并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括： 1. **定义二叉树节点结构体**：定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**：通过解析括号表示串，递归地构建二叉树的各个节点及其子树。 3. **使用示例**：展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**： - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后，提供了测试说明及通关代
RossyYan
189 10
RossyYan
|
10月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】
本关任务是实现二路归并算法，即将两个有序数组合并为一个有序数组。主要内容包括： - **任务描述**：实现二路归并算法。 - **相关知识**： - 二路归并算法的基本概念。 - 算法步骤：通过比较两个有序数组的元素，依次将较小的元素放入新数组中。 - 代码示例（以 C++ 为例）。 - 时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 - **测试说明**：平台会对你编写的代码进行测试，提供输入和输出示例。 - **通关代码**：提供了完整的 C++ 实现代码。 - **测试结果**：展示代码运行后的排序结果。 开始你的任务吧，祝你成功！
RossyYan
305 10
RossyYan
|
10月前
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括： - **任务描述**：实现希尔排序算法。 - **相关知识**： - 排序算法基础概念，如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列（增量序列）的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧，如循环嵌套和索引计算。 - **测试说明**：提供了测试输入和输出示例，帮助验证代码正确性。 - **我的通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了代码运行的测试结果。 通过这些内容，读者可以全面了解希尔排序的原理和实现方法。
RossyYan
226 10
RossyYan
|
10月前
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
259 7
RossyYan
|
10月前
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类（头歌实践教学平台习题）【合集】
1. **相关排序和查找算法的原理**：介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**：讲解如何定义`Array`类，包括类的声明和实现，以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**：探讨内存管理和正确访问数组元素的方法，确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**：解释排序和查找函数的参数传递方式及返回值处理，确保函数功能正确实现。 通过掌握这些知识，可以顺利地将排序和查找算法封装到`Array`类中，并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
RossyYan
205 5
RossyYan
|
10月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法（头歌教学实验平台习题） 【合集】
本任务旨在实现二叉树的遍历，包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义，并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑，以及层次遍历中队列的应用。最后提供了测试用例和预期输出，确保代码正确性。通过这些内容，帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
RossyYan
414 3
ephemerals__
|
11月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
247 1
ephemerals__
|
12月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
488 5
下一篇