🎈 作者：Linux猿
🎈 簡介：CSDN博客專家🏆，華為云享專家🏆，Linux、C/C++、云計算、物聯網、面試、刷題、演算法盡管咨詢我，關注我，有問題私聊！
🎈 關注專欄： 動圖講解資料結構和演算法 （優質好文持續更新中……）🚀
🎈 歡迎小伙伴們點贊👍、收藏?、留言💬
目錄
一、什么是相互轉換
二、樹與二叉樹的相互轉換
2.1 樹轉換為二叉樹
2.2 樹轉換二叉樹實體
2.2 二叉樹轉換為樹
2.3 二叉樹轉換為樹實體
三、森林與二叉樹的相互轉換
3.1 森林轉換為二叉樹
3.2 森林轉換為二叉樹實體
3.3 二叉樹轉換為森林
3.4 二叉樹轉換為森林實體
四、總結
在對樹進行一些操作時，比如：遍歷樹，存盤樹等，并沒有非常方便的資料結構來存盤，那么，可以將樹轉換為二叉樹，可以使用二叉鏈表來存盤，這樣就方便多了，接下來，本篇文章來講解下二叉樹、樹和森林的相互轉換，趕緊來看一下吧！
一、什么是相互轉換
正如文章開頭所提到的，不規則的樹并沒有非常合適的資料結構來存盤，而二叉樹有多中存盤方式，比如：雙親表示法，孩子表示法等，另一方面，給定一棵樹，有唯一的一棵二叉樹與之對應，這樣就可以在樹和二叉樹之間作相互轉換，
接下來將會介紹樹與二叉樹、森林與二叉樹的相互轉換，
二、樹與二叉樹的相互轉換
2.1 樹轉換為二叉樹
樹轉換為二叉樹的步驟如下所示：
步驟一：兄弟連線，在樹的相鄰兄弟結點之間連線；
步驟二：刪原連線，洗掉原父結點與孩子結點的連線，僅保留每個父結點與第一個孩子結點的連線；
步驟三：層次調整，調整樹的層次結構，使其成為一棵二叉樹，
下面來看一個例子來加深理解，
2.2 樹轉換二叉樹實體
假設有如下一棵樹，如下圖所示，
（1）在樹的相鄰兄弟結點之間連線，連線后如下圖所示，
在上圖中，樹中的相鄰兄弟結點連接了紅色虛線，包括：BC、CD、EF、FG等的連線，注意：是相鄰的兄弟結點連線，
（2）洗掉原樹父結點與子節點的連線，注意：保留每個父結點與第一個孩子結點的連線，如下所示，
如上圖所示，洗掉了 AC、AD、BF、BG、DI、DJ的連線，這時候已經是一棵二叉樹了，下面來調整下二叉樹的層次結構，
（3）以根結點 A 為基礎，調整結點的層次結構，如下所示，
如上圖所示，經過調整后成為了一棵正規的二叉樹，
2.2 二叉樹轉換為樹
二叉樹轉換為樹的步驟如下所示：
步驟一：連線右孩子，如果結點 i 的左孩子存在，則將結點 i 與左孩子的右孩子結點、左孩子的右孩子的右孩子結點，…… 連線，
步驟二：刪原連線，洗掉原二叉樹中所有父結點與其右孩子結點的連線，
步驟三：層次調整，調整轉換后的二叉樹的層次結構，
2.3 二叉樹轉換為樹實體
假設有如下二叉樹，如下圖所示，
（1）將每個父節點與左孩子的右孩子結點，左孩子的右孩子的右孩子結點，……連線，注意：是每一個父結點，如下所示，
在上圖中，結點 A 與左孩子 B 的右節點 C，左孩子 B 的右孩子 C 的右孩子 D 進行了連線，其它父結點同理，如上圖的 紅色 虛線所示，
（2）洗掉原二叉樹中每個父節點與右孩子的連線，如下所示，
在上圖中，分別洗掉了 BC、CD、EF、FG 等的連線，
（3）層次調整，將當前的樹進行調整，將同一個層次的結點調整到相同層，如下所示，
經過調整后成為了一棵樹，這棵樹和 2.2 中的樹是一致的，
三、森林與二叉樹的相互轉換
3.1 森林轉換為二叉樹
森林轉換為二叉樹的步驟如下所示：
步驟一：先將森林中的每一棵樹轉換為二叉樹，參見 2.1 樹轉換為二叉樹；
步驟二：第一顆二叉樹不變，其它的二叉樹依次作為前一個二叉樹的右子樹；
下面來看一個例子加深理解，
3.2 森林轉換為二叉樹實體
假設有如下森林，如下圖所示，
（1）首先，將森林中的每一顆樹轉換為二叉樹，轉換后如下圖所示，
先將森林中的每一顆樹轉換為二叉樹，轉換程序同樹轉換為二叉樹，轉換后如下所示，
（2）將轉換后的所有二叉樹組成一個二叉樹，組合后如下圖所示，
在上圖中，紅色虛線表示添加的連接，除了第一顆子樹外，其它子樹都成為了前一棵子樹的右子樹，
3.3 二叉樹轉換為森林
二叉樹轉換為森林的步驟如下所示：
步驟一：將二叉樹根結點與它的右子樹、根結點的右子樹與右子樹……的連線去掉；
步驟二：將拆分后的每一個二叉樹轉換為樹，
下面來看一個例子加深理解，
3.4 二叉樹轉換為森林實體
假設有如下二叉樹，如下圖所示，
（1）首先，將二叉樹拆分開，拆分后如下所示，
（2）然后，將拆分后的每一個二叉樹轉換為樹，如下所示，
四、總結
本文主要對二叉樹與樹和森林之間的相互轉換進行了詳細的講解，需要掌握轉換的方法，
🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓
【博客之星活動】希望路過的小伙伴支持下猿哥 點擊鏈接，拉到文章結尾，點擊五星！感謝支持！🌹🌹🌹🌹🌹🌹🌹🌹
電腦端的小伙伴可以點擊這里：主頁左上角
猿哥將一如既往的更新優質文章回饋大家！
🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓🍓
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/398674.html
標籤：java
上一篇：>Bagging
下一篇：括號匹配問題