← 筆記
LeetCode

《圖說演算法-使用C#》要點摘錄 – 「二叉樹」

書名：《圖說演算法-使用C#》

作者：吳燦銘、胡昭民

所讀版本：博碩文化

二叉樹

滿二叉樹（Fully Binary Tree）
  • 節點數 = 2^(高度) - 1，高度>=0
完全二叉樹（Complete Binary Tree）
  • 節點數 < 2^(高度) - 1，但其最底層缺少右邊若干節點
歪斜樹（Skewed Binary Tree）
  • 完全沒有左/右節點
嚴格二叉樹（Strictly Binary Tree）
  • 每個非終端節點均有非空的左右子樹

數組實作二叉樹

  • Left Index = Father Index * 2
  • Right Index = Father Index * 2 + 1
  • 以一維數組建立二叉樹 = 建立一個二叉搜尋樹
    • 可以是空集合，但若不是，則節點上一定要有一個鍵值
    • 左子節點值<根節點；右子節點值>根節點
    • 左右子樹本身也是搜尋樹
    • 樹的每個節點值都不相同
  •   static void Main(string[] args)
  {
  int[] data = new int[8] { 6, 3, 5, 9, 7, 8, 4, 2 };
  int[] result = ConstructBinaryTreeByArray(data);
  for (int i = 1; i < result.Length; i++)
  {
  	Console.Write(result[i] + " ");
  }            
  Console.WriteLine();    
  }
  
  public static int[] ConstructBinaryTreeByArray(int[] data)
  {
  int[] tree = new int[data.Length * 2];
  int treeIdx;
      for (int i = 0; i < data.Length; i++)
      {
          for(treeIdx = 1; tree[treeIdx] != 0;)
          {
          	if(data[i] > tree[treeIdx])
              {
                  //Bigger than father
                  treeIdx = treeIdx * 2 + 1;
              }
              else
              {
                  //Smaller than father
                  treeIdx = treeIdx * 2;
              }
          }
          tree[treeIdx] = data[i];
      }
      return tree;
  }

鏈表實作二叉樹

  •   public class TreeNode
  {
      public int val;
      public TreeNode left;
      public TreeNode right;
      public TreeNode(int val)
      {
          this.val = val;
          left = null;
          right = null;
      }
  }
  public class BinaryTree
  {
      public TreeNode root;        
  
      public BinaryTree(int root)
      {
          this.root = new TreeNode(root);
      }
  
      public void Add(int node)
      {
          TreeNode curr = root;
          TreeNode newNode = new TreeNode(node);
          while(true)
          {
              if(newNode.val >= curr.val)
              {
                  if(curr.right == null)
                  {
                      curr.right = newNode;
                      return;
                  }
                  curr = curr.right;
              }
              else
              {
                  if(curr.left == null)
                  {
                      curr.left = newNode;
                      return;
                  }
                  curr = curr.left;                    
              }
          }
      }
  }

二叉樹算法

前序/中序/後序遍歷

  • 前：根 -> 左 -> 右

    •   public void ForwardTraverse(TreeNode curr)
  {
      if (curr == null) { return; }
      Console.WriteLine(curr.val);
      ForwardTraverse(curr.left);
      ForwardTraverse(curr.right);
  }

  • 中：左 -> 根 -> 右

    •   public void MiddleTraverse(TreeNode curr)
  {
      if (curr == null) { return; }
      MiddleTraverse(curr.left);
      Console.WriteLine(curr.val);
      MiddleTraverse(curr.right);
  }

  • 後：左 -> 右 -> 根

    •   public void BackwardTraverse(TreeNode curr)
  {
      if (curr == null) { return; }
      BackwardTraverse(curr.left);
      BackwardTraverse(curr.right);
      Console.WriteLine(curr.val);
  }
二叉搜尋樹

  • 一個二叉樹符合「每一何節點凡資料>左子節點且小於右小節點」，便可稱為二分樹。

    • 二叉搜尋樹和二叉排序樹都是二分樹的一種
    • 二叉搜尋樹和二叉排序樹是一體兩面，沒有分別，可以說是對二分樹的兩種操作方式

  • 可以是空集合，但若不是，則節點上一定要有一個鍵值

  • 左子節點值<根節點；右子節點值>根節點

  • 左右子樹本身也是搜尋樹

  • 樹的每個節點值都不相同

  •   bool Finder(TreeNode curr, int target)
  {
      if(curr == null) { return false; }            
      else if(target == curr.val)
      {
          return true;
      }
      else if(target > curr.val)
      {
          return Finder(curr.right, target);
      }
      else
      {
          return Finder(curr.left, target);
      }
  }
二叉樹插入節點
  • if (!tree.Find(10))
{
    tree.Add(10);
    tree.Traverse(TraversalType.InOrder);
}
二叉樹刪除節點
  • 如果刪除節點為葉節點，直接將其父樹指向它的引用置空
  • 如果刪除節點只有一棵子樹，則將其父樹指向其子樹
  • 如果刪除節點有兩個子樹，則可選擇令其父樹指向：
    • 其左子樹中最右的葉節點
    • 其右子樹中最左的葉節點
