树的遍历转换

已知二叉树先序和中序遍历,求树的高度

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000;

typedef struct BTNode{
  char data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

BinTree create(char *pre, char *in, int len){
  BinTree T;
  int i;
  if(len == 0)  return NULL;
  T = (BTNode *)malloc(sizeof(BTNode));
  T -> data = pre[0]; //当前节点数据为先序遍历第一个元素
  for(i = 0; i < len; i ++){  //中序遍历中找根节点
    if(pre[0] == in[i]) break;
  }
  //左子树的先序遍历起始点即为当前先序遍历的下一位置,中序遍历起始位置不变,长度为中序遍历根节点左侧部分
  T -> lchild = create(pre + 1, in, i);
  T -> rchild = create(pre + i + 1, in + i + 1, len - i - 1);
  //右子树先序遍历起始点为当前先序遍历左子树之后部分,中序同,长度为当前长度减左子树减1(当前节点)
  return T;
}

int height(BinTree T){
  int h, l, r;
  if(T == NULL) h = 0;
  else{
    l = height(T -> lchild);
    r = height(T -> rchild);
    h = max(l, r) + 1;
  }
  return h;
}

int main(){
  int n;
  char pre[55], in[55];
  BinTree T = NULL;
  scanf("%d", &n);
  scanf("%s\n%s", pre, in);
  T = create(pre, in, n);
  printf("%d\n", height(T));
  return 0;
}

已知后序遍历和中序遍历,求树的层序遍历

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1000;

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

BinTree create(int post[], int in[], int len){
  BinTree T;
  int i;
  if(len == 0)  return NULL;
  T = (BTNode *)malloc(sizeof(BTNode));
  T -> data = post[len - 1]; //当前节点数据为后序遍历最后一个节点
  for(i = 0; i < len; i ++){  //中序遍历中找根节点
    if(post[len - 1] == in[i]) break;
  }
  T -> lchild = create(post, in, i);
  T -> rchild = create(post + i, in + i + 1, len - i - 1);
  return T;
}

int cnt = 0;
int n;

void print(BinTree T){
    queue<BinTree> q;
    q.push(T);

    while(!q.empty()){
        BinTree now = q.front();
        q.pop();
        cnt ++;
        printf("%d", now->data);
        if(cnt != n)    printf(" ");
        if(now->lchild != NULL) q.push(now->lchild);
        if(now->rchild != NULL) q.push(now->rchild);
    }
}


int main(){

  int post[55], in[55];
  BinTree T = NULL;
  scanf("%d", &n);
  for(int i = 0; i < n; i ++)   scanf("%d", &post[i]);
  for(int i = 0; i < n; i ++)   scanf("%d", &in[i]);
  T = create(post, in, n);
  print(T);
  return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注