二叉树

二叉树问题

• 节点代码

  class TreeNode<T>
  {
      public TreeNode(T val)
      {
          this.value = val;
      }
  
      public T Value
      {
          get => this.value;
          set => this.value = value;
      }
  
      public TreeNode<T> Left
      {
          get => this.left;
          set => this.left = value;
      }
  
      public TreeNode<T> Right
      {
          get => this.right;
          set => this.right = value;
      }
  
      public TreeNode<T> Parent
      {
          get => this.parent;
          set => this.parent = value;
      }
  
      private T value;
      private TreeNode<T> left;
      private TreeNode<T> right;
      private TreeNode<T> parent;
  
  }

遍历

• 先序遍历

  public static void FrontEach<T>(TreeNode<T> root, Action<T> action)
  {
      if (root == null)
      {
          return;
      }
      Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
      stack.Push(root);
      while (stack.Count != 0)
      {
          root = stack.Pop();
          action(root.Value);
          if (root.Right != null)
          {
              stack.Push(root.Right);
          }
          if (root.Left != null)
          {
              stack.Push(root.Left);
          }
      }
  }

• 中序遍历

  public static void MiddleEach<T>(TreeNode<T> root, Action<T> action)
  {
      if (root == null)
      {
          return;
      }
      Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
      while (stack.Count != 0 || root != null)
      {
          if (root != null)
          {
              stack.Push(root);
              root = root.Left;
          }
          else
          {
              root = stack.Pop();
              action(root.Value);
              root = root.Right;
          }
      }
  }

• 后序遍历

  public static void BackEach<T>(TreeNode<T> root, Action<T> action)
  {
      if (root == null)
      {
          return;
      }
      Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>(), print = new Stack<TreeNode<T>>();
      stack.Push(root);
      while (stack.Count != 0)
      {
          root = stack.Pop();
          print.Push(root);
          if (root.Left != null)
          {
              stack.Push(root.Left);
          }
          if (root.Right != null)
          {
              stack.Push(root.Right);
          }
      }
      while (print.Count != 0)
      {
          action(print.Pop().Value);
      }
  }

中序遍历的下一个

• 代码

  public static TreeNode<T> GetNextMiddleEachNode<T>(TreeNode<T> node)
  {
      if (node == null)
      {
          return null;
      }
      if (node.Right != null)
      {
          TreeNode<T> res = node.Right;
          while (res.Left != null)
          {
              res = res.Left;
          }
          return res;
      }
      else
      {
          TreeNode<T> parent = node.Parent;
          while (parent != null && node != parent.Left)
          {
              node = parent;
              parent = node.Parent;
          }
          return parent;
      }
  }

中序遍历的上一个

• 代码

  public static TreeNode<T> GetLastMiddleEachNode<T>(TreeNode<T> node)
  {
      if (node == null)
      {
          return null;
      }
      if (node.Left != null)
      {
          TreeNode<T> res = node.Left;
          while (res.Right != null)
          {
              res = res.Right;
          }
          return res;
      }
      else
      {
          TreeNode<T> parent = node.Parent;
          while (parent != null && node != parent.Right)
          {
              node = parent;
              parent = node.Parent;
          }
          return parent;
      }
  }

二叉树的序列化和反序列化

• 先序中序后序

  • 序列化

    public static string FrontSerializable<T>(TreeNode<T> root, char split = '_', char nil = '#')
    {
        if (root == null)
        {
            return $"{nil}{split}";
        }
        string res = $"{root.Value}{split}";
        res += FrontSerializable<T>(root.Left, split, nil);
        res += FrontSerializable<T>(root.Right, split, nil);
        return res;
    }
    
    public static string MiddleSerializable<T>(TreeNode<T> root, char split = '_', char nil = '#')
    {
        if (root == null)
        {
            return $"{nil}{split}";
        }
        string res = "";
        res += MiddleSerializable<T>(root.Left, split, nil);
        res += $"{root.Value}{split}";
        res += MiddleSerializable<T>(root.Right, split, nil);
        return res;
    }
    
    public static string BackSerializable<T>(TreeNode<T> root, char split = '_', char nil = '#')
    {
        if (root == null)
        {
            return $"{nil}{split}";
        }
        string res = "";
        res += BackSerializable<T>(root.Left, split, nil);
        res += BackSerializable<T>(root.Right, split, nil);
        res += $"{root.Value}{split}";
        return res;
    }

  • 反序列化

    public static TreeNode<String> UnSerializable(string str, int num, char split = '_', char nil = '#')
    {
        if (string.IsNullOrWhiteSpace(str))
        {
            return null;
        }
        string[] strs = str.Split(split);
        if (strs.Length == 0)
        {
            return null;
        }
        switch (num)
        {
            case 1: return ReconFrontTree(new Queue<string>(strs), nil);break;
            case 3: return ReconBackTree(new Stack<string>(strs), nil); break;
            default: return null;
        }
    }
    // 中序遍历的方式序列化二叉树无法还原
    /*
    例:
        树A:
                1
            2
        3
        树B:
                1
            3
                2
        这两棵二叉树中序序列化的结构都是: null 3 null 2 null 1 null, 所以无法还原.
    */
    public static TreeNode<String> ReconFrontTree(Queue<String> queue, char nil = '#')
    {
        String value = queue.Dequeue();
        if (value == $"{nil}")
        {
            return null;
        }
        TreeNode<String> root = new TreeNode<string>(value);
        root.Left = ReconFrontTree(queue, nil);
        if (root.Left != null)
        {
            root.Left.Parent = root;
        }
        root.Right = ReconFrontTree(queue, nil);
        if (root.Right != null)
        {
            root.Right.Parent = root;
        }
        return root;
    }
    
    public static TreeNode<String> ReconBackTree(Stack<String> stack, char nil = '#')
    {
        String value = stack.Pop();
        if (value == $"{nil}")
        {
            return null;
        }
        TreeNode<String> root = new TreeNode<string>(value);
        root.Right = ReconBackTree(stack, nil);
        root.Left = ReconBackTree(stack, nil);
        if (root.Left != null)
        {
            root.Left.Parent = root;
        }
        if (root.Right != null)
        {
            root.Right.Parent = root;
        }
        return root;
    }

