建立二叉树

首先先明确节点结构：

struct node{
  int data;
  node* lchild;
  node* rchild;
};

---

当前二叉树的后序序列区间为[postL,postR],中序序列区间为[inL,inR]:

node* create(int postL,int postR,int inL,int inR){
  if(postL>postR){
    return NULL;  //若后序序列长度小于等于0，则直接返回
  }
  node* root=new node;  //新建一个新的结点，用来存放当前二叉树的根节点
  root->data=post[postR];  //新结点的数据域为根节点的值
  int k;
  for(k=inL;k<=inR;k++){
    if(in[k]==post[postR]){  //在中序序列中找到in[k]==pre[L]的结点
      break;
    }
  }
  int numLeft=k-inL;  //左子树结点数
  //返回左子树的根结点地址，赋值给root的左指针
  root->lchild=create(postL,postL+numLeft-1,inL,k-1);
  //返回右子树的根结点地址，赋值给root的右指针
  root->rchild=create(postL+numLeft,postR-1,k+1,inR);
}

---

当前二叉树的先序序列区间为[preL,preR],中序序列区间为[inL,inR]:

node* create (int preL,int preR,int inL,int inR){
  if(preL>preR){
    return NULL;  //若先序序列长度小于等于0，则直接返回
  }
  node* root=new node;  //新建一个新的结点，用来存放当前二叉树的根结点
  root->data=pre[preL];  //新结点的数据与未根结点的值
  int k;
  for(k=inL;k<=inR;k++){
    if(in[k]==pre[preL]){  //在中序序列中找到in[k]==pre[L]的结点
      break;
    }
  }
  int numLeft=k-inL;  //左子树的结点数
  //返回左子树的根结点地址，赋值给root的左指针
  root->lchild=create(preL+1,preL+numLeft,inL,k-1);
  //返回右子树的根结点地址，赋值给root的右指针
  root->rchild=create(preL+numLeft+1,preR,k+1,inR);
  return root;
}

---

仅靠先序序列和后序序列是无法确定唯一的二叉树的

遍历二叉树

根据之前建立的二叉树，我们可以进行遍历

先序遍历：

void preorder(node* root){
 if(root==NULL){
    return;
  } 
  printf("%d ",root->data);
  preorder(root->lchild);
  preorder(root->rchild);
}

如果二叉树以数组的方式存储：

void preorder(int root){
  printf("%d",number[root]);
  preorder(root*2);
  preorder(root*2+1);
}

非递归实现：

 
//非递归前序遍历
void preorderTraversal(node*root){
    stack<node*> s;
    node*cur = root;
    while(cur  != NULL || !s.empty()){
        while(cur  != NULL){
            cout<<cur ->val<<" ";
            s.push(cur );
            cur  = cur ->left;
        }
        if(!s.empty()){
            cur  = s.top();
            s.pop();
            cur  = cur ->right;
        }
    }
}

---

中序遍历：

void inorder(node* root){
  if(root==NULL){
    return;
  }
  inorder(root->lchild);
  printf("%d ",root->data);
  inorder(root->rchild);
}

如果二叉树以数组的方式存储：

void inOrder(int root){
  inOrder(root*2);
  printf("%d",number[root]);
  inOrder(root*2+1);
}

非递归实现：

 
//非递归中序遍历
void inorderTraversal(node*root)
{
    stack<node*> s;
    node*cur  = root;
    while(cur  != NULL || !s.empty()){
        while(cur  != NULL){
            s.push(cur );
            cur = cur ->left;
        }
        if(!s.empty()){
            cur  = s.top();
            cout<<cur ->val<<" ";
            s.pop();
            cur  = cur ->right;
        }
    }
}

---

后序遍历：

void postorder(node* root){
  if(root==NULL){
    return;
  }
  postorder(root->lchild);
  postorder(root->rchild);
  printf("%d ",root->data);
}

如果二叉树以数组的方式存储：

void postOrder(int root){
  postOrder(root*2);
  postOrder(root*2+1);
  printf("%d",number[root]);
}

非递归实现:

