1樓:拍子
1.在後序序列中,若結點p有右子女,則右子女是其前驅,若無右子女而有左子女,則左子女是其前驅。
2.若結點p左右子女均無,設其中序左線索指向某祖先結點f(p是f右子樹中按中序遍歷的第一個結點),若f有左子女,則其左子女是結點p在後序下的前驅;若f無左子女,則順其前驅找雙親的雙親,一直繼續到雙親有左子女(這時左子女是p的前驅)。
3.還有一種情況,若p是中序遍歷的第一個結點,結點p在中序和後序下均無前驅。
2樓:
.[題目分析]在後序序列中,若結點p有右子女,則右子女是其前驅,若無右子女而有左子女,則左子女是其前驅。若結點p左右子女均無,設其中序左線索指向某祖先結點f(p是f右子樹中按中序遍歷的第一個結點),若f有左子女,則其左子女是結點p在後序下的前驅;若f無左子女,則順其前驅找雙親的雙親,一直繼續到雙親有左子女(這時左子女是p的前驅)。還有一種情況,若p是中序遍歷的第一個結點,結點p在中序和後序下均無前驅。
bithrtree inpostpre (bithrtree t,p)
//在中序線索二叉樹t中,求指定結點p在後序下的前驅結點qreturn(q); }//結束inpostpre
寫出中序線索二叉樹中找指定節點在後序下的前驅結點的演算法
3樓:
.[題目分析]在後序序列中,若結點p有右子女,則右子女是其前驅,若無右子女而有左子女,則左子女是其前驅。若結點p左右子女均無,設其中序左線索指向某祖先結點f(p是f右子樹中按中序遍歷的第一個結點),若f有左子女,則其左子女是結點p在後序下的前驅;若f無左子女,則順其前驅找雙親的雙親,一直繼續到雙親有左子女(這時左子女是p的前驅)。還有一種情況,若p是中序遍歷的第一個結點,結點p在中序和後序下均無前驅。
bithrtree inpostpre (bithrtree t,p)
//在中序線索二叉樹t中,求指定結點p在後序下的前驅結點qreturn(q); }//結束inpostpre
說明在中序線索二叉樹中找結點後繼的方法,並完成以下的演算法。
4樓:熊熊藻
在中序線索二叉樹中找結點後繼的方法: a.若rtag=1, 則rchild域直接指向其後繼 b.
若rtag=0, 其後繼應是遍歷其右子樹時訪問的第一個結點,即右子樹中最左下的結點。 if (p->rtag==1 ) return p->rchild ; q= p->rchild; while(q->ltag==0 ) q=q->lchild ; return q ; }// insucc
某二叉樹的前序遍歷是abdgcefh,中序遍歷是dgbaechf,則起後序遍歷的結點訪問順序是什麼,為什麼
不太記得了,應該是 g d b a e h f c 二叉樹的3中遍歷,知道任何其中2種,就可以建立這個二叉樹。自然就可以得到第3中的遍歷了。具體方法可以翻書或網上查詢相關資料。前序是 根左右 由此可判斷a為根節點,再看中序 由於a為根,所以在中序中根據 左根右 原則a前的即為a的左子樹 dgb 右邊...
寫出先序遍歷的二叉樹的遍歷演算法,怎樣實現二叉樹的前序遍歷的非遞迴演算法
遞迴方式 include typedef struct nodebitnode,bittree void createtree bittree bt void visit char ch void preorder bittree bt void main include include defin...
二叉樹兩個結點的最近相同父節點怎麼求,有什麼演算法
1.面對這樣的場景,選擇父親孩子結構的方式組建二叉樹就很容易了。2.如果是普通的左右結內點結構組建的二叉樹容,那就遍歷吧。int getfather treenode root,treenode a,treenode b if root a root b return 1 num else retu...