給定一棵樹的先根遍歷序列和后根遍歷序列,能否唯一確定一棵樹?若能,請舉例說明； 若不能,請給出反例。
答案給的是可以確定，因為先根遍歷對應二叉樹的先序遍歷，后根遍歷對應二叉樹的中序遍歷。因為二叉樹的先序遍歷和中序遍歷可以唯一確定一顆二叉樹，所以也可以唯一確定一顆二叉排序樹
我覺得答案說的很有道理，但是又覺得，如果這棵樹本身就是一顆二叉樹，那么它的先根遍歷就是先序遍歷，后根遍歷就是后續遍歷。可是先序遍歷和后續遍歷并不能唯一的確定一顆二叉樹，也就更不能唯一確定一棵樹了
不知道我的想法哪里錯了，希望各位大佬可以幫我解答一下
uj5u.com熱心網友回復：
你亂了吧，怎么答案說“后根遍歷對應二叉樹的中序遍歷”你覺得對，后面你又覺得“后根遍歷就是后續遍歷”，那問題不就是后根遍歷到底對應中序遍歷還是對應后續遍歷嗎？這個問題你應該知道吧。。。uj5u.com熱心網友回復：
“先根遍歷對應二叉樹的先序遍歷，后根遍歷對應二叉樹的中序遍歷”這個是針對樹跟對應的轉換后的二叉樹而說的，這點很關鍵答案分析應該有問題，雖然先序跟中序能確定一棵二叉樹，但這棵二叉樹并不能唯一對應一棵樹，因為樹轉二叉樹是唯一的，反過來則不是
你理解的也有點兒問題，一棵樹本來就是二叉樹，但根據數轉二叉樹的規則轉換后，并不是原來的二叉樹（否則上面的規則就不對了）
這個題的答案應該是可以確定，嚴格證明要用歸納法，一般分析如下：之所以二叉樹的先序遍歷和后序遍歷不能唯一確定一棵二叉樹，是由于存在度為1的節點，也就是只有一個子節點，它在左在右對應的先序和后續遍歷順序一樣但二叉樹不一樣，但是樹沒有左右的概念，只要是子節點確定了，那這個樹就確定了，在左在右都是一棵樹
大概就是這樣吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/274196.html
標籤：C語言
上一篇：怎么輸出十位整數