本篇文章小编将带大家一起回顾经典c++++之构建先序二叉树，有兴趣的小伙伴一起来复习一下吧！
二叉树首先要解决构建问题，才能考虑后续的遍历，这里贴出通过先序构建二叉树，同时包含四种二叉树的遍历方法（先序，中序，后序，逐层）
第一、定义BinaryTreeNode 类
#include #include #include using namespace std;templateclass BinaryTree;template class BinaryTreeNode {public: friend class BinaryTree; BinaryTreeNode() { data = NULL; lChild = rChild = NULL; } BinaryTreeNode(T newdata) { this->data = newdata; lChild = rChild = NULL; } T getData() { return data; } BinaryTreeNode * getLeftNode() { return lChild; } BinaryTreeNode * getRightNode() { return rChild; } T data; BinaryTreeNode* lChild; BinaryTreeNode* rChild;private:};
View Code
立即学习“C++免费学习笔记（深入）”；
第二、定义BinaryTree 类
template class BinaryTree {public: BinaryTreeNode *root; char* p; BinaryTree() { root = NULL; } BinaryTree(T data) { root = new BinaryTreeNode(data); root->lChild = NULL; root->rChild = NULL; } ~BinaryTree() { delete root; } //构建二叉树并返回 BinaryTreeNode* CreateTree() { BinaryTreeNode* bt = NULL; char t; cin >> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode(num); bt->lChild = CreateTree(); bt->rChild = CreateTree(); } return bt; } //先序构建二叉树 BinaryTreeNode* PreCreateTree() { BinaryTreeNode* bt = NULL; if (this->root == NULL) { cout << "请输入根节点（#代表空树）:"; } else { cout <> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode(num); if (this->root == NULL) { this->root = bt; } cout <data <lChild = PreCreateTree(); cout <data <rChild = PreCreateTree(); } return bt; } void preOderTraversal(BinaryTreeNode *bt); //先序遍历 void inOrderTraversal(BinaryTreeNode *bt); //中序遍历 void postOrderTraversal(BinaryTreeNode *bt);//后序遍历 void levelTraversal(BinaryTreeNode *bt); //逐层遍历private:};template void BinaryTree::preOderTraversal(BinaryTreeNode *bt) { if (bt) { cout <data; BinaryTree::preOderTraversal(bt->getLeftNode()); BinaryTree::preOderTraversal(bt->getRightNode()); }}template void BinaryTree::inOrderTraversal(BinaryTreeNode *bt) { if (bt) { BinaryTree::inOrderTraversal(bt->getLeftNode()); cout <data; BinaryTree::inOrderTraversal(bt->getRightNode()); }}template void BinaryTree::postOrderTraversal(BinaryTreeNode *bt) { if (bt) { BinaryTree::postOrderTraversal(bt->getLeftNode()); BinaryTree::postOrderTraversal(bt->getRightNode()); cout <data; }}template void BinaryTree::levelTraversal(BinaryTreeNode *bt) { queue<BinaryTreeNode*> que; que.push(bt); while (!que.empty()) { BinaryTreeNode* proot = que.front(); que.pop(); cout <data; if (proot->lChild != NULL) { que.push(proot->lChild);//左孩子入队 } if (proot->rChild != NULL) { que.push(proot->rChild);//右孩子入队 } }}
View Code
立即学习“C++免费学习笔记（深入）”；
第三、主程序运行
#include "pch.h"#include #include "BinaryTree.h"int main(){ //场景测试2 BinaryTree 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++++经典例题之先序二叉树的构建的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1433132.html
微信扫一扫 
支付宝扫一扫 
