c語言二叉樹(完整版)
【正文】 集合 樹的定義 A 只有根結點的樹 A B C D E F G H I J K L M 有子樹的樹 根 子樹 樹的定義 –基本術語 ? 結點 (node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支 ? 結點的度 (degree)——結點擁有的子樹數(shù) ? 葉子 (leaf)——度為 0的結點 ? 孩子 (child)——結點子樹的根稱為該結點的孩子 ? 雙親 (parents)——孩子結點的上層結點叫該結點的 ~ ? 兄弟 (sibling)——同一雙親的孩子 ? 樹的度 ——一棵樹中最大的結點度數(shù) ? 結點的層次 (level)——從根結點算起， 根為第一層 ，它的孩子為第二層 …… ? 深度 (depth)——樹中結點的最大層次數(shù) ? 森林 (forest)——m(m?0)棵互不相交的樹的集合 樹的相關術語 A B C D E F G H I J K L M 結點 A的度： 3 結點 B的度： 2 結點 M的度： 0 葉子： K， L， F， G， M， I， J 結點 A的孩子： B， C， D 結點 B的孩子： E， F 結點 I的雙親： D 結點 L的雙親： E 結點 B， C， D為兄弟 結點 K， L為兄弟 樹的度： 3 結點 A的層次： 1 結點 M的層次： 4 樹的深度： 4 結點 F， G為堂兄弟 結點 A是結點 F， G的祖先 樹的相關術語 –定義 ? 定義：二叉樹是 n(n?0)個結點的有限集，它或為空樹(n=0)， 或由一個根結點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構成 ? 特點 –每個結點至多有二棵子樹 (即不存在度大于 2的結點 ) –二叉樹的子樹有左、右之分，且其次序不能任意顛倒 ? 基本形態(tài) A 只有根結點 的二叉樹 ? 空二叉樹 A B 右子樹為空 A B 左子樹為空 A B C 左、右子樹 均非空 二叉樹 ? 性質 1： )1(2 1 ?? ii i 個結點層上至多有在二叉樹的第證明：用歸納法證明之 ?i=1時，只有一個根結點， 是對的 ?假設對所有 j(1?ji)命題成立，即第 j層上至多有 個結點 那么，第 i1層至多有 個結點 又二叉樹每個結點的度至多為 2 ? 第 i層上最大結點數(shù)是第 i1層的 2倍，即 故命題得證 122 01 ???i12?j22?i12 222 ?? ?? ii?性質 2：深度為 k的二叉樹至多有 個結點 (k?1) 12 ?k證明：由性質 1，可得深度為 k 的二叉樹最大結點數(shù)
教學教案相關推薦
鄂ICP備17016276號-1