| 導購 | 订阅 | 在线投稿
分享
 
 
當前位置: 王朝網路 >> c/c++ >> 數據結構C語言實現系列——二叉樹
 

數據結構C語言實現系列——二叉樹

2008-06-01 02:07:09  編輯來源:互聯網  简体版  手機版  評論  字體: ||
 
 
  Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid"

  #include <stdio.h>

  #include <stdlib.h>

  #define STACK_MAX_SIZE 30

  #define QUEUE_MAX_SIZE 30

  #ifndef elemType

  typedef char elemType;

  #endif

  /************************************************************************/

  /* 以下是關于二叉樹操作的11個簡單算法 */

  /************************************************************************/

  strUCt BTreeNode{

  elemType data;

  struct BTreeNode *left;

  struct BTreeNode *right;

  };

  /* 1.初始化二叉樹 */

  void initBTree(struct BTreeNode* *bt)

  {

  *bt = NULL;

  return;

  }

  /* 2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立) */

  void createBTree(struct BTreeNode* *bt, char *a)

  {

  struct BTreeNode *p;

  struct BTreeNode *s[STACK_MAX_SIZE];/* 定義s數組爲存儲根結點指針的棧使用 */

  int top = -1; /* 定義top作爲s棧的棧頂指針,初值爲-1,表示空棧 */

  int k; /* 用k作爲處理結點的左子樹和右子樹,k = 1處理左子樹,k = 2處理右子樹 */

  int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字符串,初值爲0 */

  *bt = NULL; /* 把樹根指針置爲空,即從空樹開始建立二叉樹 */

  /* 每循環一次處理一個字符,直到掃描到字符串結束符\0爲止 */

  while(a[i] != '\0'){

   switch(a[i]){

   case ' ':

   break; /* 對空格不作任何處理 */

   case '(':

   if(top == STACK_MAX_SIZE - 1){

   printf("棧空間太小!\n");

   exit(1);

   }

   top++;

   s[top] = p;

   k = 1;

   break;

   case ')':

   if(top == -1){

   printf("二叉樹廣義表字符串錯誤!\n");

   exit(1);

   }

   top--;

   break;

   case ',':

   k = 2;

   break;

   default:

  

   p = malloc(sizeof(struct BTreeNode));

   p->data = a[i];

   p->left = p->right = NULL;

   if(*bt == NULL){

   *bt = p;

   }else{

   if( k == 1){

   s[top]->left = p;

   }else{

   s[top]->right = p;

   }

   }

   }

   i++; /* 爲掃描下一個字符修改i值 */

  }

  return;

  }

  /* 3.檢查二叉樹是否爲空,爲空則返回1,否則返回0 */

  int emptyBTree(struct BTreeNode *bt)

  {

  if(bt == NULL){

   return 1;

  }else{

   return 0;

  }

  }

  /* 4.求二叉樹深度 */

  int BTreeDepth(struct BTreeNode *bt)

  {

  if(bt == NULL){

   return 0; /* 對于空樹,返回0結束遞歸 */

  }else{

   int dep1 = BTreeDepth(bt->left); /* 計算左子樹的深度 */

   int dep2 = BTreeDepth(bt->right); /* 計算右子樹的深度 */

   if(dep1 > dep2){

   return dep1 + 1;

   }else{

   return dep2 + 1;

   }

  }

  }

  /* 5.從二叉樹中查找值爲x的結點,若存在則返回元素存儲位置,否則返回空值 */

  elemType *findBTree(struct BTreeNode *bt, elemType x)

  {

  if(bt == NULL){

   return NULL;

  }else{

   if(bt->data == x){

   return &(bt->data);

   }else{ /* 分別向左右子樹遞歸查找 */

   elemType *p;

   if(p = findBTree(bt->left, x)){

   return p;

   }

   if(p = findBTree(bt->right, x)){

   return p;

   }

   return NULL;

   }

  }

  }

  /* 6.輸出二叉樹(前序遍曆) */

  void printBTree(struct BTreeNode *bt)

  {

  /* 樹爲空時結束遞歸,否則執行如下操作 */

  if(bt != NULL){

   printf("%c", bt->data); /* 輸出根結點的值 */

   if(bt->left != NULL bt->right != NULL){

   printf("(");

   printBTree(bt->left);

   if(bt->right != NULL){

   printf(",");

   }

   printBTree(bt->right);

   printf(")");

   }

  }

  return;

  }

  /* 7.清除二叉樹,使之變爲一棵空樹 */

  void clearBTree(struct BTreeNode* *bt)

  

   {

  if(*bt != NULL){

   clearBTree(&((*bt)->left));

   clearBTree(&((*bt)->right));

   free(*bt);

   *bt = NULL;

  }

  return;

  }

  /* 8.前序遍曆 */

  void preOrder(struct BTreeNode *bt)

  {

  if(bt != NULL){

   printf("%c ", bt->data); /* 訪問根結點 */

   preOrder(bt->left); /* 前序遍曆左子樹 */

   preOrder(bt->right); /* 前序遍曆右子樹 */

  }

  return;

  }

  /* 9.前序遍曆 */

  void inOrder(struct BTreeNode *bt)

  {

  if(bt != NULL){

   inOrder(bt->left); /* 中序遍曆左子樹 */

   printf("%c ", bt->data); /* 訪問根結點 */

   inOrder(bt->right); /* 中序遍曆右子樹 */

  }

  return;

  }

  /* 10.後序遍曆 */

  void postOrder(struct BTreeNode *bt)

  {

  if(bt != NULL){

   postOrder(bt->left); /* 後序遍曆左子樹 */

   postOrder(bt->right); /* 後序遍曆右子樹 */

   printf("%c ", bt->data); /* 訪問根結點 */

  }

  return;

  }

  /* 11.按層遍曆 */

  void levelOrder(struct BTreeNode *bt)

  {

  struct BTreeNode *p;

  struct BTreeNode *q[QUEUE_MAX_SIZE];

  int front = 0, rear = 0;

  /* 將樹根指針進隊 */

  if(bt != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = bt;

  }

  while(front != rear){ /* 隊列非空 */

   front = (front + 1) % QUEUE_MAX_SIZE; /* 使隊首指針指向隊首元素 */

   p = q[front];

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

   /* 若結點存在左孩子,則左孩子結點指針進隊 */

   if(p->left != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = p->left;

   }

   /* 若結點存在右孩子,則右孩子結點指針進隊 */

   if(p->right != NULL){

   rear = (rear + 1) % QUEUE_MAX_SIZE;

   q[rear] = p->right;

   }

  }

  return;

  }

  /************************************************************************/

  /*

  int main(int argc, char *argv[])

  {

  struct BTreeNode *bt; /* 指向二叉樹根結點的指針 */

  char *b; /* 用于存入二叉樹廣義表的字符串 */

  elemType x, *px;

  initBTree(&bt);

  printf("輸入二叉樹廣義表的字符串:\n");

  /* scanf("%s", b); */

  b = "a(b(c), d(e(f, g), h(, i)))";

  createBTree(&bt, b);

  if(bt != NULL)

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

  printf("以廣義表的形式輸出:\n");

  printBTree(bt); /* 以廣義表的形式輸出二叉樹 */

  printf("\n");

  printf("前序:"); /* 前序遍曆 */

  

   preOrder(bt);

  printf("\n");

  printf("中序:"); /* 中序遍曆 */

  inOrder(bt);

  printf("\n");

  printf("後序:"); /* 後序遍曆 */

  postOrder(bt);

  printf("\n");

  printf("按層:"); /* 按層遍曆 */

  levelOrder(bt);

  printf("\n");

  /* 從二叉樹中查找一個元素結點 */

  printf("輸入一個待查找的字符:\n");

  scanf(" %c", &x); /* 格式串中的空格跳過空白字符 */

  px = findBTree(bt, x);

  if(px){

   printf("查找成功:%c\n", *px);

  }else{

   printf("查找失敗!\n");

  }

  printf("二叉樹的深度爲:");

  printf("%d\n", BTreeDepth(bt));

  clearBTree(&bt);

  return 0;

  }

  */
 
 
 
