Tree各种遍历实现
2024-08-29 18:21:56
数据结构、算法及应用 张宪超主编 科学出版社
1. 数据结构的基本概念知识
数据结构的逻辑结构由数据节点和连接两个节点的边组成。
数据节点的数据类型:整型,实数型,布尔型,字符型,指针数据类型
结构的分类:讨论逻辑结构( K,R)一般以关系集R为主: 线性结构,属性结构,图结构。
数据的存储结构:顺序存储,连接方法,索引方法,散列方法,分析一下这些不同的数据存储方式:顺序存储就是把一组节点放在一片地址相邻得存储单元,节点中的逻辑关系用存储单元之间的自然关系来表达。顺序存储是为使用整数编码访问数据节点提供了便利。
链接方法是在节点的存储结构中附加指针域来存储节点的逻辑关系。链接方法中的数据节点有两部分组成:数据域存放节点本身的数据,指针域存放指向其后继结点指针。该方法使用于经常需要增删节点而动态变化的数据结构。
索引方法:索引表中的存储空间是附加在节点存储空间之外的,每一个元素就是指向相应的数据节点的指针。索引适合于大数据量的时候,减少对数据的读取。
散列方式是一种索引的扩展,散列方法利用散列函数进行索引值的计算,然后通过索引技术求出该节点的指针地址。主要思想就是利用节点的关键字码来确定其存储的地址。散列函数应该尽量的将地址均匀分布。
2. 树结构的复习
2.1 树结构的定义
树是由n个节点组成的有限集合。在这个集合中没有直接前驱的节点称为根节点。当 n==0的时候,是一个空树;当 n>0的时候,所有的节点中仅有一个是根节点,其余的可以分成 m个不相交的子集合,每一个子集合都是满足树的定义,称为根的子树。
关于树的一些名词解释:
结点:树结构中等个每一个元素称为一个结点,该结点包括该元素的值和该元素的逻辑关系信息。
边:使用 <m,n>表示,结点m 指向n
双亲结点和孩子结点: <m,n>则m 是n的双亲结点,也称为父节点, n是m 的子节点。
兄弟结点:如果两个结点有共同的双亲结点,则两个节点称为兄弟结点。
叶子结点:没有孩子结点的称为叶子结点
结点的度:就是该结点的孩子结点的书目
树的度:树结构中的所有节点的度的最大值
,然后往后面加
树的高度:输的高度是树的深入加 1.
路径:从输的一个结点 n到另一个结点m,如果存在一个有限集合 S连接两个结点,则是mn之间的一个路径
有序树:如果树中的结点的所有子树之间存在确定的次序关系,则称该树是有序树,反之是无序树。
森林:有多个互不相交的数组成的集合
树的基本性质
度为m的树,其第 i层上之多有m^i 个节点
的树
完全二叉树:除了最后一层以外其他所有的结点树都达到最大值,二最后一层上的所有节点分布在该层最左边连续的位置上。其性质:叶子结点只能够在最后两层出现。对于任意一层结点,如果左子树的高度是 m右子树不能够大于m,也不小于 m-1。
满二叉树:所有分支节点都有非空的左子树和非空右子树,所有的叶子结点都在同一层,这样的树称为满二叉树。叶子结点都在最后一层。
;
template <class T >
class BinaryTreeNode {
public:
T element;
BinaryTreeNode< T> * left;
BinaryTreeNode< T> * right;
};
template <class T >
class BinaryTree {
private:
BinaryTreeNode * root;
public:
void visit(BinaryTreeNode< T> * node){
cout << node->element << endl;
}
// 层次遍历,也就是广度优先遍历
void level_order( BinaryTreeNode<T > * root ){
queue< BinaryTreeNode<T >* > nodeQueue;
BinaryTreeNode<T >* pointer = this->root;
if(pointer){
nodeQueue.push(pointer);
}
while(!nodeQueue.empty()){
pointer=nodeQueue.front();
visit(pointer);
nodeQueue.pop();
if(pointer->left){
nodeQueue.push(pointer->left);
}
if(pointer->right){
nodeQueue.push(pointer->right);
}
}
}
//深度优先遍历分为前序遍历,中序遍历和后续遍历
/*
前序遍历就是先序遍历,
1 访问根节点
2. 前序遍历左子树
3. 前序遍历右子树
*/
void pre_order( BinaryTreeNode<T > * root ){
if( root!= NULL){
visit( root);
pre_order( root->left);
pre_order( root->right);
}
}
//使用 stack
void pre_order_no_recusion( BinaryTreeNode<T > * root ){
stack< BinaryTreeNode<T >*> nodeStack;
BinaryTreeNode<T >* pointer=root;
while(!nodeStack.empty|| pointer){
if(pointer){
visit(pointer);
if(pointer->right!= NULL){
nodeStack.push(pointer->right);
}
pointer=pointer->left;
}
else{
pointer=nodeStack.top();
nodeStack.pop();
}
}
}
/*
中序遍历
*/
void in_order(BinaryTreeNode< T>* root){
if( root!= NULL){
in_order( root->left);
visit( root);
in_order( root->right);
}
}
void in_order_no_recusion( BinaryTreeNode<T >* root ){
stack< BinaryTreeNode<T >*> nodeStack;
BinaryTreeNode<T >* pointer=root;
while(!nodeStack.empty()||pointer){
if(pointer){
nodeStack.push(pointer);
pointer=pointer->left;
}
else{
pointer=nodeStack.top();
visit(pointer);
pointer=pointer->right;
nodeStack.pop()
}
}
}
/*
*/
void post_order( BinaryTreeNode<T >* root ){
if( root!= NULL){
post_order( root->left);
post_order( root->right);
visit( root);
}
}
void post_order_no_recusion( BinaryTreeNode<T >* root ){
stack< BinaryTreeNode<T >* > nodeStack;
BinaryTreeNode<T >* pointer =root;
BinaryTreeNode<T >* pre=root ;
while(pointer){
for(;pointer->left!= NULL;pointer=pointer->right){
nodeStack.push(pointer);
}
while(pointer && (pointer->right == NULL||pointer->right==pre)){
visit(pointer);
pre=pointer;
if(nodeStack.empty()){
return;
}
pointer=nodeStack.top();
nodeStack.pop();
}
nodeStack.push(pointer);
pointer= pointer->right;
}
}
};
最新文章
- Git 简明教程
- Android内部自带的SQLite数据库操作dos命令
- CEF3开发者系列之JS与C++交互之一
- 在hibernate中使用c3p0数据源
- Socket知识总结
- BZOJ 1709: [Usaco2007 Oct]Super Paintball超级弹珠
- Java调用yahoo!API获取天气数据
- 移动端web开发调试
- java常见文件操作
- 【JAVAWEB学习笔记】27_Redis:在Linux上的安装、Jedis和常用命令
- c++堆与栈的简单认识
- Docker 数据卷容器
- IDEA与eclipse:vm参数调优笔记
- C#解析XML 例子二
- window7环境下ZooKeeper的安装运行及监控查看
- 总目录(Catalog)
- Python——信号量
- Springmvc配置时间日期转换
- EWS 流通知订阅邮件
- 有关FPGA
热门文章
- 移动端web开发 尽量哪些标签 常用标签及注意事项
- html-4, form 表单 输入、传文件、单选、多选、下拉菜单、文本描述、重置、submit、按钮限制输入
- javascript 理解对象--- 属性类型
- Spring MVC 复习笔记03
- 【GZAdmin】开源BS demo快速搭建
- 20145310 《Java程序设计》第6周学习总结
- 20144303 《Java程序设计》第三周学习总结
- 【Swift实现代码】iOS架构模式之MVP
- [洛谷P4918]信仰收集
- Codeforces Round #357 (Div. 2) 优先队列+模拟