王道數(shù)據(jù)結(jié)構(gòu)二叉樹算法題求指導(dǎo)

kg810 · 發(fā)表于 2012-9-2 22:24

本帖最后由 kg810 于 2012-9-2 22:26 編輯

王道數(shù)據(jù)結(jié)構(gòu) 116 頁第 11 題 “已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個(gè)元素值為x的節(jié)點(diǎn)，刪去以他為根的子樹，并釋放相應(yīng)的空間”

答案給的算法用的后序非遞歸遍歷。
我覺得先序遞歸方法更好啊，遇到值為x的節(jié)點(diǎn)，他的子樹就不需要考慮，全部刪掉。
算法如下：
int tag;          //為1時(shí)表示遇到值為x的節(jié)點(diǎn)
void search(BitTree T,ElemType x){
BitTree P = T;
BitTree Q = NULL; //用于釋放節(jié)點(diǎn)
while(P){
      if(P->data == x) tag = 1;
      search(P->ltree);
      search(P->rtree);
      if(tag == 1){
            Q = P->lchild; free(Q);
            Q = P->rchild; free(Q);
      }//if
}//while
}
求指導(dǎo)！

1018ji · 發(fā)表于 2012-9-2 23:12

額你想的也太簡單了吧所謂刪除不是釋放X節(jié)點(diǎn)那么簡單
還要釋放他包含的一堆節(jié)點(diǎn)

后序遍歷好處是先左后右最后根節(jié)點(diǎn)刪除時(shí)候最后刪除X節(jié)點(diǎn)又能釋放他所包含節(jié)點(diǎn)

先序并不是說不可以但是要換換寫法

關(guān)鍵是理解刪除要求《刪去以他為根的子樹，并釋放相應(yīng)的空間》題目要求

好了好好學(xué)習(xí)，進(jìn)度有點(diǎn)慢。

kg810 · 發(fā)表于 2012-9-2 23:23

1018ji 發(fā)表于 2012-9-2 23:12
額你想的也太簡單了吧所謂刪除不是釋放X節(jié)點(diǎn)那么簡單
還要釋放他包含的一堆節(jié)點(diǎn)

先謝啦！
但是遞歸上來的話，該節(jié)點(diǎn)的子樹中的每個(gè)節(jié)點(diǎn)都會被free掉啊，為什么不行啊。
我進(jìn)度確實(shí)慢，剛開始兩個(gè)禮拜。今年二戰(zhàn)，去年考的通信專業(yè)，今年因?yàn)楣ぷ髟蜻€是考計(jì)算機(jī)。也是因?yàn)楣ぷ髟驔]有太多的額時(shí)間復(fù)習(xí)。

1018ji · 發(fā)表于 2012-9-2 23:45

kg810 發(fā)表于 2012-9-2 23:23
先謝啦！
但是遞歸上來的話，該節(jié)點(diǎn)的子樹中的每個(gè)節(jié)點(diǎn)都會被free掉啊，為什么不行啊。
我進(jìn)度確實(shí)慢，剛 ...

額我也感覺這個(gè)tag有問題

這貨是個(gè)全局變量是會出現(xiàn)問題的

這個(gè)題代碼這么短？

kg810 · 發(fā)表于 2012-9-3 07:48

1018ji 發(fā)表于 2012-9-2 23:45
額我也感覺這個(gè)tag有問題

這貨是個(gè)全局變量是會出現(xiàn)問題的

謝啦 tag可以在函數(shù)返回時(shí)重新賦0吧還是覺得是對的。。。。。。

1018ji · 發(fā)表于 2012-9-3 22:12

kg810 發(fā)表于 2012-9-3 07:48
謝啦 tag可以在函數(shù)返回時(shí)重新賦0吧還是覺得是對的。。。。。。

額這個(gè)遞歸還真好好說看是沒用的最好調(diào)試一下，呵呵

kg810 · 發(fā)表于 2012-9-4 07:46

1018ji 發(fā)表于 2012-9-3 22:12
額這個(gè)遞歸還真好好說看是沒用的最好調(diào)試一下，呵呵

嗯謝謝你 *

1018ji · 發(fā)表于 2012-9-4 09:35

kg810 發(fā)表于 2012-9-4 07:46
嗯謝謝你 *

QQ還真不用主要是考研就把QQ廢了

有興趣郵件聯(lián)系 *

		自動登錄	找回密碼
密碼			注冊

王道數(shù)據(jù)結(jié)構(gòu)二叉樹算法題求指導(dǎo)

NEW最新資料推薦

評分

評分

王道數(shù)據(jù)結(jié)構(gòu)二叉樹算法題 求指導(dǎo)

NEW最新資料推薦

評分

評分

王道數(shù)據(jù)結(jié)構(gòu)二叉樹算法題求指導(dǎo)