c++中如何构建一个先序二叉树

魁首哥

作者

c++中如何构建一个先序二叉树

这篇文章主要讲解了“c++中如何构建一个先序二叉树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“c++中如何构建一个先序二叉树”吧！

第一、定义BinaryTreeNode 类

#include<iostream>#include<string>#include<queue>usingnamespacestd;template<typenameT>classBinaryTree;template<typenameT>classBinaryTreeNode{public:friendclassBinaryTree<T>;BinaryTreeNode(){data=NULL;lChild=rChild=NULL;}BinaryTreeNode(Tnewdata){this->data=newdata;lChild=rChild=NULL;}TgetData(){returndata;}BinaryTreeNode<T>*getLeftNode(){returnlChild;}BinaryTreeNode<T>*getRightNode(){returnrChild;}Tdata;BinaryTreeNode<T>*lChild;BinaryTreeNode<T>*rChild;private:};

View Code

第二、定义BinaryTree 类

template<typenameT>classBinaryTree{public:BinaryTreeNode<T>*root;char*p;BinaryTree(){root=NULL;}BinaryTree(Tdata){root=newBinaryTreeNode<T>(data);root->lChild=NULL;root->rChild=NULL;}~BinaryTree(){deleteroot;}//构建二叉树并返回BinaryTreeNode<T>*CreateTree(){BinaryTreeNode<int>*bt=NULL;chart;cin>>t;if(t=='#'){returnNULL;}else{intnum=t-'0';bt=newBinaryTreeNode<T>(num);bt->lChild=CreateTree();bt->rChild=CreateTree();}returnbt;}//先序构建二叉树BinaryTreeNode<T>*PreCreateTree(){BinaryTreeNode<int>*bt=NULL;if(this->root==NULL){cout<<"请输入根节点（#代表空树）:";}else{cout<<"请输入节点（#代表空树）:";}chart;cin>>t;if(t=='#'){returnNULL;}else{intnum=t-'0';bt=newBinaryTreeNode<T>(num);if(this->root==NULL){this->root=bt;}cout<<bt->data<<"的左孩子";bt->lChild=PreCreateTree();cout<<bt->data<<"的右边孩子";bt->rChild=PreCreateTree();}returnbt;}voidpreOderTraversal(BinaryTreeNode<T>*bt);//先序遍历voidinOrderTraversal(BinaryTreeNode<T>*bt);//中序遍历voidpostOrderTraversal(BinaryTreeNode<T>*bt);//后序遍历voidlevelTraversal(BinaryTreeNode<T>*bt);//逐层遍历private:};template<typenameT>voidBinaryTree<T>::preOderTraversal(BinaryTreeNode<T>*bt){if(bt){cout<<bt->data;BinaryTree<T>::preOderTraversal(bt->getLeftNode());BinaryTree<T>::preOderTraversal(bt->getRightNode());}}template<typenameT>voidBinaryTree<T>::inOrderTraversal(BinaryTreeNode<T>*bt){if(bt){BinaryTree<T>::inOrderTraversal(bt->getLeftNode());cout<<bt->data;BinaryTree<T>::inOrderTraversal(bt->getRightNode());}}template<typenameT>voidBinaryTree<T>::postOrderTraversal(BinaryTreeNode<T>*bt){if(bt){BinaryTree<T>::postOrderTraversal(bt->getLeftNode());BinaryTree<T>::postOrderTraversal(bt->getRightNode());cout<<bt->data;}}template<typenameT>voidBinaryTree<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"intmain(){//场景测试2BinaryTree<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

最终测试运行截图