1樓：匿名使用者
我覺得你主要是不清楚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賦值。
線索二叉樹,什麼是線索二叉樹,為什麼要使用線索二叉樹
我先說一說 每個 節點 那 五個格 的資料 的含義 中間哪一個 是 儲存資料 從左向右 第一個 和 第五個 是指標，具體指向什麼 取決於第二個 和 第四個的值 第二個 如果是零，實線表示，則 第一個指向的是 左孩子 第二個 如果是1，虛線表示，則 第一個 指向的是 在中序遍歷次序下 該節點的前驅 即...
線索二叉樹線索化函式的引數pre前為什麼要加引用
你的bai那個 從風格du上看應該是嚴蔚敏書裡zhi的。需要注dao 意的是,那本書裡的回 採用的是答 類c語言,並不能直接拿來就用,而是要根據需要和環境進行一定的修改。裡面的 是借鑑了c 裡的引用的概念,是想說在函式中的改變會作用到thrt變數自身,而不是作用到那個變數的一個副本上。如果用c語言,...
平衡二叉樹定義,討論請問平衡二叉樹和二叉排序樹的關係
所謂平衡二叉樹是指樹中任一結點的左 右子樹高度大致相同。平衡二叉樹有很多種最著名的是由前蘇聯數學家adelse velskil和landis在1962年提出的，稱為avl樹。平衡二叉樹 avl樹 定義如下 平衡二叉樹或者是一棵空樹，或者是具有以下性質的二叉排序樹 1 它的左子樹和右子樹的高度之差絕對...