各种树的构建方法

已知先序中序构树

#include <cstdio>  #include <iostream>  
using namespace std;  
const int N = 50;  
int pre[N], in[N], post[N];        //存放先序，中序，后序的数组   
int n;//树中元素个数  
struct node {  
    int data;//数据  
    node* lchild;//左子数指针  
    node* rchild;//右子树指针  
};  
node* create(int prel, int prer, int inl, int inr)  //根据先序和中序建立树   
{           //4个参数  先序的左右边界，中序的左右边界    
    if (prel>prer)                              //已经遍历完了，返回   
    {  
        return NULL;//返回空指针  
    }  
    node* root = new node;                      //建立一个根结点，用来存放当前的树结点  
    root->data = pre[prel];                     // 因为是已知先序，所以当前树的值，一定等于先序的最左边的点   
    int k;                                    //记录当前根节点在中序的下标  
    for (k = inl; k <= inr; k++)  
    {  
        if (in[k] == pre[prel])                 //找到位置，跳出，k不再++  
            break;  
    }  
    int numleft = k - inl;                        //当前树的左子树的数量  
    root->lchild = create(prel + 1, prel + numleft, inl, k - 1);     //将这部分存入左子树   
    root->rchild = create(prel + numleft + 1, prer, k + 1, inr);     // 将这部分存入右子树  
    return root;                //返回根结点的地址，将整个树的结点连接起来  
}  

已知后序中序构树

#include <cstdio>  #include <iostream>  #include <queue>  using namespace std;  const int N = 50;  int pre[N], in[N], post[N];//in中序，post后序  int n;//结点个数  struct Node {      int data;//数据      Node* lchild;//左子树指针      Node* rchild;//右子树指针  };  Node* create(int postl, int postr, int inl, int inr)//4个参数  后序的左右边界，中序的左右边界    {      if (postl>postr) //已经遍历完了，返回       {          return NULL;      }      Node* root = new Node; //建立一个根结点，用来存放当前的树结点      root->data = post[postr];  // 因为是已知后序，所以当前树的值，一定等于先序的最右边      int k;      for (k = inl; k<=inr; k++)      {          if (in[k] == post[postr]) //找到位置，跳出，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 printfpost(node* root)                 {      if (root == NULL)return;//遇到空指针返回        printfpost(root->lchild);      printfpost(root->rchild);        printf("%d", root->data);//这三行放后面为后序，前面先序，中间中序输出      num++;      if (num<n) printf(" ");  }

层次遍历输出

void bfs(Node* root)        //层次遍历输出   {      queue<Node*> q;      int num = 0;      q.push(root);//根结点入队      while (!q.empty())      {          Node* now = q.front();          q.pop();          printf("%d", now->data);//输出此结点数据          num++;          if (num<n) printf(" ");          if (now->lchild != NULL) q.push(now->lchild);//左右结点依次入队          if (now->rchild != NULL) q.push(now->rchild);      }      putchar(10);//换行  }  

树高度的求法

int gethight(node *root) {      if (!root)return 0;      return max(gethight(root->lchild) + 1, gethight(root->rchild) + 1);  } 

主函数

int main()  {      scanf("%d", &n);      for (int i = 0; i<n; i++)//输入先序排列      {          scanf("%d", &pre[i]);//后序scanf("%d", &post[i]);      }      for (int i = 0; i<n; i++)//输入中序排列      {          scanf("%d", &in[i]);      }      node* root = create(0, n - 1, 0, n - 1);//构树，4个参数  先后序的左右边界，中序的左右边界        调用输出函数；  }