树的性质

1.树可以没有结点，称为空树；
2.根结点为第一层；
3.结点的子树棵数称为结点的度，而树中结点的最大的度称为树的度；
4.有n个结点的树，边数一定是n-1，且满足连通、边数等于顶点数减1的结构一定是一棵树；
5.叶子结点被定义为度为0的结点，当树只有一个结点（根结点）时，根结点也算是叶子结点；

二叉树

1.满二叉树：每一层的结点个数都达到了当层能达到的最大结点数
2.完全二叉树：除了最下面一层之外，其余层的结点个数都达到了当层能达到的最大结点数，且最下面一层只从左至右连续存在若干结点，而这些连续结点右边的结点全部不存在。

二叉树的遍历

1.先序遍历：根结点->左子树->右子树
2.中序遍历：左子树->根结点->右子树
3.后序遍历：左子树->右子树->根结点
4.层次遍历：从根结点开始从上往下逐层遍历，对同一层进行从左到右的遍历

给定后序遍历和中序遍历，构建二叉树

#include<stdio.h>
#include<stdlib.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
 
using namespace std;
struct node{
    int data;
    struct node* lchild;
    struct node* rchild; 
};
struct node* create(int postL,int postR,int inL,int inR);
void bfs(struct node* root);
int post[100],in[100];
int main()
{
    int n;
    scanf("%d\n",&n);
    for(int i=0;i<n;++i){
        scanf("%d",&post[i]);
    } 
    for(int j=0;j<n;++j){
        scanf("%d",&in[j]);
    } 
    struct node* root=create(0,n-1,0,n-1);
    bfs(root);//层序遍历 
    
    
    return 0;
 } 
 
 //当前二叉树后序序列区间为[postL,postR],中序序列区间[inL,inR] 
 struct node* create(int postL,int postR,int inL,int inR){
    if(postL>postR){
        return NULL;
     }
     struct node* root=new node;
     root->data=post[postR];
     int k;
     for( k=inL;k<=inR;++k){
        if(post[postR]==in[k])
        break;
     }
     
     int numleft=k-inL;//左子树结点个数 
     root->lchild=create(postL,postL+numleft-1,inL,k-1);
     root->rchild=create(postL+numleft,postR-1,k+1,inR); 
    return root;
 }
 
 void bfs(struct node* root){
    queue<node*> q;
    q.push(root);
    while(!(q.empty())){
        struct node* now=q.front();
        q.pop();
        printf("%d",now->data);
        if(now->lchild!=NULL){
            q.push(now->lchild);
         }
         if(now->rchild!=NULL){
            q.push(now->rchild);
         }
     }
 }
 

给定一棵树及所有结点的权值，求出所有从根节点到叶子结点的路径，使得每条路径上权值之和等于给定常数s，依次输出路径上的权值。

#include<cstdio>
#include<algorithm> 
#include<vector>
using namespace std;
struct Node{
    int weight;
    vector<int> child;
}node[110];

void dfs(int index,int numNode,int sum); 
bool cmp(int a,int b){
    return node[a].weight>node[b].weight;
}

int path[110];//保存路径
int n,m,s;//n:结点数 m:有孩子树的结点数 s:要求的权值 
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;++i){
        scanf("%d",&node[i].weight);//设置结点的权值 
    }
    int id,k;//id:编号 k:孩子数 
    int child;//孩子编号 
    //每个有孩子的结点
    for(int i=0;i<m;++i){
        scanf("%d%d",&id,&k);//设置该编号id的结点有k个孩子 
        for(int i=0;i<k;++i){
            scanf("%d",&child);//设置孩子编号
            node[id].child.push_back(child); 
        } 
        sort(node[id].child.begin(),node[id].child.end(),cmp);
    } 
    path[0]=0;
    dfs(0,1,node[0].weight);
    
    return 0;
}

void dfs(int index,int numNode,int sum)
{
    if(sum>s){
        return;
    }
    if(sum==s){
        //当前结点是否为叶子结点
        if(node[index].child.size()!=0){
            return ;
        } 
        for(int i=0;i<numNode;++i){
            printf("%d",node[path[i]].weight);
            if(i<numNode-1){
                printf(" ");
            }
            else{
                printf("\n");
            }
        }
        return ;
    }
    if(sum<s){
        for(int i=0;i<node[index].child.size();++i){
            int child=node[index].child[i];
            path[numNode]=child;
            dfs(child,numNode+1,sum+node[child].weight);
        }
    }
}

二叉查找树

二叉查找树满足其左子树上所有结点的数据域均小于或等于根节点的数据域，右子树上所有结点的数据域均大于根节点的数据域。

给出N个正整数来作为一棵二叉排序树的结点插入顺序，问：这串序列是否是该二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列，如果是镜像树，输出yes，并输出对应的树的后序序列，否则输出no

#include<cstdio>
#include<vector>
using namespace std; 
struct node{
    int data;
    struct node* lchild;
    struct node* rchild;
};
void insert(struct node*& root,int data);
void preOrder(struct node* root,vector<int>& vi);
void postOrder(struct node* root,vector<int>& vi);
void preMorder(struct node* root,vector<int>& vi);
void postMorder(struct node* root,vector<int>& vi);
vector<int> origin,pre,post,preM,postM;
int main(){
    int n,data;//结点个数 
    scanf("%d\n",&n);
    struct node* root=NULL;
    for(int i=0;i<n;++i){
        scanf("%d",&data);
        origin.push_back(data);
        insert(root,data);
    }
    preOrder(root,pre);
    preMorder(root,preM);
    postOrder(root,post);
    postMorder(root,postM);
    if(origin==pre){
        printf("yes\n");
        for(int i=0;i<post.size();++i){
            printf("%d ",post[i]);
        }
    }else if(origin==preM){
        printf("yes\n");
        for(int i=0;i<postM.size();++i){
            printf("%d ",postM[i]);
        }
    }
    else{
        printf("no");
    }
    return 0;
} 

void insert(struct node*& root,int data){
    if(root==NULL){
        root=new node;
        root->data=data;
        root->lchild=NULL;
        root->rchild=NULL;
        return ;
    } 
    if(data<root->data){
        insert(root->lchild,data);
    }
    else{
        insert(root->rchild,data);
    }
}
void preOrder(struct node* root,vector<int>& vi){
    if(root==NULL){
        return ;
    }
    vi.push_back(root->data);
    preOrder(root->lchild,vi);
    preOrder(root->rchild,vi);
}

void postOrder(struct node* root,vector<int>& vi){
    if(root==NULL){
        return ;
    }
    postOrder(root->lchild,vi);
    postOrder(root->rchild,vi);
    vi.push_back(root->data);
}

void preMorder(struct node* root,vector<int>& vi){
    if(root==NULL){
        return ;
    }
    vi.push_back(root->data);
    preMorder(root->rchild,vi);
    preMorder(root->lchild,vi);
    
}

void postMorder(struct node* root,vector<int>& vi){
    if(root==NULL){
        return ;
    }
    postMorder(root->rchild,vi);
    postMorder(root->lchild,vi);
    vi.push_back(root->data);
}