写一颗二叉树-适合初学者

（有任何问题欢迎留言或私聊 本文目的旨在给初学二叉树的朋友提供一个借鉴的模板：一个是指针版本，一个非指针版本。 在文末推荐几道经典例题、我的题解和经典博客，供大家学习。 已经了解二叉树的同学可以直接去看最下面的一些经典题目。点击左侧目录即可。 二叉树的很多相关定义在百度百科或者他人博客上都有，建议先看一下。

引入：

 一个二叉树如下： 前序遍历： ABDHIEJCFG 中序遍历： HDIBJEAFCG 后序遍历： HIDJEBFGCA 层序遍历： ABCDEFGHIJ 特点：  1. 前序遍历中，根节点在第一位；后序遍历中，根节点在最后一位；  2. 中序遍历中，根节点的左右子树分别在根节点位置两边；

非指针版本：

//DFS遍历二叉树 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1005; const int INF = 0x3f3f3f3f; const LL mod = 1000000007; const double eps = 1e-8; struct BinaryTree{ int val; int l; int r; BinaryTree(){val=0;l=r=-1;} }tree[N]; int ar[N],ans[N],n,tot,t; int pre[N],jing[N]; //递归建树，k为当前建树已经跑到了输入序列数组的第几号元素 void build(int k){ if(k>n)return; tree[++tot].val=ar[k]; tree[tot].l=tree[tot].r=-1; int i=1;//从根节点往下分析此节点的位置情况 while(1){ if(ar[k]<tree[i].val){//比此节点的值小，就往左跑 if(tree[i].l!=-1){ i=tree[i].l; }else{//如果此节点没有左儿子，就让k号元素当它左儿子，break tree[i].l=tot; break; } }else {//反之往右跑 if(tree[i].r!=-1){ i=tree[i].r; }else{ tree[i].r=tot; break; } } } build(k+1); return; } //二叉搜索树前序遍历的序列 void get_pre(int k){ pre[++t]=tree[k].val; if(tree[k].l!=-1)get_pre(tree[k].l); if(tree[k].r!=-1)get_pre(tree[k].r); return; } //镜像二叉搜索树前序遍历的序列 void get_jing(int k){ jing[++t]=tree[k].val; if(tree[k].r!=-1)get_jing(tree[k].r); if(tree[k].l!=-1)get_jing(tree[k].l); return; } //二叉搜索树中序遍历的结果 void get_mid(int k){ if(tree[k].l!=-1)get_mid(tree[k].l); ans[++t]=tree[k].val; if(tree[k].r!=-1)get_mid(tree[k].r); } //镜像二叉搜索树中序遍历的结果 void get_mid2(int k){ if(tree[k].r!=-1)get_mid2(tree[k].r); ans[++t]=tree[k].val; if(tree[k].l!=-1)get_mid2(tree[k].l); } //二叉搜索树后序遍历的结果 void get_la(int k){ if(tree[k].l!=-1)get_la(tree[k].l); if(tree[k].r!=-1)get_la(tree[k].r); ans[++t]=tree[k].val; } //镜像二叉树后序遍历的结果 void get_la2(int k){ if(tree[k].r!=-1)get_la2(tree[k].r); if(tree[k].l!=-1)get_la2(tree[k].l); ans[++t]=tree[k].val; } void output(){ for(int i=1;i<=n;++i){ if(i==n)printf("%d\n",ans[i]); else printf("%d ",ans[i]); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&ar[i]); } tot=1; tree[1].val=ar[1]; tree[1].l=tree[1].r=-1; build(2); t=0; get_pre(1); t=0; get_jing(1); return 0; }

指针版本：

//由后序遍历和中序遍历获取层序遍历-BFS #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1005; const int INF = 0x3f3f3f3f; const LL mod = 1000000007; const double eps = 1e-8; typedef struct BinaryTree { int val; BinaryTree* left; BinaryTree* right; BinaryTree(){} BinaryTree(int data) : val(data), left(nullptr), right(nullptr) {} }*tree; int n; int post[N],mid[N],pre[N]; tree build(int k,int *mid,int *post,int inl,int inr){ int i,j; if(k<=0)return nullptr; if(inl>inr)return nullptr; tree p; p=new BinaryTree; p->left=p->right=nullptr; p->val=post[k-1]; for(i=0;i<n;++i){ if(mid[i]==post[k-1])break; } for(j=0;j<n;++j){ //printf("j=%d\n",j); //j=0; if(*mid==mid[j])break; } int l=i-j; p->left=build(l,mid,post,inl,inl+l-1); p->right=build(k-l-1,mid+l+1,post+l,inl+l+1,inr); return p; } void bfs(tree head){ queue<tree>Q; while(!Q.empty())Q.pop(); Q.push(head); int s=0; while(!Q.empty()){ tree u=Q.front();Q.pop(); pre[s++]=u->val; if(u->left!=nullptr)Q.push(u->left); if(u->right!=nullptr)Q.push(u->right); } for(int i=0;i<s;++i){ if(i==s-1)printf("%d\n",pre[i]); else printf("%d ",pre[i]); } } int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&post[i]); } for(int i=0;i<n;++i){ scanf("%d",&mid[i]); } tree root=new BinaryTree; root->left=root->right=nullptr; root=build(n,mid,post,0,n-1); bfs(root); return 0; }

例题：

