c++经典例题之先序二叉树的构建
本篇文章小编将带大家一起回顾经典C++之构建先序二叉树,有兴趣的小伙伴一起来复习一下吧!
二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层)
第一、定义BinaryTreeNode 类
#include <iostream> #include <string> #include <queue> using namespace std; template<typename T >class BinaryTree; template <typename T> class BinaryTreeNode { public: friend class BinaryTree<T>; BinaryTreeNode() { data = NULL; lChild = rChild = NULL; } BinaryTreeNode(T newdata) { this->data = newdata; lChild = rChild = NULL; } T getData() { return data; } BinaryTreeNode<T> * getLeftNode() { return lChild; } BinaryTreeNode<T> * getRightNode() { return rChild; } T data; BinaryTreeNode<T>* lChild; BinaryTreeNode<T>* rChild; private: };
View Code
第二、定义BinaryTree 类
template <typename T> class BinaryTree { public: BinaryTreeNode<T> *root; char* p; BinaryTree() { root = NULL; } BinaryTree(T data) { root = new BinaryTreeNode<T>(data); root->lChild = NULL; root->rChild = NULL; } ~BinaryTree() { delete root; } //构建二叉树并返回 BinaryTreeNode<T>* CreateTree() { BinaryTreeNode<int>* bt = NULL; char t; cin >> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode<T>(num); bt->lChild = CreateTree(); bt->rChild = CreateTree(); } return bt; } //先序构建二叉树 BinaryTreeNode<T>* PreCreateTree() { BinaryTreeNode<int>* bt = NULL; if (this->root == NULL) { cout << "请输入根节点(#代表空树):"; } else { cout << "请输入节点(#代表空树):"; } char t; cin >> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode<T>(num); if (this->root == NULL) { this->root = bt; } cout << bt->data << "的左孩子"; bt->lChild = PreCreateTree(); cout << bt->data << "的右边孩子"; bt->rChild = PreCreateTree(); } return bt; } void preOderTraversal(BinaryTreeNode<T> *bt); //先序遍历 void inOrderTraversal(BinaryTreeNode<T> *bt); //中序遍历 void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历 void levelTraversal(BinaryTreeNode<T> *bt); //逐层遍历 private: }; template <typename T> void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) { if (bt) { cout << bt->data; BinaryTree<T>::preOderTraversal(bt->getLeftNode()); BinaryTree<T>::preOderTraversal(bt->getRightNode()); } } template <typename T> void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) { if (bt) { BinaryTree<T>::inOrderTraversal(bt->getLeftNode()); cout << bt->data; BinaryTree<T>::inOrderTraversal(bt->getRightNode()); } } template <typename T> void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) { if (bt) { BinaryTree<T>::postOrderTraversal(bt->getLeftNode()); BinaryTree<T>::postOrderTraversal(bt->getRightNode()); cout << bt->data; } } template <typename T> void BinaryTree<T>::levelTraversal(BinaryTreeNode<T> *bt) { queue<BinaryTreeNode<T>*> que; que.push(bt); while (!que.empty()) { BinaryTreeNode<T>* proot = que.front(); que.pop(); cout << proot->data; if (proot->lChild != NULL) { que.push(proot->lChild);//左孩子入队 } if (proot->rChild != NULL) { que.push(proot->rChild);//右孩子入队 } } }
View Code
第三、主程序运行
#include "pch.h" #include <iostream> #include "BinaryTree.h" int main() { //场景测试2 BinaryTree<int> btree; btree.PreCreateTree();//先序构建二叉树 cout << "先序遍历:"; btree.preOderTraversal(btree.root); cout << endl;//先序遍历 cout << "中序遍历:"; btree.inOrderTraversal(btree.root); cout << endl;//中序遍历 cout << "后序遍历:"; btree.postOrderTraversal(btree.root); cout << endl;//后序遍历 cout << "逐层序遍历:"; btree.levelTraversal(btree.root); }
View Code
最终测试运行截图
相关教程:C++视频教程
以上是c++经典例题之先序二叉树的构建的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

在C++并发编程中,数据结构的并发安全设计至关重要:临界区:使用互斥锁创建代码块,仅允许一个线程同时执行。读写锁:允许多个线程同时读取,但仅一个线程同时写入。无锁数据结构:使用原子操作实现并发安全,无需锁。实战案例:线程安全的队列:使用临界区保护队列操作,实现线程安全性。

C++对象布局和内存对齐优化内存使用效率:对象布局:数据成员按声明顺序存储,优化空间利用率。内存对齐:数据在内存中对齐,提升访问速度。alignas关键字指定自定义对齐,例如64字节对齐的CacheLine结构,提高缓存行访问效率。

实现定制比较器可以通过创建一个类,重载运算符()来实现,该运算符接受两个参数并指示比较结果。例如,StringLengthComparator类通过比较字符串长度来排序字符串:创建一个类并重载运算符(),返回布尔值指示比较结果。在容器算法中使用定制比较器进行排序。通过定制比较器,我们可以根据自定义标准对数据进行排序或比较,即使需要使用自定义比较标准。

策略模式在C++中的实现步骤如下:定义策略接口,声明需要执行的方法。创建具体策略类,分别实现该接口并提供不同的算法。使用上下文类持有具体策略类的引用,并通过它执行操作。

Golang和C++分别是垃圾回收和手动内存管理编程语言,语法和类型系统各异。Golang通过Goroutine实现并发编程,C++通过线程实现。Golang内存管理简单,C++性能更强。实战案例中,Golang代码更简洁,C++性能优势明显。

复制C++STL容器有以下三种方法:使用copy构造函数复制容器的内容到一个新容器中。使用assignment运算符复制容器的内容到目标容器中。使用std::copy算法复制容器中的元素。

C++智能指针通过指针计数、析构函数和虚函数表实现自动内存管理。指针计数跟踪引用数,当引用数降为0时,析构函数释放原始指针。虚函数表启用多态性,允许针对不同类型的智能指针实现特定行为。

嵌套异常处理在C++中通过嵌套的try-catch块实现,允许在异常处理程序中引发新异常。嵌套的try-catch步骤如下:1.外部try-catch块处理所有异常,包括内部异常处理程序抛出的异常。2.内部try-catch块处理特定类型的异常,如果发生超出范围的异常,则将控制权交给外部异常处理程序。