上一篇《在C語言中如何處理時間和日期》
下一篇《C++設計模式之Singleton》
 
 
 
 
 
 
日版寵物情人插曲《Winding Road》歌詞

日版寵物情人2017的插曲,很帶節奏感,日語的,女生唱的。 最後聽見是在第8集的時候女主手割傷了,然後男主用嘴幫她吸了一下,插曲就出來了。 歌手:Def...

兄弟共妻,我成了他們夜裏的美食

老鍾家的兩個兒子很特別,就是跟其他的人不太一樣,魔一般的執著。兄弟倆都到了要結婚的年齡了,不管自家老爹怎麽磨破嘴皮子,兄弟倆說不娶就不娶,老父母爲兄弟兩操碎了心...

如何磨出破洞牛仔褲?牛仔褲怎麽剪破洞?

把牛仔褲磨出有線的破洞 1、具體工具就是磨腳石,下面墊一個硬物,然後用磨腳石一直磨一直磨,到把那塊磨薄了,用手撕開就好了。出來的洞啊很自然的。需要貓須的話調幾...

我就是掃描下圖得到了敬業福和愛國福

先來看下敬業福和愛國福 今年春節,支付寶再次推出了“五福紅包”活動,表示要“把欠大家的敬業福都還給大家”。 今天該活動正式啓動,和去年一樣,需要收集“五福”...

