二叉树+二叉树搜索树+堆

                                          二叉树

二叉树的几个性质

1在二叉树的第i层最多有2^(i-1)个节点

2深度为k的二叉树最少有k个节点，最多2^k-1个节点

3对于任何一颗非空二叉树，如果其叶子节点数为n0，度为2的非叶子节点个数为n2= n0-1

4具有n个节点的完全二叉树的深度为log(n+1)

5有前序序列和中序序列可以唯一确定一颗二叉树

6如果有n个节点，那么二叉树的不同形态有[1/(n+1)]*[(2n)!/(n!*n!)](这与1...n进栈问有几种出栈顺序相同)

7一棵有n个节点的完全二叉树的第一个非叶子节点的编号为n/2（节点编号1~n）

//1二叉树的结构
struct Tree{
   Tree *L_child;
   Tree *R_child;
   Tree *father;
   int level;//当前节点在第几层
   char value//节点的数据
   Tree(char ch){//构造函数
      L_child = NULL;
      R_child = NULL;
      father = NULL;
      value = ch;
   }
};

//2利用前序序列建立二叉树
//例如"ABC##DE#G##F###",返回根节点
Tree* buildTree(Tree *root){
    char ch;
    cin>>ch;
    if(ch == '#')
      root = NULL;
    else{
      root = new Tree(ch);
      buildTree(root->L_child);
      buildTree(root->R_child);
    }
    return root;
}

//3二叉树的遍历
//前序遍历二叉树
void preOrder(Tree *u){
    if(u != NULL){
      printf("%c" , u->value);
      PreOrder(u->L_child);
      PreOrder(u->R_child);
    }
}

//中序遍历二叉树
void inOrder(Tree *u){
    if(u != NULL){
       inOrder(u->L_child);
       printf("%c" , u->value);
       inOrder(u->R_child);
    }
}

//后序遍历二叉树
void postOrder(Tree *u){
    if(u != NULL){
       postOrder(u->L_child);
       postOrder(u->R_child);
       printf("%c" , u->value);
    }
}

//层次遍历二叉树
void levelOrder(Tree *root){
    queue<Tree*>q;
    q.push(root);
    while(!q.empty()){
        Tree *tmp = q.front();
        q.pop();
        printf("%c" , tmp->value);
        if(tmp->L_child != NULL)
           q.push(tmp->L_child);
        if(tmp->R_child != NULL)
           q.push(tmp->R_child);
    }
}

//4二叉树的计数
//计算二叉树的节点的个数（等于左子树+右子树+根节点）
int size(Tree *root){
   if(root == NULL)
      return 0;
   else
      return 1+size(root->L_child)+size(root->R_child);
}

//计算二叉树的高度(如果二叉树为空那么高度为0，否则高度就是取左右子树中高的那个+根节点)
int high(Tree *root){
   if(root == NULL)
      return 0;
   else{
      int left = high(root->L_child);
      int right = high(root->R_child);
      return left < right ? right+1 : left+1;
   }
}

//5二叉树的复制，返回复制后的根节点
Tree * copy(Tree *root){
   if(root == NULL)
      return NULL;
   Tree *tmpRoot = new Tree(root->value);
   tmpRoot->L_child = copy(root->L_child);
   tmpRoot->R_child = copy(root->R_child);
   return tmpRoot;
}

//6判断两棵二叉树是否相等
bool isEqual(Tree* root1 , Tree *root2){
   if(root1 == NULL && root2 == NULL)
      return true;
   if(root1 != NULL && root２ != NULL && root1->value == root2->value
      &&isEqual(root1->L_child, roo2->L_child)//左子树相等
      &&isEqual(root1->R_child, roo2->R_child)//右子树相等
      )
      return true;
   else
      return false;
}

//7二叉树的重建(节点编号从1~n)
由前序序列和中序序列构造二叉树（len是序列的长度，pre为前序序列 mid为中序序列，返回根节点）
Tree* buildTree(char *pre , char *mid , int len){
   if(!len)
     return NULL;
   int k = 0;
   while(pre[0] != mid[k])//在中序序列找根节点
       k++;
   Tree *root = new Tree(pre[0]);//创建根节点
   root->L_child = buildTree(pre+1 , mid , k);//左边k个元素是左子树的
   root->R_child = buildTree(pre+k+1 , mid+K+1 , len-k-1);//右边len-k-1个元素是右子树的,扣除根节点
   return root;
}

//由中序和后序建立二叉树(len是序列的长度，mid是中序序列，post是后序序列，返回根节点)
Tree* buildTree(char *mid , char *post , int len){
   if(!len)
     return NULL;
   int k = 0;
   while(mid[k] != post[len-1])//在中序序列中找根节点,这里要len-1
       k++;
   Tree *root = new Tree(post[len-1]);
   root->L_child = buildTree(mid , post , k);//左边k个元素是左子树的
   root->R_child = buildTree(mid+k+1 , pos+k , len-k-1);//右边len-k-1个元素是右子树的,扣除根节点
   return root;
}

//8作用：无跟树转化为有根树
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 15;
vector<int>v[MAXN];
int fa[MAXN];

void dfs(int u , int f){
    fa[u] = f;
    int size = v[u].size();//求出和点u相连的点的个数
    for(int i = 0 ; i < size ; i++){
       int tmp = v[u][i];
       if(tmp != f)
          dfs(tmp , u);
    }
}

