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脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

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

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

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

Dreamweaver CS6
视觉化网页开发工具

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

在 C 语言中,char 类型在字符串中用于:1. 存储单个字符;2. 使用数组表示字符串并以 null 终止符结束;3. 通过字符串操作函数进行操作;4. 从键盘读取或输出字符串。

C35 的计算本质上是组合数学,代表从 5 个元素中选择 3 个的组合数,其计算公式为 C53 = 5! / (3! * 2!),可通过循环避免直接计算阶乘以提高效率和避免溢出。另外,理解组合的本质和掌握高效的计算方法对于解决概率统计、密码学、算法设计等领域的许多问题至关重要。

语言多线程可以大大提升程序效率,C 语言中多线程的实现方式主要有四种:创建独立进程:创建多个独立运行的进程,每个进程拥有自己的内存空间。伪多线程:在一个进程中创建多个执行流,这些执行流共享同一内存空间,并交替执行。多线程库:使用pthreads等多线程库创建和管理线程,提供了丰富的线程操作函数。协程:一种轻量级的多线程实现,将任务划分成小的子任务,轮流执行。

std::unique 去除容器中的相邻重复元素,并将它们移到末尾,返回指向第一个重复元素的迭代器。std::distance 计算两个迭代器之间的距离,即它们指向的元素个数。这两个函数对于优化代码和提升效率很有用,但也需要注意一些陷阱,例如:std::unique 只处理相邻的重复元素。std::distance 在处理非随机访问迭代器时效率较低。通过掌握这些特性和最佳实践,你可以充分发挥这两个函数的威力。

C语言中蛇形命名法是一种编码风格约定,使用下划线连接多个单词构成变量名或函数名,以增强可读性。尽管它不会影响编译和运行,但冗长的命名、IDE支持问题和历史包袱需要考虑。

C 中 release_semaphore 函数用于释放已获得的信号量,以便其他线程或进程访问共享资源。它将信号量计数增加 1,允许阻塞的线程继续执行。

Dev-C 4.9.9.2编译错误及解决方案在Windows11系统使用Dev-C 4.9.9.2编译程序时,编译器记录窗格可能会显示以下错误信息:gcc.exe:internalerror:aborted(programcollect2)pleasesubmitafullbugreport.seeforinstructions.尽管最终显示“编译成功”,但实际程序无法运行,并弹出“原始码档案无法编译”错误提示。这通常是因为链接器collect

C 适合系统编程和硬件交互,因为它提供了接近硬件的控制能力和面向对象编程的强大特性。1)C 通过指针、内存管理和位操作等低级特性,实现高效的系统级操作。2)硬件交互通过设备驱动程序实现,C 可以编写这些驱动程序,处理与硬件设备的通信。
