寒假集训——二叉树

本文主要是介绍寒假集训——二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;typedef struct node
{char date;node *lch,*rch;
}Bn,*Bt;
void cbtree(Bt &T)//先序建二叉树
{char c;scanf("%c",&c);if(c==',')T=NULL;else{T=new Bn;T->date=c;cbtree(T->lch);cbtree(T->rch);}return ;
}
void pre(Bt T)//先序遍历二叉树
{if(T){printf("%c",T->date);pre(T->lch);pre(T->rch);}
}
void in(Bt T)//中序遍历二叉树
{if(T){in(T->lch);printf("%c",T->date);in(T->rch);}
}
void post(Bt T)//后序遍历二叉树
{if(T){post(T->lch);post(T->rch);printf("%c",T->date);}
}
void level(Bt T)//层次遍历二叉树
{queue<Bn>Q;Q.push(*T);while(!Q.empty()){Bn next=Q.front();Q.pop();printf("%c",next.date);if(next.lch)Q.push(*(next.lch));if(next.rch)Q.push(*(next.rch));}
}
int cnt=0;
void cntleaf1(Bt T)//求叶子节点
{if(T){if(!T->lch&&!T->rch){cnt++;return;}cntleaf1(T->lch);cntleaf1(T->rch);}
}
int cntleaf2(Bt T)//求叶子节点
{if(!T)return 0;if(!T->lch&&!T->rch)return 1;else{int nl=cntleaf2(T->lch);int nr=cntleaf2(T->rch);return nl+nr;}
}
int dep(Bt T)//求二叉树的深度
{int ddep=0;if(!T) return ddep;int nl=dep(T->lch);int nr=dep(T->rch);return (nl>nr?nl:nr)+1;
}
int main()
{Bt head;//先序建二叉树cbtree(head);//先序遍历二叉树pre(head);printf("\n");//中序遍历二叉树in(head);printf("\n");//后序遍历二叉树post(head);printf("\n");//层次遍历二叉树level(head);printf("\n");//求二叉树的叶子节点cntleaf1(head);printf("%d\n",cnt);printf("%d\n",cntleaf2(head));//求二叉树深度printf("%d\n",dep(head));
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;typedef struct node
{char date;node *lch,*rch;
}Bn,*Bt;
char pre[1000],ins[1000],post[1000];
void cbtree1(Bt &T,char *pre,char *ins,int n)//根据先序和中序建立二叉树
{if(n<=0)T=NULL;else{int k=strchr(ins,pre[0])-ins;T=new Bn;T->date=pre[0];cbtree1(T->lch,pre+1,ins,k);cbtree1(T->rch,pre+k+1,ins+k+1,n-k-1);}
}
void cbtree2(Bt &T,char *ins,char *post,int n)//根据中序和后序建立二叉树
{if(n<=0)T=NULL;else{int k=strchr(ins,post[n-1])-ins;T=new Bn;T->date=post[n-1];cbtree2(T->lch,ins,post,k);cbtree2(T->rch,ins+k+1,post+k,n-k-1);}
}
void preorder(Bt &T)//先序遍历二叉树
{if(T){printf("%c",T->date);preorder(T->lch);preorder(T->rch);}
}
void postorder(Bt &T)//后序遍历二叉树
{if(T){postorder(T->lch);postorder(T->rch);printf("%c",T->date);}
}
int main()
{Bt head;scanf("%s%s",pre,ins);//先序和中序cbtree1(head,pre,ins,strlen(pre));postorder(head);//scanf("%s%s",ins,post);//中序和后序//cbtree2(head,ins,post,strlen(post));//preorder(head);
}

这篇关于寒假集训——二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---