冰箱異味産生的原因和臭味去除的方法

有時候我們打開冰箱就會聞到一股異味,冰箱裏的這種異味是因爲一些物質發出的氣味的混合體,聞起來讓人惡心。 産生這些異味的主要原因有以下幾點。 1、很多人有這種習...

《極品家丁》1-31集大結局分集劇情介紹

簡介 《極品家丁》講述了現代白領林晚榮無意回到古代金陵,並追隨蕭二小姐化名“林三”進入蕭府,不料卻陰差陽錯上演了一出低級家丁拼搏上位的“林三升職記”。...

李溪芮《極品家丁》片尾曲《你就是我最愛的寶寶》歌詞

你就是我最愛的寶寶 - 李溪芮 (電視劇《極品家丁》片尾曲) 作詞:常馨內 作曲:常馨內 你的眉 又鬼馬的挑 你的嘴 又壞壞的笑 上一秒吵鬧 下...

烏梅的功效與作用以及烏梅的食用禁忌有哪些?

烏梅,又稱春梅,中醫認爲,烏梅味酸,性溫,無毒,具有安心、除熱、下氣、祛痰、止渴調中、殺蟲的功效,治肢體痛、肺痨病。烏梅泡水喝能治傷寒煩熱、止吐瀉,與幹姜一起制...

什麽是脂肪粒?如何消除臉部脂肪粒?

什麽是脂肪粒 在我們的臉上總會長一個個像脂肪的小顆粒,弄也弄不掉,而且顔色還是白白的。它既不是粉刺也不是其他的任何痘痘,它就是脂肪粒。 脂肪粒雖然也是由油脂...

網絡安全治理:國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰受害者

來源:中國青年報 新的攻擊方法不斷湧現,黑客幾乎永遠占據網絡攻擊的上風,我們不可能通過技術手段杜絕網絡攻擊。國家安全保障的主要方向是打擊犯罪,而不是處置和懲罰...

河南夫妻在溫嶺網絡直播“造人”內容涉黃被刑事拘留

夫妻網絡直播“造人”爆紅   1月9日,溫嶺城北派出所接到南京警方的協查通告,他們近期打掉了一個涉黃直播APP平台。而根據掌握的線索,其中有一對涉案的夫妻主播...

如何防止牆紙老化?牆紙變舊變黃怎麽辦?

如何防止牆紙老化? (1)選擇透氣性好的牆紙 市場上牆紙的材質分無紡布的、木纖維的、PVC的、玻璃纖維基材的、布面的等,相對而言,PVC材質的牆紙最不透氣...

鮮肌之謎非日本生産VS鮮肌之謎假日貨是謠言

觀點一:破日本銷售量的“鮮肌之謎” 非日本生産 近一段時間,淘寶上架了一款名爲“鮮肌之謎的” 鲑魚卵巢美容液,號稱是最近日本的一款推出的全新護膚品,産品本身所...

中國最美古詩詞精選摘抄

系腰裙(北宋詞人 張先) 惜霜蟾照夜雲天,朦胧影、畫勾闌。人情縱似長情月,算一年年。又能得、幾番圓。 欲寄西江題葉字,流不到、五亭前。東池始有荷新綠,尚小如...

關于女人的經典語句

關于女人的經典語句1、【做一個獨立的女人】 思想獨立:有主見、有自己的人生觀、價值觀。有上進心,永遠不放棄自己的理想,做一份自己喜愛的事業,擁有快樂和成就...

未來我們可以和性愛機器人結婚嗎?

你想體驗機器人性愛嗎?你想和性愛機器人結婚嗎?如果你想,機器人有拒絕你的權利嗎? 近日,第二屆“國際人類-機器人性愛研討會”大會在倫敦金史密斯大學落下帷幕。而...

