數據結構教程第二十三課二叉樹的存儲結構

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