樹的(de)基本概念
時間：2018-07-26 來源：未知
一、學習時間
2018年3月27日
二、課程安排
隊列、樹
三、學習內容
1. 什么是(shi)隊列
隊(dui)列是限制在兩端進行的(de)(de)插入和刪除操作的(de)(de)線性表(注：為(wei)區分滿(man)隊(dui)和空對，滿(man)隊(dui)元(yuan)素的(de)(de)個數比數組中(zhong)的(de)(de)個數少一個)
2.什么是樹
樹是有(you)n個節點(dian)(dian)的(de)有(you)限集合，它滿足有(you)且僅有(you)一(yi)個特定(ding)的(de)根節點(dian)(dian)，其余節點(dian)(dian)又分成(cheng)m個互不相(xiang)交的(de)有(you)限集合。
3.樹的基(ji)本概念(nian)
度(du)數：一個(ge)節(jie)點的(de)子樹(shu)的(de)個(ge)數，其中，一棵樹(shu)的(de)度(du)數是(shi)指(zhi)該樹(shu)種(zhong)節(jie)點的(de)最(zui)大度(du)數。
樹葉(xie)：度數為零的節(jie)點(dian)
高度：樹中節點層(ceng)數的(de)最大值
4.什么是二叉樹(shu)
由一(yi)個(ge)根節點(dian)以及(ji)兩顆互補交融的(de)、分(fen)別稱為左(zuo)子(zi)樹和右子(zi)樹的(de)二叉樹組成。
5.二叉樹的性(xing)質
二叉樹第i層(ceng)上的節點最多為2^(i-1)
深度為K的二叉樹最多有2^k-1
任意一顆二叉樹(shu)中，樹(shu)葉的數(shu)目比度數(shu)為2的節點的數(shu)目多一
滿二叉樹：
深度(du)為k時(shi)有2^k-1個節點的二叉樹
完全二叉樹：
只有最(zui)(zui)下面兩(liang)層有度數小于2的節點，且(qie)最(zui)(zui)下面一層的葉(xie)節點集中在最(zui)(zui)左邊的若(ruo)干位(wei)置。
6.二叉樹的存儲(chu)以及遍歷
先序遍歷：先訪(fang)問根節點，再訪(fang)問左子樹，最(zui)后訪(fang)問右子樹
中序遍歷：先訪問(wen)左子樹，再訪問(wen)根節點，最(zui)后(hou)訪問(wen)右(you)子樹
后序遍歷：先訪問左子樹，再訪問右(you)子樹，最(zui)后訪問根節點
五、學習心得
通過對棧和隊的(de)(de)學(xue)習(xi)(xi)，明(ming)白指(zhi)(zhi)(zhi)針在(zai)數(shu)據結構中(zhong)的(de)(de)重(zhong)(zhong)要性，所以在(zai)學(xue)習(xi)(xi)的(de)(de)過程中(zhong)，要明(ming)白指(zhi)(zhi)(zhi)針的(de)(de)指(zhi)(zhi)(zhi)向(xiang)，指(zhi)(zhi)(zhi)針地址的(de)(de)操(cao)作。在(zai)樹的(de)(de)學(xue)習(xi)(xi)中(zhong)，重(zhong)(zhong)點(dian)需要注意的(de)(de)便是(shi)二叉樹的(de)(de)一些性質，同(tong)時，要注重(zhong)(zhong)對遞歸(gui)的(de)(de)理(li)解。
