三种建树， 三种遍历 高度，深度 叶子树 结点数 中序线索化 线索化遍历 二叉排序树
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10; typedef struct Tre{ char data; Tre *l; Tre *r; int lt; int rt; }; typedef struct Tre_int{ int data; Tre_int *l; Tre_int *r; int lt; int rt; }; void pre_c_Tre(Tre *&root){ char c; cin>>c; if(c!='#'){ root=(Tre *)malloc(sizeof(Tre)); root->data=c; pre_c_Tre(root->l); pre_c_Tre(root->r); }else{ root=NULL; } } void in_c_Tre(Tre *&root){ char c; cin>>c; if(c!='#'){ root=(Tre *)malloc(sizeof(Tre)); pre_c_Tre(root->l); root->data=c; pre_c_Tre(root->r); }else{ root=NULL; } } void af_c_Tre(Tre *&root){ char c; cin>>c; if(c!='#'){ root=(Tre *)malloc(sizeof(Tre)); pre_c_Tre(root->l); pre_c_Tre(root->r); root->data=c; }else{ root=NULL; } } void pre_tra(Tre *root){ if(root!=NULL){ cout<<root->data<<" "; pre_tra(root->l); pre_tra(root->r); } } void in_tra(Tre *root){ if(root!=NULL){ pre_tra(root->l); cout<<root->data<<" "; pre_tra(root->r); } } void af_tra(Tre *root){ if(root!=NULL){ pre_tra(root->l); pre_tra(root->r); cout<<root->data<<" "; } } void th2(Tre *& pre, Tre*& root){ if(root!=NULL){ th2(pre,root->l); if(root->l==NULL ){ root->l=pre; root->lt=1; } if(pre!=NULL && pre->r==NULL ){ pre->r=root; pre->rt=1; } pre=root; th2(pre,root->r); } } void th(Tre* &root){ Tre *pre=NULL; if(root!=NULL){ th2(pre,root); pre->r=NULL; pre->rt=1; } } Tre * find_first(Tre * root){ while(root->lt!=1) root=root->l; return root; } Tre * find_next(Tre * root){ if(root->rt==1){ return root->r; }else{ return find_first(root->r); } } void t(Tre * root){ for(Tre *rr=find_first(root);rr!=NULL;rr=find_next(rr)){ cout<<rr->data<<" "; } } int nodes(Tre * root){ if(root!=NULL){ return nodes(root->l)+nodes(root->r)+1; }else{ return 0; } } void leaf(Tre * root, int &cnt){ if(root->l==NULL && root->r==NULL){ cnt++; }else{ leaf(root->l,cnt); leaf(root->r,cnt); } } int depth(Tre *root){ if(root!=NULL){ return max(depth(root->l),depth(root->r))+1; }else{ return 0; } } void insert(Tre_int * &root, int c){ if(root!=NULL){ if(c==root->data){ return; }else if(c>root->data){ insert(root->r,c); }else if(c<root->data){ insert(root->l,c); } }else{ root=(Tre_int*)malloc(sizeof(Tre_int)); root->data=c; } } void b_sort_tre(Tre_int * &root, int *s, int n){ for(int i=0;i<n;i++){ insert(root,s[i]); } } void bst_tra(Tre_int *root){ if(root!=NULL){ bst_tra(root->l); cout<<root->data<<" "; bst_tra(root->r); } } int main(){ int cnt=0; Tre *r=NULL; Tre_int *r_int=NULL; af_c_Tre(r); pre_tra(r); cout<<endl; in_tra(r); cout<<endl; af_tra(r); cout<<endl; leaf(r,cnt); cout<<nodes(r)<<endl; cout<<cnt<<endl; cout<<depth(r)<<endl; th(r); t(r); cout<<endl; int a[5]={6,8,9,1,2}; b_sort_tre(r_int,a,5); bst_tra(r_int); return 0; }