c/c++ 用前序和中序，或者中序和后序，创建二叉树

时间：2021-07-19 16:42:34

c/c++ 用前序和中序，或者中序和后序，创建二叉树

用前序和中序创建二叉树

//用没有结束标记的char*, clr为前序，lcr为中序来创建树

//前序的第一个字符一定是root节点，然后去中序字符串中找到root节点的位置，然后在root节点位置的左边查找，root的左节点，如果找到就作为root节点的左节点；

//然后再在root节点位置的右边查找，root的右节点，如果找到就作为root节点的右节点，以此类推。

//if(k > cnt) return;这句代码非常重要，在指定位置的左右查找时，即使找到了，但是如果位置超过了createNode_clr_lcr的第三个参数，需要返回，不创建节点，理由如下：

//  char* clr = "ABCDEFGH";//前序

//  char* lcr = "CBEDFAGH";//中序

//查找D的时候，D虽然在C的右边，也就是可以找到，但超出了范围，所以D不是C的右子节点。

void createNode_clr_lcr(BinTreeNode** n, char** clr, char* lcr, int cnt){

  if(cnt == 0) return;

  int k = 0;

  while((*clr)[0] != lcr[k]){

    k++;

  }

  if(k > cnt) return;

  *n = (BinTreeNode*)malloc(sizeof(BinTreeNode));

  (*n)->data = (*clr)[0];

  (*clr)++;

  createNode_clr_lcr(&((*n)->leftChild), clr, lcr, k);

  createNode_clr_lcr(&((*n)->rightChild), clr, &(lcr[k+1]), cnt - k - 1);

}

//用没有结束标记的char*, clr为前序，lcr为中序来创建树

void createBinTree_clr_lcr(BinTree* bt, char* clr, char* lcr, int cnt){

  createNode_clr_lcr(&(bt->root), &clr, lcr, cnt);

}

用后序和中序创建二叉树

/用没有结束标记的char*, lrc为后序，lcr为中序来创建树

void createNode_lcr_lrc(BinTreeNode** n, char** lrc, char* lcr, int cnt){

  if(cnt == 0) return;

  int k = 0;

  while((*lrc)[0] != lcr[k]){

    k++;

  }

  if(k > cnt) return;

  *n = (BinTreeNode*)malloc(sizeof(BinTreeNode));

  (*n)->data = (*lrc)[0];

  (*lrc)++;

  createNode_lcr_lrc(&((*n)->rightChild), lrc, &(lcr[k+1]), cnt - k - 1);

  createNode_lcr_lrc(&((*n)->leftChild), lrc, lcr, k);

}

//用没有结束标记的char*, lrc为后序，lcr为中序来创建树

//后序的思想和前序类似，先把后序的字符串反转过来，然后先创建又节点，再创建左节点即可。

void createBinTree_lcr_lrc(BinTree* bt, char* lrc, char* lcr, int cnt){

  //反转lrc

  int i = 0;

  int k = strlen(lrc) - 1;

  while(k - i > 0){

    char c = lrc[k];

    lrc[k] = lrc[i];

    lrc[i] = c;

    i++;

    k--;

  }

  //lrc = "AGHBDFEC";

  createNode_lcr_lrc(&(bt->root), &lrc, lcr, cnt);

}

bintreemain.c

#include "bintree.h"

int main(){

  char* clr = "ABCDEFGH";

  char* lcr = "CBEDFAGH";

  //char* lrc = "CEFDBHGA";

  BinTree tr2;

  init(&tr2, '#');

  int n2 = strlen(clr);

  createBinTree_clr_lcr(&tr2, clr, lcr, n2);

  display_clr(&tr2);

  printf("\n");

  char* lcr1 = "CBEDFAGH";

  char lrc1[] = "CEFDBHGA";

  BinTree tr3;

  init(&tr3, '#');

  int n3 = strlen(lcr1);

  createBinTree_lcr_lrc(&tr3, lrc1, lcr1, n3);

  display_clr(&tr3);

  printf("\n");

  return 0;

}

完整代码

编译方法：g++ -g nodestack.c nodequeue.c bintree.c bintreemain.c

相关文章