vector<int> postorderTraversal(node*root) {
        stack<node*> s;
        node*cur = root;
        node*last = NULL;        // 上一个被完整后序遍历过的树的根结点
        vector<int> v;
        while (cur != NULL || !s.empty()) {
            while (cur != NULL) {
                s.push(cur);
                cur = cur->lchild;
            }

            node*top = s.top();
            if (top->rchild == NULL||top->rchild== last) {
                cout<<top->data<<" ";
                s.pop();
                last = top;
            } else {
                cur = top->rchild;
            }
        }
        return v;
 }

---

层序遍历/广度优先遍历:

void BFS(node* root){
  queue<node*> q;
  q.push(root);
  while(!q.empty()){
    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);
  }
}

---

平衡：

重新设置一下结点的结构：

struct node{
  int v,height;
  node *lchild,*rchild;
}*root;

如果一个结点的左右孩子高度差的绝对值大于1，那么可以说这个地方不平衡，故我们在建立AVL的时候应该在插入时就进行处理高度差问题.
首先我们要解决的一个问题，那就是每个数据读入之后，如何在树中创建一个新结点；
生成新结点的函数：

node* newNode(int v){
  node* Node=new node;    //申请一个node型变量的地址空间
  Node->v=v;  //结点权值为v
  Node->height=1;  //结点的初始高度设置为1
  Node->lchild=Node->rchild=NULL;  //初始设定没有左右孩子
  return Node;  //返回新建结点的地址
}

在判断高度差的问题上，我们先明确两点:
一个确认当前结点高度差的问题上，我们按照左子树高度减掉右子树高度的，
还有一个就是每次在添加结点的过程中在添加完孩子之后，父结点的高度就应该+1，例如孩子是默认高度1，那父结点就该变成2.
不过，先写出获取高度的函数以便我们上述想法的实现。
获取以root为根节点的字数的当前的height:

int getHeight(node* root){
  if(root==NULL)  return 0;  //空结点要设置为0
  return root->height;
}

更新结点root的height：

void updateHeight(node* root){
  //取左右孩子中最大的高度+1
  root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}

计算结点root的平衡因子：

int getBalanceFactor(node* root){
  //左子树高度减掉右子树高度
  return getHeight(root->lchild)-getHeight(root->rchild);
}

如果判断出不平衡的地方，也就是我们的getBalanceFactor()返回的值的绝对值大于1，我们进入正题，平衡的方式有两种：左旋和右旋
左旋:

void L(node* &root){
  node* temp=root->rchild;  //root指向结点A,temp指向结点B
  root->rchild=temp->lchild;
  temp->lchild=root;
  updateHeight(root);  //更新结点A的高度
  updateHeight(temp);  //更新结点B的高度
  root=temp;
}

右旋：

void R(node* &root){
  node* temp=root->lchild;  //root指向结点B,temp指向结点A
  root->lchild=temp->rchild;  
  temp->rchild=root;
  updateHeight(root);  //更新结点B的高度
  updateHeight(temp);  //更新结点A的高度
  root=temp;
}

我们要处理的返回值如果是2，那么我们看它左子树的返回值，如果是1那就是LL型，-1那就是LR型；
我们要处理的返回值如果是-2，那么我们看它右子树的返回值，如果是-1那就是RR型，1那就是RL型；
LL型：右旋父结点一次
LR型：左旋左子树一次，右旋父结点一次
RR型：左旋父结点一次
RL型：右旋右子树一次，左旋父结点一次
插入权值为v的结点：

void insert(node* &root,int v){
  if(root==NULL){  //到达空结点
    root==newNode(v);
    return;
  }
  //根据权值去判断往哪个子树插
  if(v < root->v){  //v比根结点权值小
    insert(root->lchild,v);  //往左子树插入
    updateHeight(root);  //更新树高
    if(getBalanceFactor(root)==2){
      if(getBalanceFactor(root->lchild)==1){  //LL型
        R(root);
      }else if(getBalanceFactor(root->lchild)==-1){  //LR型
        L(root->lchild);
        R(root);
      }
    }
  }else{  //v比根结点权值大
    insert(root->rchild,v);  //往右子树插入
    updateHeight(root);  //更新树高
    if(getBalanceFactor(root)==-2){
      if(getBalanceFactor(root->rchild)==-1){  //RR型
        L(root);
      }else if(getBalanceFactor(root->rchild)==1){    //RL型      
        R(root->rchild);
        L(root);
      }
    }
  }
}