線索二叉樹線索化函式的引數pre前為什麼要加引用

1樓:heart阿飛

你的bai那個**從風格du上看應該是嚴蔚敏書裡zhi的。需要注dao

意的是,那本書裡的回**採用的是答

類c語言,並不能直接拿來就用,而是要根據需要和環境進行一定的修改。裡面的&是借鑑了c++裡的引用的概念,是想說在函式中的改變會作用到thrt變數自身,而不是作用到那個變數的一個副本上。如果用c語言,可以改為指標形式的,如果用c++,則也可以採用引用。

只要能夠改變那個變數即可。

為什麼前序線索二叉樹線索化時遞迴入口處需要判斷左右指標是否為線索,而中序和後序不用呢?

2樓:司馬刀劍

前序遍歷(中左右)、中序遍歷(左中右)的最後訪問的節點都是左或右葉節點,葉節點是沒有子樹的,所以兩個指標域空出來了,可以存放線索指標。但是後續遍歷(左右中),最後訪問的子樹的根節點,子樹根節點的兩個指標域都指向子樹了,所以不能空出來存放線索資訊。

二叉樹線索化的思想是什麼? 15

3樓:

線索二叉樹就是

使用的物件:樹節點中沒有使用的n-1個空指標(n個樹節點,空指標永遠都是n+1個,自己推下)。

執行的原則:某種深度遍歷順序——先序,中序,後序

過程:按照中序(當然也可以是其他的遍歷)的前驅後繼關係,若p的左子樹為空,則左子樹指向p的中序前驅,若p的右子樹為空,則p的右子樹節點指向p的後繼,若是子樹都有,就不用搗騰了。第一個節點的左子樹為空(此節點一定是葉節點,而且沒前驅,所以是空),最後一個節點的右子樹也是空。

資料結構:在樹節點的結構是(data,*lchild,*rchild)線索樹的節點是(data,*lchild,*rchild,ltag,rtag),tag為1表示線索數的節點,為0標識樹節點。

目的:方便找到樹在某種遍歷的條件下前驅和後繼。不是用來遍歷的哈

注意的點:只用中序線索樹可以很完美的達到這個效果,前序線索樹在計算前驅的時候會牽扯到自己的父節點,就要使用棧來找,這樣和遍歷查詢沒區別,同理,後序線索樹找後繼會比較麻煩。

話說,要點基本就這樣了。

細節的點,比如說為什麼n+1啊,為什麼前序後序不完美啊,這些一邊就考個知道,而且推理是很快的,所以呢,考試的話,就照著我說的這幾個點就ok了,主要是要會畫,還有就是中序查詢的實現。

中序實現給你一個要點:

找前驅:向左找第一個rtag為1的就是它的前驅了。

因為在中序中,所有的內節點(非葉節點)的前驅和後繼必然是一個葉節點。

要是記不住演算法,記住這點臨場寫也夠了,前提是老兄您在之前弄明白我的要點的意義。

線索二叉樹中關於線索的問題

4樓:匿名使用者

我覺得你主要是不清楚pre指向的是什麼。

我的資料結構書是嚴蔚敏版的,書上是這麼說的:pre始終指向剛剛訪問過的結點,若指標root指向當前訪問的結點,則pre指向它的前續。

說的有點抽象。其實主要就是要清楚何時改變pre的值,「pre始終指向剛剛訪問過的結點」就是說訪問完一個結點後,就改變pre的值。

具體的思路是這樣:首先書上建立線索的**是一箇中序遍歷過程,其訪問順序分三步:左子樹->本身結點->右子樹。

其中訪問左子樹就是指呼叫函式inthread(root->lchild)。任何一次訪問結點的操作必然處在這三步中的第二步,因為第一步又可以分為三步。可見pre值的修改應該在第二步之後,且在第三步之前,即在inthread(root->rchild)之前。

正如**中一樣。

另外要注意第一次呼叫inthread前要先給pre賦值。

1.此**中的root可能指向的是二叉樹中的任意一結點,由於任意一結點可以看做一個子樹的根節點,所以可以理解為root指向二叉樹本身或其子樹的根節點。

root->lchild=pre這個**是說讓當前結點的左子樹指向當前結點的前驅(pre),即建立一個前續索引。

2.此**主要是判斷是否要給pre建立一個後續線索。那麼建立後續線索的前提條件是要右結點為空,這就是if中的判斷。

pre->rchild=root就是給pre建立一個後續索引。pre是root的前續,反過來root就是pre的後續。

3.前續和後續結點的指向通過pre與root互為前續後續的關係實現的。以首結點為例的話比較特殊,因為如果root指向首結點,那麼這就是第一次呼叫,在呼叫前要預先給pre賦值。