int main(){
    int n , x , y;
    scanf("%d" , &n);
    for(int i = 0 ; i < n ; i++){
       scanf("%d%d" , &x , &y);
       v[x].push_back(y);
       v[y].push_back(x);
    }
    dfs(1 , -1);//这里举例1为根，我们传人其它的节点作为根节点
    return 0;
}

 

                                                                                         二叉树搜索树

二叉搜索树的性质
1 二叉搜索树可以是一棵空树
2 二叉搜索树的每个节点的值都互不相同
3 二叉搜索树的左子树上的所有节点值都小于根节点的值，右子树上的所有
节点的值都大于根节点的值，左右子树都是二叉搜索树
4 对二叉搜索树进行中序遍历，可以按从小到大排列起来
5 假设有n个节点，那么就有(1/(n+1))*((2n)!/(n!*n!))种可能的二叉搜索树形态
6 在随机情况下具有n个节点的二叉搜索树的插入，删除，搜索的时间复杂度为O(logn)。

//1 二叉搜索树的结构体
struct Tree{
   Tree* L_child;
   Tree* R_child;
   int num;
   Tree(int x){
      num = x;
      L_child = R_child = NULL;
   }
};
Tree* root;//全局变量

//2 建立二叉搜索树
//（做法是假设有n个节点那么插入n次）
void buildTree(int x , Tree *&u){
   if(u == NULL)//建立根节点
      u = new Tree(x);
   else if(u->num == x)//已经有了不用在插入
      return ;
   else if(x < u->num)
      buildTree(x , u->L_child);
   else 
      buildTree(x , u->R_child);
}

//3 二叉搜索树的搜索
bool search(int x , Tree *u){
   if(u == NULL)
     return false;
   else if(u->num == x)
     return true;
   else if(x < u->num)
     return search(x , u->L_child);
   else
     return search(x , u->R_child);
}

//4 二叉搜索树的删除
 //1 假设要删除的节点只有做儿子或右儿子，那么用这个唯一的儿子节点代替该节点，删除之。
 //2 假设要删除的节点有两个儿子节点，那么就是找到右子树中中序下的第一个节点代替该节点，然后删除该节点并递归向下删除
void remove(int x , Tree *u){
    if(u == NULL)
        return;
    else if(x < u->num)
      remove(x , u->L_child);
    else if(x > u->num)
      remove(x , u->R_child);
    else{
      if(u->L_child != NULL && u->R_child != NULL){
        Tree *tmp = u->R_child;
        while(tmp->L_child != NULL)
             tmp = tmp->L_child;
        u->num = tmp->num;
        remove(u->num , u->R_child);
      }
      else{
        Tree *tmp = u;
        if(u->L_child == NULL)
          u = u->R_child;
        else
          u = u->L_child;
        delete tmp;
      }
    }
}

                                             堆

堆的性质

1堆是一棵完全二叉树

2最小堆是指所有的节点都满足根节点的值小于等于左右儿子节点的值，最大堆则是所有的节点都满足根节点的值大于等于左右儿子节点的值

3假设有n个元素的无序序列heap[n]编号从1~n，现在要建一个最小堆。

算法是从第一个非叶子节点开始往上调整即可。

//1 n/2次的调整（每一次内部可能还需从上往下调整） , 因为第一个非叶子节点肯点是n/2
void buildHeap(){
   for(int i = n/2 ; i >= 1 ; i--)
      adjustUp(i,n);
}
//2 从上往下调整
void adjustDown(int num , int size){
   //num是当前要调整的编号，size是堆的最大的元素个数
   int L_child , R_child , min;
   L_child = 2*num , R_child = 2*num+1 , min = num;
   if(L_child <= size && heap[L_child] < heap[min])
      min = L_child;
   if(R_child <= size && heap[R_child] < heap[min])
      min = R_child;
   if(min != num){
      swap(heap[num] , heap[min]);
      adjustDown(min , size);//还要继续向下调整
   }
}
//3 最小堆中插入元素
（做法是先插入最后一个元素的下个位置，然后从下往上调整成最小堆）
（curSize是当前的最后一个元素的下标（1开始），maxSize是最大的元素的个数）
void insert(int x){
   if(curSize == maxSize)   
      return;
   heap[++curSize] = x;
   adjustUp(curSize);
}
//4 从下往上调整
void adjustUp(int num){
   int cur = num;
   int father = cur/2;
   while(cur > 0){
      if(heap[cur] < heap[father]){
         swap(heap[cur] , heap[father]);
         cur = father;
         father = father/2;
      }
      else//如果是根节点比当前点小或相等那么直接返回，因为已经是最小堆     
        return;
   }
}
//5 最小堆中删除最小值（也就是删除根节点）
（做法是把最后一个元素拿到根节点，然后从上往下调整为最小堆）
void removeMin(){
   if(!curSize)//如果没有元素直接返回
      return;
   swap(heap[1] , heap[curSize]);
   curSize--;//把最后一个隔开
   adjustDown(1,curSize);//从上往下调整为最小堆
}
//6 堆排序（如果要使得队列从小到大）
（做法是假设已经是最大堆，那么就是每次取走根节点的值，把最后一个换上去继续调整为最大堆
 那么如果n个元素只要n-1次最后一个就不用了）。
void heapSort(){
   int size = n;
   for(int i = n ; i >= 2 ; i--){
      swap(heap[1] , heap[i]);      
      size--;//说明后面已经排好序了不用管
      adjustDown(1 , size);//只要调整1~size的即可
   }
}