树

news/2023/6/5 20:27:59

    今天，我们一起用C++写一颗树，目的是熟练C++的语法细节，具体如下：

LinkQueue.h内容如下：

#include "QueueNode.h"template<typename Type> class LinkQueue{
public:LinkQueue() :m_prear(NULL), m_pfront(NULL){}~LinkQueue(){MakeEmpty();}void Append(const Type item);Type Delete();Type GetFront();void MakeEmpty();bool IsEmpty() const{return m_pfront == NULL;}void Print();private:QueueNode<Type> *m_prear, *m_pfront;
};template<typename Type> void LinkQueue<Type>::MakeEmpty(){QueueNode<Type> *pdel;while (m_pfront){pdel = m_pfront;m_pfront = m_pfront->m_pnext;delete pdel;}
}template<typename Type> void LinkQueue<Type>::Append(const Type item){if (m_pfront == NULL){m_pfront = m_prear = new QueueNode<Type>(item);}else{m_prear = m_prear->m_pnext = new QueueNode<Type>(item);}
}template<typename Type> Type LinkQueue<Type>::Delete(){if (IsEmpty()){cout << "There is no element!" << endl;exit(1);}QueueNode<Type> *pdel = m_pfront;Type temp = m_pfront->m_data;m_pfront = m_pfront->m_pnext;delete pdel;return temp;
}template<typename Type> Type LinkQueue<Type>::GetFront(){if (IsEmpty()){cout << "There is no element!" << endl;exit(1);}return m_pfront->m_data;
}template<typename Type> void LinkQueue<Type>::Print(){QueueNode<Type> *pmove = m_pfront;cout << "front";while (pmove){cout << "--->" << pmove->m_data;pmove = pmove->m_pnext;}cout << "--->rear" << endl << endl << endl;
}
QueueNode.h内容如下：

template<typename Type> class LinkQueue;template<typename Type> class QueueNode{
private:friend class LinkQueue < Type > ;QueueNode(const Type item, QueueNode<Type> *next = NULL):m_data(item), m_pnext(next){}
private:Type m_data;QueueNode<Type> *m_pnext;
};
Tree.h内容如下：