全球最變態的十個地方

10.土耳其地下洞穴城市 變態指數:★★☆☆☆ 這是土耳其卡帕多西亞的一個著名景點,傳說是當年基督教徒們爲了躲避戰爭而在此修建。裏面曾住著20000人,...

科學家稱,人類死亡後意識將在另外一個宇宙中繼續存活

據英國《每日快報》報道,一位科學家兼理論家Robert Lanza博士宣稱,世界上並不存在人類死亡,死亡的只是身體。他認爲我們的意識借助我們體內的能量生存,而且...

《屏裏狐》片頭曲《我愛狐狸精》歌詞是什麽?

《我愛狐狸精》 - 劉馨棋   (電視劇《屏裏狐》主題曲)   作詞:金十三&李旦   作曲:劉嘉   狐狸精 狐狸仙   千年修...

 
 
 
Word-BREAK: break-all; PADDING-TOP: 4px; BORDER-BOTTOM: windowtext 0.5pt solid" #include <stdio.h> #include <stdlib.h> #define STACK_MAX_SIZE 30 #define QUEUE_MAX_SIZE 30 #ifndef elemType typedef char elemType; #endif /************************************************************************/ /* 以下是關于二叉樹操作的11個簡單算法 */ /************************************************************************/ strUCt BTreeNode{ elemType data; struct BTreeNode *left; struct BTreeNode *right; }; /* 1.初始化二叉樹 */ void initBTree(struct BTreeNode* *bt) { *bt = NULL; return; } /* 2.建立二叉樹(根據a所指向的二叉樹廣義表字符串建立) */ void createBTree(struct BTreeNode* *bt, char *a) { struct BTreeNode *p; struct BTreeNode *s[STACK_MAX_SIZE];/* 定義s數組爲存儲根結點指針的棧使用 */ int top = -1; /* 定義top作爲s棧的棧頂指針,初值爲-1,表示空棧 */ int k; /* 用k作爲處理結點的左子樹和右子樹,k = 1處理左子樹,k = 2處理右子樹 */ int i = 0; /* 用i掃描數組a中存儲的二叉樹廣義表字符串,初值爲0 */ *bt = NULL; /* 把樹根指針置爲空,即從空樹開始建立二叉樹 */ /* 每循環一次處理一個字符,直到掃描到字符串結束符\0爲止 */ while(a[i] != '\0'){ switch(a[i]){ case ' ': break; /* 對空格不作任何處理 */ case '(': if(top == STACK_MAX_SIZE - 1){ printf("棧空間太小!\n"); exit(1); } top++; s[top] = p; k = 1; break; case ')': if(top == -1){ printf("二叉樹廣義表字符串錯誤!\n"); exit(1); } top--; break; case ',': k = 2; break; default: p = malloc(sizeof(struct BTreeNode)); p->data = a[i]; p->left = p->right = NULL; if(*bt == NULL){ *bt = p; }else{ if( k == 1){ s[top]->left = p; }else{ s[top]->right = p; } } } i++; /* 爲掃描下一個字符修改i值 */ } return; } /* 3.檢查二叉樹是否爲空,爲空則返回1,否則返回0 */ int emptyBTree(struct BTreeNode *bt) { if(bt == NULL){ return 1; }else{ return 0; } } /* 4.求二叉樹深度 */ int BTreeDepth(struct BTreeNode *bt) { if(bt == NULL){ return 0; /* 對于空樹,返回0結束遞歸 */ }else{ int dep1 = BTreeDepth(bt->left); /* 計算左子樹的深度 */ int dep2 = BTreeDepth(bt->right); /* 計算右子樹的深度 */ if(dep1 > dep2){ return dep1 + 1; }else{ return dep2 + 1; } } } /* 5.從二叉樹中查找值爲x的結點,若存在則返回元素存儲位置,否則返回空值 */ elemType *findBTree(struct BTreeNode *bt, elemType x) { if(bt == NULL){ return NULL; }else{ if(bt->data == x){ return &(bt->data); }else{ /* 分別向左右子樹遞歸查找 */ elemType *p; if(p = findBTree(bt->left, x)){ return p; } if(p = findBTree(bt->right, x)){ return p; } return NULL; } } } /* 6.輸出二叉樹(前序遍曆) */ void printBTree(struct BTreeNode *bt) { /* 樹爲空時結束遞歸,否則執行如下操作 */ if(bt != NULL){ printf("%c", bt->data); /* 輸出根結點的值 */ if(bt->left != NULL bt->right != NULL){ printf("("); printBTree(bt->left); if(bt->right != NULL){ printf(","); } printBTree(bt->right); printf(")"); } } return; } /* 7.清除二叉樹,使之變爲一棵空樹 */ void clearBTree(struct BTreeNode* *bt) { if(*bt != NULL){ clearBTree(&((*bt)->left)); clearBTree(&((*bt)->right)); free(*bt); *bt = NULL; } return; } /* 8.前序遍曆 */ void preOrder(struct BTreeNode *bt) { if(bt != NULL){ printf("%c ", bt->data); /* 訪問根結點 */ preOrder(bt->left); /* 前序遍曆左子樹 */ preOrder(bt->right); /* 前序遍曆右子樹 */ } return; } /* 9.前序遍曆 */ void inOrder(struct BTreeNode *bt) { if(bt != NULL){ inOrder(bt->left); /* 中序遍曆左子樹 */ printf("%c ", bt->data); /* 訪問根結點 */ inOrder(bt->right); /* 中序遍曆右子樹 */ } return; } /* 10.後序遍曆 */ void postOrder(struct BTreeNode *bt) { if(bt != NULL){ postOrder(bt->left); /* 後序遍曆左子樹 */ postOrder(bt->right); /* 後序遍曆右子樹 */ printf("%c ", bt->data); /* 訪問根結點 */ } return; } /* 11.按層遍曆 */ void levelOrder(struct BTreeNode *bt) { struct BTreeNode *p; struct BTreeNode *q[QUEUE_MAX_SIZE]; int front = 0, rear = 0; /* 將樹根指針進隊 */ if(bt != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = bt; } while(front != rear){ /* 隊列非空 */ front = (front + 1) % QUEUE_MAX_SIZE; /* 使隊首指針指向隊首元素 */ p = q[front]; printf("%c ", p->data); /* 若結點存在左孩子,則左孩子結點指針進隊 */ if(p->left != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = p->left; } /* 若結點存在右孩子,則右孩子結點指針進隊 */ if(p->right != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q[rear] = p->right; } } return; } /************************************************************************/ /* int main(int argc, char *argv[]) { struct BTreeNode *bt; /* 指向二叉樹根結點的指針 */ char *b; /* 用于存入二叉樹廣義表的字符串 */ elemType x, *px; initBTree(&bt); printf("輸入二叉樹廣義表的字符串:\n"); /* scanf("%s", b); */ b = "a(b(c), d(e(f, g), h(, i)))"; createBTree(&bt, b); if(bt != NULL) printf(" %c ", bt->data); printf("以廣義表的形式輸出:\n"); printBTree(bt); /* 以廣義表的形式輸出二叉樹 */ printf("\n"); printf("前序:"); /* 前序遍曆 */ preOrder(bt); printf("\n"); printf("中序:"); /* 中序遍曆 */ inOrder(bt); printf("\n"); printf("後序:"); /* 後序遍曆 */ postOrder(bt); printf("\n"); printf("按層:"); /* 按層遍曆 */ levelOrder(bt); printf("\n"); /* 從二叉樹中查找一個元素結點 */ printf("輸入一個待查找的字符:\n"); scanf(" %c", &x); /* 格式串中的空格跳過空白字符 */ px = findBTree(bt, x); if(px){ printf("查找成功:%c\n", *px); }else{ printf("查找失敗!\n"); } printf("二叉樹的深度爲:"); printf("%d\n", BTreeDepth(bt)); clearBTree(&bt); return 0; } */
󰈣󰈤
 
 
 
  免責聲明:本文僅代表作者個人觀點,與王朝網路無關。王朝網路登載此文出於傳遞更多信息之目的,並不意味著贊同其觀點或證實其描述,其原創性以及文中陳述文字和內容未經本站證實,對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾,請讀者僅作參考,並請自行核實相關內容。
 
 
高清美女攝影(8)
高清美女攝影(7)
高清美女攝影(6)
高清美女攝影(5)
痞子的甘南日記
疑是銀河落九天
雪域壩上四——純美色
冬日戀歌——西城楊柳弄輕柔
 
>>返回首頁<<
 
 熱帖排行
 
 
 
 
© 2005- 王朝網路 版權所有