以下代码中显示了二叉树的链式存储以及先序遍历递归建树,后序遍历释放资源,复制一棵二叉树,先序、中序、后序遍历的递归以及非递归实现,求叶子结点数量的递归以及非递归函数,求非叶子结点的递归以及非递归函数。求深度的递归函数。
文件输入,文件中的内容是
1 2 4 0 0 5 6 0 0 0 3 7 0 0 8 0 0 1 2 3 4 5 6 0 0 0 0 0 0 0
构建的两棵二叉树为:
所有代码如下:
#include<iostream> #include<queue> #include<stack> using namespace std; #define maxn 1000 //二叉树结点定义 struct BiTNode{ int data; BiTNode* lchild; BiTNode* rchild; BiTNode():data(-1),lchild(NULL),rchild(NULL){} BiTNode(int data,BiTNode* l,BiTNode* r):data(data),lchild(l),rchild(r){} }; class BinaryTree{ private: BiTNode *bt;//根节点指针 int RCreate(BiTNode *p,int k,int end); int PreTraverse(BiTNode *p); int InTraverse(BiTNode *p); int PostTraverse(BiTNode *p); public: BinaryTree(){bt=NULL;}//构造函数,构造空树 ~BinaryTree();//利用后序遍历销毁二叉树 void release(BiTNode* p); bool compare(BiTNode* t1,BiTNode* t2);//使用后序遍历查看判断两个二叉树是否相等 void CreateBiTree(int end);//创建二叉树,其中end为空指针域标志 BiTNode* copy(BiTNode* p);//复制二叉树并且返回树根 void PreOrderTraverse(); void InOrderTraverse(); void PostOrderTraverse(); void PreOrder();//非递归 void InOrder(); void PostOrder(); BiTNode* GetRoot();//二叉树不为空时返回的是根节点指针,否则为NULL void SetRoot(BiTNode* rt); void BiTreeDisplay(BiTNode *bt,int level = 1);//树形显示算法 int LeaveCount(BiTNode* p);//通过递归方法求叶子结点的数量 int LeaveCount2();//通过广度优先搜索(非递归方法)对叶子结点的数量进行计数 int NonLeave(BiTNode* p); //递归求解非叶子结点的数量 int NonLeave2();//非递归求解非叶子结点的数量 int getDepth(BiTNode* p); }; //递归构造左子树或者右子树 int BinaryTree::NonLeave(BiTNode* p){ if(p==NULL)return 0; else if(p->lchild==NULL&&p->rchild==NULL)return 0; else return NonLeave(p->lchild)+NonLeave(p->rchild)+1; } int BinaryTree::NonLeave2(){ queue<BiTNode*> q; BiTNode* p = this->bt; if(!p)return 0; q.push(p); int count = 0; while(!q.empty()){ BiTNode* cur = q.front(); q.pop(); if(cur->lchild==NULL&&cur->rchild==NULL)count+=0; else if(cur->lchild==NULL&&cur->rchild!=NULL)count++,q.push(cur->rchild); else if(cur->lchild!=NULL&&cur->rchild==NULL)count++,q.push(cur->lchild); else count++,q.push(cur->lchild),q.push(cur->rchild); } return count; } void BinaryTree::release(BiTNode* p){ if(p){ release(p->lchild); release(p->rchild); delete p; } } BinaryTree::~BinaryTree(){ release(bt); } int BinaryTree::RCreate(BiTNode* p,int k,int end){ BiTNode *q; int e; cin>>e; if(e!=end)//空指针标记 { q = new BiTNode; q->data=e; q->lchild=NULL; q->rchild=NULL; if(k==1)p->lchild=q; if(k==2)p->rchild=q; RCreate(q,1,end);//递归构造左子树 RCreate(q,2,end);//递归构造右子树 } return 0; } void BinaryTree::CreateBiTree(int end){ cout<<"请按先序序列的顺序输出二叉树,0为空指针域标志:"<<endl; BiTNode *p; int e; cin>>e; if(e==end)return;//输入根节点就是结束标志,空树 p = new BiTNode; if(!p){ cout<<"申请内存失败!"<<endl; exit(-1); } p->data=e; p->lchild=NULL; p->rchild=NULL; bt=p;//设置根结点 RCreate(p,1,end);//构建左子树 RCreate(p,2,end);//构建右子树 } void BinaryTree::BiTreeDisplay(BiTNode* bt,int level){ if(bt){ BiTreeDisplay(bt->rchild,level+1); cout<<endl; for(int i=0;i<level-1;i++)cout<<" "; cout<<bt->data; BiTreeDisplay(bt->lchild,level+1); } } BiTNode* BinaryTree::GetRoot(){ return this->bt; } void BinaryTree::SetRoot(BiTNode* rt){ this->bt=rt; } int BinaryTree::PreTraverse(BiTNode* p){ if(p){ cout<<p->data<<" "; PreTraverse(p->lchild); PreTraverse(p->rchild); } return 0; } void BinaryTree::PreOrderTraverse(){ PreTraverse(bt); } void BinaryTree::InOrderTraverse(){ InTraverse(bt); } void BinaryTree::PostOrderTraverse(){ PostTraverse(bt); } int BinaryTree::InTraverse(BiTNode* p){ if(p){ InTraverse(p->lchild); cout<<p->data<<" "; InTraverse(p->rchild); } } int BinaryTree::PostTraverse(BiTNode* p){ if(p){ PostTraverse(p->lchild); PostTraverse(p->rchild); cout<<p->data<<" "; } } int BinaryTree::LeaveCount(BiTNode* p){ if(p==NULL)return 0; else if(p->lchild==NULL && p->rchild==NULL) { return 1; } else return LeaveCount(p->lchild)+LeaveCount(p->rchild); } int BinaryTree::LeaveCount2(){ BiTNode* p = bt; int ret = 0; if(p==NULL)return ret; queue<BiTNode*> q; q.push(p); while(!q.empty()){ BiTNode* cur = q.front(); q.pop(); if(cur->lchild==NULL&&cur->rchild==NULL)ret++; else if(cur->lchild==NULL&&cur->rchild!=NULL)q.push(cur->rchild); else if(cur->lchild!=NULL&&cur->rchild==NULL)q.push(cur->lchild); else q.push(cur->lchild),q.push(cur->rchild); } return ret; } void BinaryTree::PreOrder(){ stack<BiTNode*> sk; BiTNode* p = bt; while(p || !sk.empty()){ if(p){ cout<<p->data<<" "; if(p->rchild)sk.push(p); p=p->lchild; } else { p=sk.top(); sk.pop(); p=p->rchild; } } } void BinaryTree::InOrder(){ stack<BiTNode*> sk; BiTNode* p = bt; while(p || !sk.empty()){ if(p){ sk.push(p); p=p->lchild; } else{ p=sk.top(); sk.pop(); cout<<p->data<<" "; p=p->rchild; } } } struct BiTNode1{//用于非递归后序遍历 BiTNode* bt; int tag;//标记,为1则访问左子树,为2则访问右子树 }; void BinaryTree::PostOrder(){ stack<BiTNode1*> sk; BiTNode* p = bt; while(p || !sk.empty()){ if(p){ BiTNode1* tmp = new BiTNode1; tmp->bt=p; tmp->tag=1; sk.push(tmp); p=p->lchild;//找到最左下角的结点 } else{//左子树为空时回溯到当前结点向右子树深入 BiTNode1* tmp = sk.top(); sk.pop(); if(tmp->tag==1){//第一次回溯到该结点,继续向右子树深入 tmp->tag=2; sk.push(tmp); p=tmp->bt->rchild; }else{ cout<<tmp->bt->data<<" "; p=NULL;//该结点之后的结点都已经输出,不用考虑 } } } } int BinaryTree::getDepth(BiTNode* p){ if(p==NULL)return 0; else if(p->lchild==NULL&&p->rchild==NULL)return 1; else return max(getDepth(p->lchild),getDepth(p->rchild))+1; } bool BinaryTree::compare(BiTNode* t1,BiTNode* t2){ if(t1==NULL&&t2==NULL)return true; else if (t1==NULL || t2==NULL)return false; else if ((t1->data)==(t2->data) && compare(t1->lchild,t2->lchild) && compare(t1->rchild,t2->rchild))return true; return false; } BiTNode* BinaryTree::copy(BiTNode* p){ if(!p)return NULL; BiTNode *ltr,*rtr; if(p->lchild==NULL)ltr = NULL; else ltr = copy(p->lchild); if(p->rchild==NULL)rtr = NULL; else rtr = copy(p->rchild); return new BiTNode(p->data,ltr,rtr); } int main(){ freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); BinaryTree BT; BT.CreateBiTree(0); // BT.BiTreeDisplay(BT.GetRoot()); //输出二叉树的先序、中序、后序遍历 ,分别是递归与非递归的实现 cout<<"递归先序遍历二叉树:"; BT.PreOrderTraverse(); cout<<endl<<"非递归先序遍历二叉树:"; BT.PreOrder(); cout<<endl<<"递归中序遍历二叉树:"; BT.InOrderTraverse(); cout<<endl<<"非递归中序遍历二叉树:"; BT.InOrder(); cout<<endl<<"递归后序遍历二叉树:"; BT.PostOrderTraverse(); cout<<endl<<"非递归后序遍历二叉树:"; BT.PostOrder(); cout<<endl; cout<<"递归求解二叉树的叶子结点的数量:"<< BT.LeaveCount(BT.GetRoot())<<endl; cout<<"非递归求解二叉树的叶子结点的数量:"<< BT.LeaveCount2()<<endl; cout<<"递归求解二叉树的非叶子结点的数量:"<<BT.NonLeave(BT.GetRoot())<<endl; cout<<"非递归求解二叉树的非叶子结点的数量:"<<BT.NonLeave2()<<endl; cout<<"递归求解二叉树的深度:"<<BT.getDepth(BT.GetRoot())<<endl; cout<<"########################################"<<endl; // if(BT.compare(BT.GetRoot(),BT2.GetRoot()))cout<<"两棵二叉树相同"<<endl; // else cout<<"两棵二叉树不同"<<endl; // BinaryTree BT3; // BT3.SetRoot(BT2.copy(BT2.GetRoot())); // if(BT3.compare(BT3.GetRoot(),BT2.GetRoot()))cout<<"BT3&BT2相同"<<endl; }
原文链接: https://www.cnblogs.com/randy-lo/p/13053346.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/353315
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!