二叉树BinTree4种遍历及其应用
2024-09-25 15:25:50
前序遍历
template<class T> void BinTree<T>::PreOrder(BinTreeNode<T>*subTree){ //前序遍历以subTree为根的树 if(subTree!=NULL){ cout<<subTree->data<<endl; PreOrder(subTree->leftChild); PreOrder(subTree->rightChild); } }
中序遍历
template<class T> void BinTree<T>::InOrder(BinTreeNode<T>*subTree){ //中序遍历以subTree为根的树 if(subTree!=NULL){//NULL是递归终止条件 InOrder(subTree->leftChild);//中序遍历左子树 cout<<subTree->data<<endl;//访问根结点 InOrder(subTree->rightChild);//中序遍历右子树 } }
后序遍历
template<class T> void BinTree<T>::PostOrder(BinTreeNode<T>*subTree){ //后序遍历以subtree为根的树 if(subTree!=NULL){ PostOrder(subTree->leftChild); PostOrder(subTree->rightChild); cout<<subTree->data<<endl; } }
已知中序排列,和先序排列,可以还原二叉树,并推出后序排列。
已知中序排列,和后序排列,可以还原二叉树,并推出先序排列。
但是已知先序排列和后序排列,可能无法唯一确定二叉树。
层次序遍历,需要用到队列
template<class T> void BinTree<T>::LevelOrder(BinTreeNode<T>*subTree) { //层次序遍历以subTree为根的二叉树 Queue<BinTreeNode<T>*>Q;//定义队列 BinTreeNode<T>*p=subTree; Q.EnQueue(p);//根结点入队 while(!Q.IsEmpty()){//队列不空 Q.DeQueue(p); cout<<p->data; if(p->leftChild!=NULL) Q.EnQueue(p->leftChild);//左子入队 if(p->rightChild!=NULL) Q.EnQueue(p->rightChild);//右子入队 } }
遍历看完后,接下来是遍历的应用以及遍历思想的应用
前序遍历的应用——复制构造函数与复制函数
template<class T> BinTree<T>::BinTree(const BinTree<T>&s){ //复制构造函数 root=Copy(s.root); } template<class T> BinTreeNode<T>* BinTree<T>::Copy(BinTreeNode<T>*orignode){ //返回一个指针,它给出一个以orignode为根的二叉树的副本 if(orignode==NULL) return NULL; BinTreeNode<T>*temp=new BinTreeNode<T>;//创建根结点 temp->data=orignode->data; temp->leftChild=Copy(orignode->leftChild); temp->rightChild=Copy(orignode->rightChild); return temp; }
前序遍历的应用——判断两颗二叉树是否相等
template<class T> bool equal(BinTreeNode<T>*a,BinTreeNode<T>*b){ //为BinTree类的友元函数 if(a==NULL&&b==NULL) return true; if(a!=NULL&&b!=NULL&&a->data==b->data&&equal(a->leftChild,b->leftChild)&&equal(a->rightChild,b->rightChild)) return true; else return false; }
前序遍历的应用——利用前序遍历建立二叉树
约定以输入序列中不可能出现的值作为空结点的值以结束递归,此值在RefValue中,如# template<class T> void BinTree<T>::CreatBinTree(ifstream& in,BinTreeNode<T>*&subTree){ //以递归的方式建立二叉树 T item; if(!in.eof()){//未读完,读入并建树 in>>item; if(item!=RefValue){ subTree->data=item; CreatBinTree(in,subTree->leftChild);//递归建立左子树 CreatBinTree(in,subTree->rightChild);//递归建立右子树 } else subTree=NULL; } }
后序遍历的应用——计算结点的个数
template<class T> int BinTree<T>::Size(BinTreeNode<T>*subTree) const{ //计算以subTree为根的二叉树的结点的个数 ;//递归结束 +Size(subTree->leftChild)+Size(subTree->rightChild); }
后序遍历的应用——计算树的高度
template<class T> int BinTree<T>::Height(BinTreeNode<T>*subTree) const{ //计算以subTree为根的二叉树的高度 ; +max(Height(subTree->leftChild),Height(subTree->rightChild)); }
最新文章
- swing with transformjs
- java.lang.IllegalArgumentException: Illegal character in query at index 261
- Scala入门之函数进阶
- R包介绍
- Android 编程下 Touch 事件的分发和消费机制
- Java IO(一)
- Leetcode_ Best Time to Buy and Sell Stock II
- day23 框架之基础加强
- docker 基础命令
- CentOS安装VirtualBox增强工具
- 高并发解决方案之Actor——第一节
- C语言结构体1.1
- c++多态性---虚函数
- Oracle:WITH AS () Merge ?
- VS2015 IIS Express Web服务器无法启动解决办法
- Python自学:第三章 确定列表长度
- NOIP2018联赛总结
- Js/Jquery 关闭 离开或刷新当前页面时提醒,和执行解绑取消提醒
- java多线程15 :wait()和notify() 的生产者/消费者模式
- ubuntu16.04 安装jdk 错误解决