#include "TreeNode.h"
#include "LinkQueue.h"template<typename Type> class Tree{
public:Tree() :m_proot(NULL), m_pcurrent(NULL){}
public:TreeNode<Type> *GetCurrent(){	//Get the current nodereturn m_pcurrent;}void SetCurrent(TreeNode<Type> *current){	//set the current nodem_pcurrent = current;}bool Insert(Type item);		//insert an new node to current nodevoid Remove(Type item);		//delete the node whose data is equal to itemvoid Remove(TreeNode<Type> *current);	//delete the nodebool Find(Type item);		//find the node whose data is equal to itemvoid PrintChild(TreeNode<Type> *current);	//print the child treeTreeNode<Type> *Parent(TreeNode<Type> *current);	//get the parentvoid Print();				//print the treevoid PreOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root firstvoid PostOrder(TreeNode<Type> *root);	//ordering the tree by visiting the root lastvoid LevelOrder(TreeNode<Type> *root);	//ordering the tree by levelvoid PreOrder();void PostOrder();void LevelOrder();private:TreeNode<Type> *m_proot, *m_pcurrent;bool Find(TreeNode<Type> *root, Type item);void Remove(TreeNode<Type> *root, Type item);TreeNode<Type> *Parent(TreeNode<Type> *root, TreeNode<Type> *current);void Print(TreeNode<Type> *start, int n = 0);
};template<typename Type> bool Tree<Type>::Insert(Type item){TreeNode<Type> *newnode = new TreeNode<Type>(item);if (NULL == newnode){cout << "Application Error!" << endl;exit(1);}if (NULL == m_proot){m_proot = newnode;m_pcurrent = m_proot;return 1;}if (NULL == m_pcurrent){cerr << "insert error!" << endl;return 0;}if (NULL == m_pcurrent->m_pfirst){m_pcurrent->m_pfirst = newnode;m_pcurrent = newnode;return 1;}TreeNode<Type> *pmove = m_pcurrent->m_pfirst;while (pmove->m_pnext){pmove = pmove->m_pnext;}pmove->m_pnext = newnode;m_pcurrent = newnode;return 1;}template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *current){if (NULL == current){return;}TreeNode<Type> *temp = Parent(current);if (NULL == temp){TreeNode<Type> *pmove = current->m_pfirst;if (NULL != pmove->m_pfirst){pmove = pmove->m_pfirst;while (pmove->m_pnext){pmove = pmove->m_pnext;}pmove->m_pnext = current->m_pfirst->m_pnext;current->m_pfirst->m_pnext = NULL;}else{pmove->m_pfirst = pmove->m_pnext;}m_proot = current->m_pfirst;}else{if (temp->m_pfirst == current){TreeNode<Type> *pmove = current->m_pfirst;if (pmove){while (pmove->m_pnext){pmove = pmove->m_pnext;}pmove->m_pnext = current->m_pnext;}else{current->m_pfirst = current->m_pnext;}}else{TreeNode<Type> *pmove = temp->m_pfirst;while (pmove->m_pnext != current){pmove = pmove->m_pnext;}pmove->m_pnext = current->m_pnext;while (pmove->m_pnext){pmove = pmove->m_pnext;}pmove->m_pnext = current->m_pfirst;}}delete current;
}template<typename Type> void Tree<Type>::Remove(TreeNode<Type> *root, Type item){if (NULL == root){return;}if (root->m_pfirst){TreeNode<Type> *pmove = root->m_pfirst;while (pmove){Remove(pmove, item);pmove = pmove->m_pnext;}}if (root->m_data == item){Remove(root);}}
template<typename Type> void Tree<Type>::Remove(Type item){return Remove(m_proot, item);
}template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *root, TreeNode<Type> *current){if (NULL == root){return NULL;}TreeNode<Type> *pmove = root->m_pfirst, *temp;if (NULL != pmove){while (pmove){if (pmove == current){return root;}pmove = pmove->m_pnext;}}pmove = root->m_pfirst;while (pmove){temp = Parent(pmove, current);if (temp){return temp;}pmove = pmove->m_pnext;}return NULL;
}template<typename Type> TreeNode<Type>* Tree<Type>::Parent(TreeNode<Type> *current){return Parent(m_proot, current);
}template<typename Type> void Tree<Type>::PrintChild(TreeNode<Type> *current){TreeNode<Type> *pmove = current->m_pfirst;cout << "first";if (NULL != pmove){cout << "--->" << pmove->m_data;}while (pmove->m_pnext){cout << "--->" << pmove->m_data;pmove = pmove->m_pnext;}
}template<typename Type> bool Tree<Type>::Find(TreeNode<Type> *root, Type item){if (root->m_data == item){return 1;}if (NULL == root){return 0;}TreeNode<Type> *pmove = root->m_pfirst;if (NULL == pmove){return 0;}while (pmove){if (Find(pmove, item)){return 1;}pmove = pmove->m_pnext;}return 0;
}template<typename Type> bool Tree<Type>::Find(Type item){return Find(m_proot, item);
}template<typename Type> void Tree<Type>::Print(TreeNode<Type> *start, int n = 0){if (NULL == start){for (int i = 0; i < n; i++){cout << "     ";}cout << "NULL" << endl;return;}TreeNode<Type> *pmove = start->m_pfirst;Print(pmove, n + 1);for (int i = 0; i < n; i++){cout << "     ";}cout << start->m_data << "--->" << endl;if (NULL == pmove){return;}pmove = pmove->m_pnext;while (pmove){Print(pmove, n + 1);pmove = pmove->m_pnext;}
}template<typename Type> void Tree<Type>::Print(){Print(m_proot);
}template<typename Type> void Tree<Type>::PreOrder(TreeNode<Type> *root)
{if (NULL == root){return;}cout << root->m_data;TreeNode<Type> *pmove = root->m_pfirst;while (pmove){PreOrder(pmove);pmove = pmove->m_pnext;}
}template<typename Type> void Tree<Type>::PostOrder(TreeNode<Type> *root)
{if (NULL == root){return;}TreeNode<Type> *pmove = root->m_pfirst;while (pmove){PostOrder(pmove);pmove = pmove->m_pnext;}cout << root->m_data;
}template<typename Type> void Tree<Type>::PreOrder(){PreOrder(m_proot);
}template<typename Type> void Tree<Type>::PostOrder(){PostOrder(m_proot);
}template<typename Type> void Tree<Type>::LevelOrder(TreeNode<Type> *root)
{	//using queueLinkQueue<TreeNode<Type> *> queue;TreeNode<Type> *pmove, *ptemp;if (root != NULL){queue.Append(root);while (!queue.IsEmpty()){ptemp = queue.Delete();cout << ptemp->m_data;pmove = ptemp->m_pfirst;while (pmove){queue.Append(pmove);pmove = pmove->m_pnext;}}}
}template<typename Type> void Tree<Type>::LevelOrder()
{LevelOrder(m_proot);
}
TreeNode.h具体内容如下：

template<typename Type> class Tree;template<typename Type> class TreeNode{
public:friend class Tree < Type > ;private:Type m_data;TreeNode<Type> *m_pfirst, *m_pnext;TreeNode() :m_pfirst(NULL), m_pnext(NULL){}TreeNode(Type item, TreeNode<Type> *first = NULL, TreeNode<Type> *next = NULL):m_data(item), m_pfirst(first), m_pnext(next){}
};
main.cpp具体内容如下：