• 层次

  • 序列化代码

    public static String LevelSerializable<T>(TreeNode<T> root, char split = '_', char nil = '#')
    {
        if (root == null)
        {
            return $"{nil}{split}";
        }
    
        Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
        queue.Enqueue(root);
        String res = "";
        while (queue.Count != 0)
        {
            TreeNode<T> tmp = queue.Dequeue();
            if (tmp == null)
            {
                res += $"{nil}{split}";
            }
            else
            {
                res += $"{tmp.Value}{split}";
                queue.Enqueue(tmp.Left);
                queue.Enqueue(tmp.Right);
            }
        }
        return res;
    }

  • 反序列化代码

    public static TreeNode<String> LevelUnSerializable(String res, char split = '_', char nil = '#')
    {
        string[] strs = res.Split(split);
        if (strs.Length == 0)
        {
            return null;
        }
        if (strs[0] == $"{nil}")
        {
            return null;
        }
        Queue<String> queue = new Queue<string>(strs);
        Queue<TreeNode<String>> help = new Queue<TreeNode<string>>();
        TreeNode<String> root = new TreeNode<string>(queue.Dequeue());
        help.Enqueue(root);
        while (help.Count != 0)
        {
            TreeNode<String> tmp = help.Dequeue();
            string left = queue.Dequeue();
            if (left != $"{nil}")
            {
                tmp.Left = new TreeNode<string>(left);
                help.Enqueue(tmp.Left);
            }
            string right = queue.Dequeue();
            if (right != $"{nil}")
            {
                tmp.Right = new TreeNode<string>(right);
                help.Enqueue(tmp.Right);
            }
        }
        return root;
    }

平衡二叉树

• 判断是否为平衡二叉树的代码

  public static Tuple<bool, int> IsBalance<T>(TreeNode<T> root)
  {
      if (root == null)
      {
          return new Tuple<bool, int>(true, 0);
      }
      Tuple<bool, int> left = IsBalance<T>(root.Left);
      Tuple<bool, int> right = IsBalance<T>(root.Right);
      return new Tuple<bool, int>(left.Item1 && right.Item1 && Math.Abs(left.Item2 - right.Item2) <= 1, 1 + Math.Max(left.Item2, right.Item2));
  }

搜索二叉树

• 判断是否为搜索二叉数的代码

  public static bool IsSearch<T>(TreeNode<T> root) where T: IComparable<T>
  {
      if (root == null)
      {
          return true;
      }
      T lastValue = root.Value;
      bool flag = true;
      Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
      while (stack.Count != 0 || root != null)
      {
          if (root != null)
          {
              stack.Push(root);
              root = root.Left;
          }
          else
          {
              root = stack.Pop();
              if (flag)
              {
                  flag = false;
                  lastValue = root.Value;
              }
              else
              {
                  if (root.Value.CompareTo(lastValue) > 0)
                  {
                      lastValue = root.Value;
                  }
                  else
                  {
                      return false;
                  }
              }
              root = root.Right;
          }
      }
      return true;
  }

完全二叉树

• 判断是否为完全二叉树的代码

  public static bool IsFull<T>(TreeNode<T> root)
  {
      if (root == null)
      {
          return true;
      }
      bool flag = false;
      Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>();
      queue.Enqueue(root);
      while (queue.Count != 0)
      {
          root = queue.Dequeue();
          if (!flag)
          {
              if (root.Left != null && root.Right != null)
              {
                  queue.Enqueue(root.Left);
                  queue.Enqueue(root.Right);
              }
              else if (root.Left == null && root.Right != null)
              {
                  return false;
              }
              else
              {
                  flag = true;
              }
          }
          else
          {
              if (root.Left != null || root.Right != null)
              {
                  return false;
              }
          }
      }
      return flag;
  }

完全二叉树节点个数

• 得到一颗完全二叉树的节点个数

  public static int NodeCount<T>(TreeNode<T> root)
  {
      if (root == null)
      {
          return 0;
      }
      return Bs<T>(root, 1, GetLeftLevel(root, 1));
  }
  
  public static int Bs<T>(TreeNode<T> root, int level, int h)
  {
      if (level == h)
      {
          return 1;
      }
      if (GetLeftLevel(root.Right, level + 1) == h)
      {
          return (1 << (h - level)) + Bs<T>(root.Right, level + 1, h);
      }
      else
      {
          return (1 << (h - level - 1)) + Bs<T>(root.Left, level + 1, h);
      }
  }
  
  public static int GetLeftLevel<T>(TreeNode<T> node, int level)
  {
      while (node != null)
      {
          level++;
          node = node.Left;
      }
      return level - 1;
  }