數(shù)據(jù)結(jié)構(gòu)教程第二十三課二叉樹的存儲結(jié)構(gòu)

教學(xué)目的： 掌握二叉樹的兩種存儲結(jié)構(gòu)
    教學(xué)重點： 鏈式存儲結(jié)構(gòu)
    教學(xué)難點： 鏈式存儲二叉樹的基本操作
    授課內(nèi)容：
    一、復(fù)習(xí)二叉樹的定義
    二叉樹的基本特征：每個結(jié)點的度不大于２。
    二、順序存儲結(jié)構(gòu)
    #define MAX_TREE_SIZE 100
    typedef TElemType SqBiTree[MAX_TREE_SIZE];
    SqBiTree bt;
    結(jié)點編號 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
    結(jié)點值 1 2 3 4 5 0 0 0 0 6 7 0 0 0 0
    第i號結(jié)點的左右孩子一定保存在第2i及2i+1號單元中。
    缺點：對非完全二叉樹而言，浪費存儲空間
    三、鏈式存儲結(jié)構(gòu)
    一個二叉樹的結(jié)點至少保存三種信息：數(shù)據(jù)元素、左孩子位置、右孩子位置
    對應(yīng)地，鏈式存儲二叉樹的結(jié)點至少包含三個域：數(shù)據(jù)域、左、右指針域。