二叉树机试模板

二叉树建立与各种排序模板
1.根据前序和空值建立二叉树排序

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    char data;
    struct node *lchlid,*rchlid;
}*BitTree;
int len;
string s;
void CreateBitTree(BitTree &T){
    if(len == s.length())
        return;
    char c = s[len];
    len++;
    if(c == '0') T = NULL;
    else{
        T = new node;
        T -> data = c;
        // 模拟删除操作
        T -> lchlid = NULL;
        T -> rchlid = NULL;
        CreateBitTree(T -> lchlid);
        CreateBitTree(T -> rchlid);
    }
}
void PreOrderTraverse(BitTree T){
    if(T != NULL){
        cout<<T->data<<" ";
        PreOrderTraverse(T ->lchlid);
        PreOrderTraverse(T -> rchlid);
    }
}
void InOrderTraverse(BitTree T){
    if(T != NULL){
        InOrderTraverse(T -> lchlid);
        cout<<T -> data<<" ";
        InOrderTraverse(T -> rchlid);
    }
}
void PostOrderTraverse(BitTree T){
    if(T != NULL){
        PostOrderTraverse(T -> lchlid);
        PostOrderTraverse(T -> rchlid);
        cout<< T ->data<<" ";
    }
}
int Leaf(BitTree T){
    if(T == NULL) return 0;
    if(T -> lchlid == NULL && T -> rchlid == NULL)return 1;
    return Leaf(T ->lchlid) + Leaf(T ->rchlid);
}
int Deepth(BitTree T){
    if(T == NULL) return 0;
    int x = Deepth(T->lchlid);
    int y = Deepth(T->rchlid);
    return max(x,y)+1;
}
string new_string(string a){
    //删除字符串中的空格
    string b = "";
    int len = a.length();
    for(int i = 0;i < len;i++){
        if(a[i] != ' ')
            b += a[i];
    }
    return  b;
}
int main(){
    while (getline(cin,s)){
        s = new_string(s);
        len = 0;
        BitTree T;
        CreateBitTree(T);
        PreOrderTraverse(T);cout<<endl;
        InOrderTraverse(T);cout<<endl;
        PostOrderTraverse(T);cout<<endl;
        cout<<Leaf(T)<<endl;
    }
    return 0;
}

2.根据前序+中序确定二叉树（思想就是按照顺序将左右孩子和根分出来）

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    char data;
    struct node *lchlid,*rchlid;
}*BitTree;
void CreateBitTree(BitTree &T,string pre,string in,int size){
    if(size <= 0)
        return;
    T = new node;
    T -> data = pre[0];
    // 模拟删除操作
    T -> lchlid = NULL;
    T -> rchlid = NULL;
    //记录根节点
    char root = pre[0];
    int i;
    for(i = 0;i < size;i++){
        if(root == in[i])
            break;
    }
    string preLeft = pre.substr(1,i);
    string preRight = pre.substr(i+1,size-1-i);
    string inLeft = in.substr(0,i);
    string inRight = in.substr(i+1,size-1-i);
    CreateBitTree(T -> lchlid,preLeft,inLeft,i);
    CreateBitTree(T -> rchlid,preRight,inRight,size - i - 1);

}
void PreOrderTraverse(BitTree T){
    if(T != NULL){
        cout<<T->data;
        PreOrderTraverse(T ->lchlid);
        PreOrderTraverse(T -> rchlid);
    }
}
void InOrderTraverse(BitTree T){
    if(T != NULL){
        InOrderTraverse(T -> lchlid);
        cout<<T -> data;
        InOrderTraverse(T -> rchlid);
    }
}
void PostOrderTraverse(BitTree T){
    if(T != NULL){
        PostOrderTraverse(T -> lchlid);
        PostOrderTraverse(T -> rchlid);
        cout<< T ->data;
    }
}
string new_string(string a){
    string b = "";
    int len = a.length();
    for(int i = 0;i < len;i++){
        if(a[i] != ' ')
            b += a[i];
    }
    return  b;
}
int main(){
    string pre,in;
    while (getline(cin,pre)){
        getline(cin,in);
        pre = new_string(pre);
        in = new_string(in);
        BitTree T;
        CreateBitTree(T,pre,in,in.size());
        PreOrderTraverse(T);
        cout<<endl;
        InOrderTraverse(T);
        cout<<endl;
        PostOrderTraverse(T);
        cout<<endl;
    }
    return 0;
}

3.二叉排序树

#include<bits/stdc++.h>
using namespace std;
typedef struct node{
    int data;
    struct node *lchild,*rchild;
}*BiTree;

void createTree(BiTree &T,int x)
{
    if(T==NULL)
    {
        T=new node;
        T->data=x;
        T->lchild=NULL;
        T->rchild=NULL;
        return;
    }
    if(x==T->data)
    {
        return;
    }
    else if(x<T->data)
    {
        createTree(T->lchild,x);
    }
    else
    {
        createTree(T->rchild,x);
    }
}

//先序遍历
void pre(BiTree T)
{
    if(T!=NULL)
    {
        cout<<T->data<<" ";
        pre(T->lchild);
        pre(T->rchild);
    }
}
//中序遍历
void mid(BiTree T)
{
    if(T!=NULL)
    {
        mid(T->lchild);
        cout<<T->data<<" ";
        mid(T->rchild);
    }
}
//后序遍历
void las(BiTree T)
{
    if(T!=NULL)
    {
        las(T->lchild);
        las(T->rchild);
        cout<<T->data<<" ";
    }
}

int main()
{
    int n,x;
    while(cin>>n)
    {
        BiTree T=NULL;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            createTree(T,x);
        }
        pre(T);
        cout<<endl;
        mid(T);
        cout<<endl;
        las(T);
        cout<<endl;
    }
    return 0;
}

4.判断两颗二叉树是否相同

bool isSame(BitTree T1, BitTree T2){
    if (!T1&&!T2)
        return true;
    else if (T1&&T2){
        if (T1->data == T2->data)
            return isSame(T1->lchlid, T2->lchlid) && isSame(T1->rchlid, T2->rchlid);
        else
            return false;
    }
    else
        return false;
}

完全二叉树结点个数

int NodeCountOfBiTree ( BiTree T)
{
    if(T == NULL)
        return 0;
    else
        return 1 + NodeCountOfBiTree(T->lchild) + NodeCountOfBiTree(T->rchild);
}