c++先序二叉树的构建详解

发布时间:2020-03-09 18:44:48发布者:admin浏览数:

二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层)

第一、定义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

最终测试运行截图

  程序开发分类
程序开发 |  系统教程 |  软件应用 |  图形图像 |  网络应用 |  站长教程 |  网站建设 |  视频教程 |  硬件维护 |  IT资讯 |  中国it动力网
本站发布的系统与软件仅为个人学习测试使用,请在下载后24小时内删除,不得用于任何商业用途,否则后果自负,请支持购买微软正版软件!
如侵犯到您的权益,请及时通知我们,我们会及时处理。
Copyright @ 2019 中国it动力网 网站导航