c/c++ 用前序和中序，或者中序和後序，創建二叉樹

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