【C算法】第10章 木構造

だんだん終局が近づいてきた。

• n進木：ノードの度数がたかだかnの木。
  
• 2進木：ノードの度数がたかだか2の木。
  
• 2分木：ノードの度数がたかだか2であり、子に左右の区別がある木。
  
• 2分探索木：キー値について、どのノードにおいても、それの左部分木のノードは小さく、それの右部分木のノードは大きい2分木。
  
• 2分探索木を深さ優先探索して通りがけ順でみると、キー値の昇順でノードが得られる。
  
• いまさらながら、2分探索木はおなじメンツでも違う構成があることに気付いた。
  

  
  　　６
  　／　＼
  ２　　　７
  　＼
  　　３
  
  　　　　６
  　　　／　＼
  　　３　　　７
  　／　
  ２
  

  
  
• 完全2分木
  
  
  
  • 最下層以外は全て「詰まって」いる。
    
  • 最下層は、左側から詰めていく。
    
  • 根から下流へ、各層を左から右へと添字をふっていくと、配列の添字に対応できる。
    

    
    　　　　０
    　　　／　＼
    　　１　　　２
    　／　＼
    ３　　　４
    

    
    
  
  
• ん? list10-2で
  

  
  else if (cond < 0)
    SearchNode(p->left, x);
  else 
    SearchNode(p->right, x);
  

  
  は、次の間違いでは?
  

  
  else if (cond < 0)
    return (SearchNode(p->left, x));
  else 
    return (SearchNode(p->right, x));
  

  
  

最後のほうがぐだぐだになったが木構造がおわった。
次回は6-8 ヒープソート。