#include <iostream>using namespace std;#include "Tree.h"int main()
{Tree<int> tree;int init[10] = { 3, 6, 0, 2, 8, 4, 9, 1, 5, 7 };for (int i = 0; i < 10; i++){tree.Insert(init[i]);if (1 == i % 2){tree.SetCurrent(tree.Parent(tree.GetCurrent()));}}tree.Print();cout << endl << endl << endl;tree.Remove(3);tree.Print();cout << endl << endl << endl;cout << tree.Find(5) << endl << tree.Find(11) << endl;tree.PreOrder();cout << endl;tree.PostOrder();cout << endl;tree.LevelOrder();cin.get();return 0;
}
运行效果如图1所示：

图1 运行效果


转载于:https://www.cnblogs.com/new0801/p/6176928.html


https://dhexx.cn/news/show-18168.html

相关文章

Stream流中collect方法

Stream流中collect方法

Stream流中collect方法一、收集Stream流到集合和指定集和中1、示例2、结果二、收集 Stream 流中的数据到数组中1、示例2、结果三、Stream流中数据聚合/分组/分区/拼接操作1、聚合操作2、分组操作3、多级分组操作4、分区操作5、拼接操作一、收集Stream流到集合和指定集和中 Str…
阅读更多...
Impala数据存储方式和压缩方式

Impala数据存储方式和压缩方式

数据存储方式&#xff1a;注意&#xff0c;Impala不支持ORC格式数据压缩方式和好处&#xff1a; 减小了数据的体积减小了IO&#xff0c;相当于增加了解压缩的时间&#xff0c;减小了IO传输文件的时间
阅读更多...
Stream流中forEach方法

Stream流中forEach方法

Stream流中forEach方法一、forEach方法一、forEach方法 java.util.function.Consumer接口是一个消费型接口。 Consumer接口中包含抽象方法void accept(T t)&#xff0c;意为消费一个指定泛型的数据。 void forEach(Consumer<? super T> action);Testvoid test8() {Lis…
阅读更多...
java学习面向对象之this

java学习面向对象之this

在我们讲构造函数的时候&#xff0c;我们知道&#xff0c;如果同时在java的堆内存当中&#xff0c;同时存在好几个刚进内存&#xff0c;但是又没来得及初始化的同一个类的对象。在这种情况下&#xff0c;那么如何去区分栈内存当中的构造函数是属于那个对象的呢&#xff0c;其实…
阅读更多...
Stream流中filter方法

Stream流中filter方法

Stream流中filter方法一、filter方法一、filter方法 Stream<T> filter(Predicate<? super T> predicate);Testvoid test9() {List<People> peopleList new ArrayList<>();peopleList.add(new People(1, "小王", 1));peopleList.add(new Pe…
阅读更多...
学习Vue基本使用方法和组件

学习Vue基本使用方法和组件

学习Vue基本使用方法和组件一、基本使用方法1、常用二、组件1、全局组件2、局部组件3、特殊元素特殊对待三、其他一、基本使用方法 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-C…
阅读更多...
Nodejs使用webpack或vue-cli搭建vue项目

Nodejs使用webpack或vue-cli搭建vue项目

Nodejs搭建vue项目一、下载后基本配置1、安装cnpm以及全局二、webpack工程三、vue-cli工程四、解读1、项目根目录中的文件2、public文件夹3、src文件夹五、总结六、遇到问题1、安装vue出现报错2、项目实操一、下载后基本配置 1、安装cnpm以及全局 在 nodejs 安装目录下&#…
阅读更多...
Vue 项目初始化

Vue 项目初始化

Vue 项目初始化一、初始化1、删除 Helloword.vue2、删除 views 中的文件3、自定义页面4、清空默认根组件、项目样式二、其他1、设置行尾序列一、初始化 1、删除 Helloword.vue 删除 src文件夹下的 cpmponents文件夹下的 Helloword.vue 文件 2、删除 views 中的文件 删除 v…
阅读更多...
Hbase Shell命令大全

Hbase Shell命令大全

hbase shell - get,scan,过滤器等使用https://blog.csdn.net/qq_41712271/article/details/108465612 —般操作 1 查看命令行的具体使用 help help scan 2 查看操作表的命令 table_help 3 查询服务器状态 可以为 ‘summary’, ‘simple’, ‘detailed’, or ‘replication’…
阅读更多...
第二周会议：任务分配与时间规划

第二周会议：任务分配与时间规划

系统架构&#xff1a;MVC 开发模式&#xff1a;敏捷开发 时间规划&#xff1a; l 第3周(9.30~10.6)&#xff1a;逻辑层、底层迅速走读所有代码&#xff0c;熟悉整体架构&#xff0c;江林楠、洪宇、王需三人平时需要密切沟通&#xff0c;尽快开会给表现层做大致介绍。底层&…
阅读更多...
最新文章

Copyright @ 2022~2023