二叉树：PATL2-004. 这是二叉搜索树吗？ 树的遍历：PATL2-006. 树的遍历 二叉树：PATL2-011. 玩转二叉树 完全二叉树：PATL3-010. 是否完全二叉搜索树 层序遍历例题：数据结构实验之二叉树五：层序遍历

我的题解

推荐博客：

二叉树前中后序遍历，DFS与BFS遍历二叉树 层序遍历讲解

二叉搜索树变双向链表：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1005; const int INF = 0x3f3f3f3f; const LL mod = 1000000007; const double eps = 1e-8; struct binaryTree{ int val; binaryTree* l; binaryTree* r; }cw[N]; typedef binaryTree* bsTree; int ar[N],n; bsTree last,fi; bsTree insert(bsTree cur,int x){ if(cur==nullptr){ cur = new binaryTree; cur->val=x; cur->l=nullptr; cur->r=nullptr; return cur; } if(cur->val>x){ cur->l=insert(cur->l,x); }else if(cur->val<x){ cur->r=insert(cur->r,x); } return cur; } bsTree treeToList(bsTree cur){ if(cur->l!=nullptr){ treeToList(cur->l); } if(last==nullptr){ last=cur; fi=cur; }else{ last->r=cur; last=cur; } if(cur->r!=nullptr){ treeToList(cur->r); } return fi; } void outTree(bsTree cur){ if(cur==nullptr){ return; } outTree(cur->l); printf("%d ",cur->val ); outTree(cur->r); } void outList(bsTree cur){ bsTree node = cur; while(node!=nullptr){ printf("%d ",node->val ); node=node->r; } } int main(){ while(~scanf("%d",&n)){ bsTree tree = nullptr; last=fi=nullptr; for(int i=1;i<=n;++i){ scanf("%d",&ar[i]); tree=insert(tree,ar[i]); } outTree(tree); printf("\n"); tree=treeToList(tree); printf("%d\n",tree->val ); outList(tree); printf("\n"); } return 0; } /* 8 27 58 3 73 86 49 59 80 */

二叉搜索树查找：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1005; const int INF = 0x3f3f3f3f; const LL mod = 1000000007; const double eps = 1e-8; struct BinaryTree{ int val; int l; int r; BinaryTree(){val=0;l=r=-1;} }tree[N]; int ar[N],n,tot; int flag;//找没找到，找到就为1 //递归建树，k为当前建树已经跑到了输入序列数组的第几号元素 void build(int k){ if(k>n)return; tree[++tot].val=ar[k]; tree[tot].l=tree[tot].r=-1; int i=1;//从根节点往下分析此节点的位置情况 while(1){ if(ar[k]<tree[i].val){//比此节点的值小，就往左跑 if(tree[i].l!=-1){ i=tree[i].l; }else{//如果此节点没有左儿子，就让k号元素当它左儿子，break tree[i].l=tot; break; } }else {//反之往右跑 if(tree[i].r!=-1){ i=tree[i].r; }else{ tree[i].r=tot; break; } } } build(k+1); return; } void fin(int x,int cur){ if(x==tree[cur].val){ flag=1;//找到了 return; }else if(x<tree[cur].val){ fin(x,tree[cur].l); }else fin(x,tree[cur].r); } int main(){ while(~scanf("%d",&n)){ for(int i=1;i<=n;++i){ scanf("%d",&ar[i]); } tot=1; tree[1].val=ar[1]; tree[1].l=tree[1].r=-1; build(2); int x; flag=0; scanf("%d",&x); fin(x,1); if(flag==1)printf("Yes\n"); else printf("No\n"); } return 0; }

哈夫曼树：

#include<iostream> #include<cstring> #include<algorithm> #include<queue> #include<map> using namespace std; const int Max=1e6+5; map<int ,int> mp; int l1,l2; struct node { int date,lson,rson,par,flag; string ans; int cnt; }; node p[Max]; int w[Max]; bool cmp(node a,node b) { return a.date<b.date; } void init(int n) { for(int i=0;i<2*n-1;i++){ p[i].date=0x3f3f3f3f; p[i].flag=0; p[i].par=p[i].lson=p[i].rson=-1; } } void select(int n) { sort(p,p+n,cmp); for(int i=0;i<n;i++) if(!p[i].flag){ l1=i,l2=i+1; p[i].flag=1,p[i+1].flag=1; break; } } void HuffMan(int n) { init(n); for(int i=0;i<n;i++) p[i].date=w[i]; for(int i=n;i<2*n-1;i++){ select(i); p[i].date=p[l1].date+p[l2].date; p[i].lson=l1,p[i].rson=l2; p[l1].par=i,p[l2].par=i; } } void print(int n) { for(int i=0;i<2*n-1;i++){ mp[p[i].date]=i; cout<<i<<" "<<p[i].date<<" "<<p[i].par<<" "<<p[i].lson<<" "<<p[i].rson<<endl; } } void bfs(int n) { queue<node> que; que.push(p[n]); node q; while(!que.empty()){ q=que.front(); que.pop(); if(q.lson!=-1){ p[q.lson].ans=q.ans+'0'; que.push(p[q.lson]); } if(q.rson!=-1){ p[q.rson].ans=q.ans+'1'; que.push(p[q.rson]); } } } int main() { int n,x; cin>>n; for(int i=0;i<n;i++) cin>>w[i]; HuffMan(n); print(n); bfs(2*n-2); while(cin>>x) cout<<p[mp[x]].ans<<endl; }