这个二叉树啊，挺绕的，还有后面的平衡二叉树，都是需要画图来辅助的，废话少说，直接讲知识。
首先，为什么要建立这个二叉树呢，是因为二叉树能够进行有效的查找，避免重复查找和无用查找。具体操作先将所有的数或者字符全部以树的形式建立起来，然后在找数或者找字符时按照数的构造来找。建树的第一步是建立根，找到根后，然后再建立左子树和右子树。然后在去找下一个根然后一直这样下去。再说一下遍历的种类：前序（先序），中序，后序，层序遍历。
最基本的问题是首先把数建立起来，一般是中序和前序推后序和层序，或者中序和后序退前序或者层序，前序或者中序或者后续带着空节点来建树（节点数，叶子数）。
代码如下：
//给前序和空节点输出中序，后序，层次
#include<bits/stdc++.h> using namespace std; char a[10000]; int l1; struct node { char data; struct node *rchild,*lchild; }; struct node *creat() { struct node *root; char c; c=a[l1++]; if(c==',') return NULL; else root=new node; root->data=c; root->lchild=creat(); root->rchild=creat(); return root; };//建树 void qianxu(struct node *root) { if(root) { cout<<root->data; qianxu(root->lchild); qianxu(root->rchild); }//前序遍历 } void zhongxu(struct node *root) { if(root) { qianxu(root->lchild); cout<<root->data; qianxu(root->rchild); } }//中序遍历 void houxu(struct node *root) { if(root) { houxu(root->lchild); houxu(root->rchild); cout<<root->data; } }//后序遍历 void cengxu(struct node *root) { queue<struct node *>q; q.push(root); struct node *tmp=new node; while(!q.empty()) { tmp=q.front(); q.pop(); if(tmp) { cout<<tmp->data; q.push(tmp->lchild); q.push(tmp->rchild); } } }//层次遍历 int main() { cin>>a; int len=strlen(a); struct node *root=NULL; l1=0; root=new node; root=creat(); qianxu(root); cout<<endl; zhongxu(root); cout<<endl; houxu(root); cout<<endl; cengxu(root); cout<<endl; return 0;
}
由于前面已经将各种排序的方法已经给出（在建好树的前提下），下面讲一下如何通过前序和中序，后序和中序来建一个
二叉树。
#include<bits/stdc++.h>//前序和中序建树（主要就是观察前序和中序的特点，先把根找出来，然后逐次低减下去） using namespace std; char str1[1000],str2[1000]; struct node { char data; struct node *rchild,*lchild; }; struct node *creat(int n,char *str1,char *str2)//指针的变化 if(n==0) return NULL: struct node *root; else root=new node; root->data=str1[0]; //以前序为模板 int i; for(i=0;i<n;i++) { if(str2[i]==str1[0]) break; } root->lchild=creat(i,str1+1,str2);//左子树 root->rchild=creat(n-i-1,str1+i+1,str2+i+1);//右子树
};
#include<bits/stdc++.h>//后序和中序建树和推前序（以中序为主心骨，后序作比较） using namespace std; char str1[100],str2[100]; struct node { char data; struct node *rchild,*lchild; }; struct node *creat(int s1,int t1,int s2,int t2) { struct node *root; int i; for(i=s1;i<=t1;i++) { if(str1[i]==str2[t2]) break; } if(i<=t1) { root=new node; root->data=str2[t2]; root->lchild=creat(s1,i-1,s2,s2+i-s1-1); root->rchild=creat(i+1,t1,s2+i-s1,t2-1); return root; } else return NULL; return root; }; void f(struct node *root) { if(root) { cout<<root->data; f(root->lchild); f(root->rchild); } }//输出前序 int main() { cin>>str1>>str2; int n=strlen(str1); struct node *root; root=new node; root=creat(0,n-1,0,n-1); f(root); return 0;
}
还有一个知识点就是求叶子数和根的个数以及求深度
#include<bits/stdc++.h>//建造好树的前提下，求叶子数，如果是求根的个数，稍微改一下就行了（叶子的左右节点都为空，根的左右节点至少有一个不为空） using namespace std; int l1=0; void f(struct node *root) { if(root==NULL) return NULL; else if(root->rchild==NULL&&root->lchild==NULL) return 1; else return f(root->rchild)+f(root->lchild); }
如果是求深度或者高度类似，用递归
#include<bits/stdc++.h> using namespace std; int l1=0; void f(struct node *root) { if(root) { int l1=deep(root->lchild); int l2=deep(root->rchild); in d; d=l1>l2?l1+1:l2+1; } return d; }
在这里要区分一下二叉树的高度和深度。高度，是从下往上开始数，到达目标节点的最短高度
深度，是从根节点往下开始数。感觉代码差不多，哈哈哈，自己慢慢领悟吧，我就不多说了。
