匆匆，原以為只是一次普通的過年回家，沒想到變成了寒假連暑假，時間線推移，來到了八月底，很多同學已經摩拳擦掌準備開學了，然而也有同學對即將到來的線下考試惴惴不安，
多說無益，先把文章看完，
在學習資料結構的程序中，二叉樹是我們繞不開的一個坎兒，關于二叉樹的重要性呢，我們并不在本文中贅述，本文想要闡述的是二叉樹的三個推論和兩個定理，
具有n個結點的二叉樹可能的形態數為C（2n，n）/（n+1），
當n等于0，也就是空樹的情形，公式成立，接著我們可以再來想一個簡單的例子：比如說一個具有三個結點的二叉樹，我們用窮舉的方式考慮，
可能的情形有：全部傾斜向左，全部傾斜向右，根和兩個孩子，根左右，根右左，總共是5種情形，代入我們的公式，沒有問題，
其實在這里有個小彩蛋，看到這個公式應該是可以聯想起來一些東西的，n個元素順序入堆疊，所有可能的出堆疊序列情況數量也是這個公式，
完全二叉樹中1度結點（只有一個孩子的結點）不是0個就是1個，
具有n個結點的二叉樹，如果用二叉鏈表來存盤，其二叉鏈表匯總空指標域的個數為n+1個，
接著我們看兩個很相似的定理，很簡單，
n(n>=0)個結點的二叉樹，可以由它的中序序列和先序序列唯一確定，
n(n>=0)個結點的二叉樹，可以由它的中序序列和后序序列唯一確定，
其實，言外之意就是說，有先序序列和后序序列是不能唯一確定一個二叉樹的、當然，如果只有一種序列也無法唯一確定一個二叉樹，
那么關于這兩個定理怎么證明呢？這個曾經是一道考研題，證明的方法是采用數學歸納法，證明思路也并不復雜，同學們可以一起來領略一下，
證明：中序序列和先序序列可以唯一確定一棵二叉樹，
當n為0的時候，可以確定，二叉樹是一棵空樹，結論正確，假設節點數小于n的任何二叉樹都可以根據中序序列和先序序列唯一確定，所以只要可以證明對于n個結點的二叉樹，也可以根據中序序列和先序序列唯一確定，就可以完事了，
對于這一棵包含n個結點的二叉樹，可以假設這課二叉樹的先序序列是a0 a1 a2 a3……a(n-1)，它的中序序列為b0 b(k-1) bk b(k+1)……b(n-1)，
因為在先序遍歷中，二叉樹訪問順序是根左右，先訪問根節點，所以a0就一定是整個二叉樹的根，而且a0也一定會在中序序列中出現，假設它在中序序列中出現的位置bk就是a0，
所以，在中序序列中，k號結點之前的b0到b(k-1)就是根的左子樹的中序序列，而k號結點之后的b(k+1)到bn就是根的右子樹的中序序列，
與之對應的，在先序序列中，緊跟在a0之后的k個結點a1到ak就一定是左子樹的先序序列，其余的a(k+1)到a（n-1）就一定是右子樹的先序序列，
結合假設2，結點數少于n的二叉樹可以由中序序列和先序序列唯一確定，所以我們談及的左子樹和右子樹可以分別根據它們的先序序列和中序序列唯一確定，
綜上所述，這棵二叉樹的左右子樹可以被唯一確定，所以整個二叉樹也就可以被唯一確定了，
開學之際，分不清興奮還是緊張；
各在一方，皆是為夢奔忙；
負重前行，我已學會眼里帶光，
感謝閱讀，學習使人強大，
如果你想更好的提升你的編程能力，成為一個強大的C/C++程式員！不妨和一些志同道合的小伙伴一起學習成長！
C語言C++編程學習交流圈子，QQ群【757874045點擊進入】微信公眾號：C語言編程學習基地
有一些原始碼和資料分享，歡迎轉行也學習編程的伙伴，和大家一起交流成長會比自己琢磨更快哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/144606.html
標籤：其他