第4單元非線性結構一-資料下載頁
2025-09-19 16:09本頁面
【導讀】1)存在唯一的元素沒有前趨,稱為根；3)所有元素，或有若干個互不相同的后繼，樹是一個或多個結點組成的有限集。0）個互不相交的集。書目錄目錄樹樹結構。兄弟結點擁有同一父結點的結點之間互為。樹的度樹中結點的最大度數(shù)；上述樹的度為3。有序樹結點的各子樹看成從左至右有順序且。不能互換，則該樹為有序樹。高度從一結點到葉結點的最長路徑為該結點。刪除結點x的第i個子樹。樹中各個結點，且使每個結點只被訪問一次。普通樹的特殊情況；深度為4,則最多有24-1個結點.y置為x的左孩子。若深度為k的二叉樹T中共有2k-1個。第i個結點存放在第i個位置；第i層的結點個數(shù)均為2i-1. 第k層從右邊連續(xù)缺若干個結點。設完全二叉樹的結點總數(shù)為n，深度為k，某結。2*i+1,否則,i為葉結點.完全二叉樹也可以采用一維樹組作為存儲結構,且方法完全同滿二叉樹.
【正文】 (“%d \n”,rootdata)。 if (rootlc!=NULL) preorder_t(rootlc)。 if (rootrc!=NULL) preorder_t(rootrc)。 } } 前序遍歷序列為： A B C D E F A B C D E F 35 /41 樹類的存儲結構 ?雙親表示 : 數(shù)組實現(xiàn) ?孩子表示 : 鏈表實現(xiàn) ?孩子兄弟表示 : 二叉鏈表實現(xiàn) 36 /41 一 . 雙親表示法 1 2 3 4 5 6 7 8 9 序號 → 結點 → 雙親 → 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 1 2 2 3 5 5 5 特點： 找雙親容易，找子結點難 存儲數(shù)據(jù)元素結點同時存儲雙親結點的位置 37 /41 二 . 孩子表示法 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 NULL 4 5 NULL 6 NULL NULL 7 8 9 NULL 特點 : 便于實現(xiàn)對孩子的操作 ,不便于對父親 的操作 . NULL NULL NULL NULL 為每個結點的孩子建立一個鏈表 38 /41 三 .孩子兄弟表示法 1 2 3 4 5 6 7 8 9 1 2 NULL 3 7 4 5 6 8 9 左子女右兄弟表示 39 /41 樹、森林轉(zhuǎn)換 成 二叉樹 ? 一 . 樹轉(zhuǎn)換成二叉樹 – 加線 : 連接兄弟結點； – 抹線 :保留一個結點的最左子結點 ,抹掉其余兄弟結點與上級結點連線； – 以根為軸 ， 順時針旋轉(zhuǎn) 加線 o o o o o o o o o o o o o o o o o o o o o 抹線 旋轉(zhuǎn) o o o o o o o 40 /41 二 . 森林轉(zhuǎn)換成二叉樹 ? 將森林中每棵樹的樹根連接起來； ? 將每棵樹轉(zhuǎn)換成對應的二叉樹； ? 以第一棵樹的根為軸順時針旋轉(zhuǎn) o o o o o o o o o o 連線 o o o o o o o o o o 抹線 o o o o o o o o o o 旋轉(zhuǎn) o o o o o o o o o o 41 /41 作業(yè) 本單元 作業(yè)： 課本 88頁 11 題
教學課件相關推薦
鄂ICP備17016276號-1