二叉排序樹
  • 第一個輸入的資料作為樹根
  • 之後的資料以遞歸的方式與樹根比較，比根節點小的置於左子樹，比根節點大的置於右子樹
    • 對樹中序遍歷即可得出由小到大的結果
引線二叉樹

  • 把節點中的空鏈結指向樹的其他節點，這些鏈結稱為「引線」

  • 步驟：

    • 中序遍歷二叉樹，將空鏈結改成引線
    • 如果引線指向該節點的左鏈結，將該引線指到中序遍歷順序下的後一個節點
    • 如果引線指向該節點的右鏈結，將該引線指到中序遍歷順序下的後一個節點
    • 指向一個空節點，並將此空節點的右鏈結指向自己，空節點的左子樹是此引線二叉樹

  • 引線二叉樹的結構

    • LBIT：左控制位元
    • LCHILD：左子樹鏈結
    • DATA：節點資料
    • RCHILD：右子樹鏈結
    • RBIT：右控制位元
    • 如果LCHILD為正常指標，LBIT = 1；如果為引線，則=0
    • 如果RCHILD為正常指標，RBIT = 1；如果為引線，則=0

  • 優缺點

    • 優點
      • 中序遍歷不需要用Stack，而一般二叉樹需要
      • 中序遍歷速度較快
      • 避免鏈結閒置
      • 任一節點都容易找出他的中序後繼者（右子樹最小）和中序前行者（左子樹最大）。
    • 缺點
      • 加入/刪除節點比一般二叉樹慢
      • 引線子樹間不能共享
  •   public class ThreadedNode
  {
      public int data, lbit, rbit;
      public ThreadedNode lchild, rchild;
      public ThreadedNode(int data)
      {
          this.data = data;
          this.lbit = 0;
          this.rbit = 0;
          this.lchild = null;
          this.rchild = null;
      }
  }
  
  public class Threaded_Binary_Tree
  {
      //引線二元樹根節點
      public ThreadedNode root;
  
      public Threaded_Binary_Tree()
      {
          root = null;
      }
      public Threaded_Binary_Tree(int[] data)
      {
          foreach (var i in data)
          {
              AddNode(i);
          }
      }
  
      public void AddNode(int val)
      {
          ThreadedNode newNode = new ThreadedNode(val);
          ThreadedNode curr;
          ThreadedNode parent;
          ThreadedNode prev = new ThreadedNode(val);
          int pos;
          //設定起始節點
          if(root == null)
          {
              root = newNode;
              root.lchild = root;
              root.rchild = null;
              root.lbit = 0;
              root.rbit = 1;
              return;
          }
  
          //設定起始節點所指的節點
          curr = root.rchild;
          if(curr == null)
          {
              root.rchild = newNode;
              newNode.lchild = root;
              newNode.rchild = root;
              return;
          }
  
          parent = root; //父節點是起始節點
          pos = 0; //設定二叉樹的行進方向
  
          while(curr != null)
          {
              if(curr.data > val)
              {
                  if(pos != 1)
                  {
                      pos = -1;
                      prev = parent;
                  }
                  parent = curr;
                  if(curr.lbit == 1)
                  {
                      curr = curr.lchild;
                  }
                  else
                  {
                      curr = null;
                  }
              }
              else
              {
                  if(pos != 1)
                  {
                      pos = 1;
                      prev = parent;
                  }
                  parent = curr;
                  if(curr.rbit == 1)
                  {
                      curr = curr.rchild;
                  }
                  else
                  {
                      curr = null;
                  }
              }
  
              if(parent.data > val)
              {
                  parent.lbit = 1;
                  parent.lchild = newNode;
                  newNode.lchild = prev;
                  newNode.rchild = parent;
              }
              else
              {
                  parent.rbit = 1;
                  parent.rchild = newNode;
                  newNode.lchild = parent;
                  newNode.rchild = prev;
              }
  
              return;
          }
      }
  }
延伸二叉樹
  • 任何一個二叉樹，若具有n個節點，則有n-1個非空鏈結，n+1個空鏈結。
    • 在每一個空鏈結上加一個特定節點，稱為外節點。
    • 其餘節點（不包括根節點）稱為內節點
    • 該樹可被定義為「延伸二叉樹」。
  • 外徑長 = 所有外節點到樹根距離的總和
  • 內徑長 = 所有內節點到樹根距離的總和
  • 如果每個外節點都有加權值（如搜尋機率等），則外徑長必須考慮相關加權值（加權外徑長）
霍夫曼樹
  • 有n個權值（q1, q2 … qn），且構成一個有n個節點的二叉樹，每個節點外部節點權值為qi，則加權徑長度最小的稱為「最佳化二叉樹」（霍夫曼樹）
平衡樹（AVL樹）
  • 二叉搜尋樹在加入資料後，有可能產生歪斜樹，使樹的高度增加，導致搜尋效率下降。
  • 因此，需要通過保持二叉樹高度平衡，從而保證搜尋效率。
  • 插入/刪除資料後，對二叉樹進行高度調整。
  • 高度平衡樹條件：
    • 左右子樹也是高度平衡樹
    • 內部節點的左右子樹高度相差小於等於1