樹(shù)的性質(zhì)

1.樹(shù)可以沒(méi)有結(jié)點(diǎn)，稱為空樹(shù)；
2.根結(jié)點(diǎn)為第一層；
3.結(jié)點(diǎn)的子樹(shù)棵數(shù)稱為結(jié)點(diǎn)的度，而樹(shù)中結(jié)點(diǎn)的最大的度稱為樹(shù)的度；
4.有n個(gè)結(jié)點(diǎn)的樹(shù)，邊數(shù)一定是n-1，且滿足連通、邊數(shù)等于頂點(diǎn)數(shù)減1的結(jié)構(gòu)一定是一棵樹(shù)；
5.葉子結(jié)點(diǎn)被定義為度為0的結(jié)點(diǎn)，當(dāng)樹(shù)只有一個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)）時(shí)，根結(jié)點(diǎn)也算是葉子結(jié)點(diǎn)；

二叉樹(shù)

1.滿二叉樹(shù)：每一層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了當(dāng)層能達(dá)到的最大結(jié)點(diǎn)數(shù)
2.完全二叉樹(shù)：除了最下面一層之外，其余層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到了當(dāng)層能達(dá)到的最大結(jié)點(diǎn)數(shù)，且最下面一層只從左至右連續(xù)存在若干結(jié)點(diǎn)，而這些連續(xù)結(jié)點(diǎn)右邊的結(jié)點(diǎn)全部不存在。

二叉樹(shù)的遍歷

1.先序遍歷：根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
2.中序遍歷：左子樹(shù)->根結(jié)點(diǎn)->右子樹(shù)
3.后序遍歷：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn)
4.層次遍歷：從根結(jié)點(diǎn)開(kāi)始從上往下逐層遍歷，對(duì)同一層進(jìn)行從左到右的遍歷

給定后序遍歷和中序遍歷，構(gòu)建二叉樹(shù)

#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;
 } 
 
 //當(dāng)前二叉樹(shù)后序序列區(qū)間為[postL,postR],中序序列區(qū)間[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;//左子樹(shù)結(jié)點(diǎn)個(gè)數(shù) 
     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);
         }
     }
 }
 

給定一棵樹(shù)及所有結(jié)點(diǎn)的權(quán)值，求出所有從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑，使得每條路徑上權(quán)值之和等于給定常數(shù)s，依次輸出路徑上的權(quán)值。

#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:結(jié)點(diǎn)數(shù) m:有孩子樹(shù)的結(jié)點(diǎn)數(shù) s:要求的權(quán)值 
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<n;++i){
        scanf("%d",&node[i].weight);//設(shè)置結(jié)點(diǎn)的權(quán)值 
    }
    int id,k;//id:編號(hào) k:孩子數(shù) 
    int child;//孩子編號(hào) 
    //每個(gè)有孩子的結(jié)點(diǎn)
    for(int i=0;i<m;++i){
        scanf("%d%d",&id,&k);//設(shè)置該編號(hào)id的結(jié)點(diǎn)有k個(gè)孩子 
        for(int i=0;i<k;++i){
            scanf("%d",&child);//設(shè)置孩子編號(hào)
            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){
        //當(dāng)前結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)
        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);
        }
    }
}

二叉查找樹(shù)

二叉查找樹(shù)滿足其左子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)域均小于或等于根節(jié)點(diǎn)的數(shù)據(jù)域，右子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)域均大于根節(jié)點(diǎn)的數(shù)據(jù)域。

給出N個(gè)正整數(shù)來(lái)作為一棵二叉排序樹(shù)的結(jié)點(diǎn)插入順序，問(wèn)：這串序列是否是該二叉排序樹(shù)的先序序列或是該二叉排序樹(shù)的鏡像樹(shù)的先序序列，如果是鏡像樹(shù)，輸出yes，并輸出對(duì)應(yīng)的樹(shù)的后序序列，否則輸出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;//結(jié)點(diǎn)個(gè)數(shù) 
    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);
}