正文  电脑教程 > 服务器教程 >

c语言构建一个静态二叉树实现方法

  第一、树的构建   定义树结构   struct BTNode {   char data;   struct BTNode* pLChild;...

  第一、树的构建

  定义树结构

  struct BTNode {

  char data;

  struct BTNode* pLChild;

  struct BTNode* pRChild;

  };

  静态方式创建一个简单的二叉树

  struct BTNode* create_list() {

  struct BTNode* pA = (struct BTNode*)malloc(sizeof(BTNode));

  struct BTNode* pB = (struct BTNode*)malloc(sizeof(BTNode));

  struct BTNode* pC = (struct BTNode*)malloc(sizeof(BTNode));

  struct BTNode* pD = (struct BTNode*)malloc(sizeof(BTNode));

  struct BTNode* pE = (struct BTNode*)malloc(sizeof(BTNode));

  pA->data = ‘A‘;

  pB->data = ‘B‘;

  pC->data = ‘C‘;

  pD->data = ‘D‘;

  pE->data = ‘E‘;

  pA->pLChild = pB;

  pA->pRChild = pC;

  pB->pLChild = pB->pRChild = NULL;

  pC->pLChild = pD;

  pC->pRChild = NULL;

  pD->pLChild = NULL;

  pD->pRChild = pE;

  pE->pLChild = pE->pRChild = NULL;

  return pA;

  }

  第二、树的三种遍历

  1. 先序遍历

  //先序输出

  void PreTravense(struct BTNode* pHead) {

  if (NULL!= pHead)

  {

  printf("%c", pHead->data);

  if (NULL!= pHead->pLChild)

  {

  PreTravense(pHead->pLChild);

  }

  if (NULL != pHead->pRChild)

  {

  PreTravense(pHead->pRChild);

  }

  }

  }

  2. 中序遍历

  //中序输出

  void InTravense(struct BTNode* pHead) {

  if (NULL != pHead)

  {

  if (NULL != pHead->pLChild)

  {

  PreTravense(pHead->pLChild);

  }

  printf("%c", pHead->data);

  if (NULL != pHead->pRChild)

  {

  PreTravense(pHead->pRChild);

  }

  }

  }

  3.后续遍历

  //后序输出

  void PostTravense(struct BTNode* pHead) {

  if (NULL != pHead)

  {

  if (NULL != pHead->pLChild)

  {

  PreTravense(pHead->pLChild);

  }

  if (NULL != pHead->pRChild)

  {

  PreTravense(pHead->pRChild);

  }

  printf("%c", pHead->data);

  }

  }

  第三、最终运行测试

  int main() {

  printf("创建序列 ");

  struct BTNode* pHead = create_list();

  printf("先序输出 ");

  PreTravense(pHead);

  printf("中序输出 ");

  InTravense(pHead);

  printf("后序输出 ");

  PostTravense(pHead);

  return 0;

  }