递归创建

  • 思路：通过传入一个集合/数组，按照其元素顺序创建二叉树节点，并将其值赋予节点。当集合/数组中的某一元素为null时，表明当前不具有节点，也即表明当前节点的父节点不具有左子树或右子树。

步骤1：

  • 通过传入的数据按顺序进行二叉树节点的生成。这里我们以前序遍历为例。
  • 首先是遍历这组数据。我们可以确定其递归函数表达式类似为：

f(arr) = f(arr){arr.RemoveAt(0)}

  • 由于传入的参数x是一组数据集合/数组，所以我们可以考虑每次遍历都删除元素索引为0的元素：

    1. void Create(Lsit<int?> arr)
    2. {
    3.   if(arr == null || arr.Count == 0) return;
    5.   arr.RemoveAt(0);
    6.   Create(arr);
    7. }
    • 通过上述代码即可遍历该集合。至于递归出口，自然地，当传入的arr为空、或者遍历到最后一个数据时（即arr的元素个数为0时），返回。

  • 上述遍历的递归路径为线性路径，在二叉树结构中分为两条路径，所以我们需要额外增加一次调用，于此同时，制定路径变换条件（当满足某一条件时返回，即可返回执行下一条路径）。

    • 至于条件。考虑到需要在二叉树节点的左或右子节点为空的情况下折返走另一条路径，所以可以判断当前集合/数组的第一个元素是否为null，为null的情况下说明需要走相对路径，返回即可。

      1. void Create(Lsit<int?> arr)
      2. {
      3. if(arr == null || arr.Count == 0) return;
      5. if(arr[0] == null) return;
      7. arr.RemoveAt(0);
      8. Create(arr);
      9. Create(arr);
      10. }

  • 但按照上面这样写会有一个问题：由于在当前第一个元素为null时执行的返回操作之前没有将集合/数组的第一个元素删除，这就会导致整个递归遍历过程遇到null即“归”回去了，null后面的所有元素都不会遍历到。

  • 换句话说，不管当前遍历到的集合元素是否为null，我们都需要进行删除首元素操作：

    1. void Create(Lsit<int?> arr)
    2. {
    3.   if(arr == null || arr.Count == 0) return;
    5.   if(arr[0] == null)
    6.   {
    7.       arr.RemoveAt(0);
    8.       return;
    9.   }
    10.   arr.RemoveAt(0);
    11.   Create(arr);
    12.   Create(arr);
    13. }

    步骤2：

  • 以上，根据传入的集合/数组进行双向路径的遍历操作已经完成。接下来，我们就需要生成二叉树了，即求值问题。

  • 思路很简单，我们要在每一次遍历过程中都生成一个节点，并将当前遍历元素值赋予节点。这个操作理应放在“递”过程的代码执行周期中：

    • 如下，鉴于达到路径变换条件时不需要生成新节点，所以该操作需放在路径变化条件判断的后面。

      1. void Create(Lsit<int?> arr)
      2. {
      3. if(arr == null || arr.Count == 0) return;
      5. if(arr[0] == null)
      6. {
      7.    arr.RemoveAt(0);
      8.    return;
      9. }
      11. var node = new BinaryTree() { Data = arr[0] };
      13. arr.RemoveAt(0);
      14. Create(arr);
      15. Create(arr);
      16. }

      步骤3：

  • 前面解决了遍历以及节点生成的问题，接下来就需要考虑如何把生成的二叉树返回、如何把生成的所有二叉树节点组成一个二叉树，即返回问题。

  • 我们知道，如果要在每一次遍历中返回某个值，只需要在每次遍历过程中新建、然后返回即可，如此一来，便会将当前的值返回给上一个遍历层。

  • 首先，我们思考把整个二叉树的根节点返回的操作：

    • 只需在末尾将新建的node返回，同时改变递归函数的返回类型以及出口、路径变换条件中的返回值：

      1. BinaryTree Create(Lsit<int?> arr)
      2. {
      3. if(arr == null || arr.Count == 0) return null;
      5. if(arr[0] == null)
      6. {
      7.    arr.RemoveAt(0);
      8.    return null;
      9. }
      11. var node = new BinaryTree() { Data = arr[0] };
      13. arr.RemoveAt(0);
      14. Create(arr);
      15. Create(arr);
      17. return node;
      18. }

    • 如此一来，上述的递归函数最终会返回最外层，也就是第一次遍历的结果。该结果是整个二叉树的根节点。其余新建的node虽被返回了，但返回之后没有对这些返回值有任何操作，所以其余的node暂时都被扔掉了。

  • 接下来，我们就需要思考如何将其余的node存起来，并与上一个节点构建父子关系。
  • 通过两次对Create自身的调用我们可以得知这是两条遍历路径，遍历路径的变换由路径变换条件决定。除了第一遍历层外，其余遍历层的所有返回值都会在前一遍历层的递归函数调用中返回出来。
  • 在上面的代码中，我们暂时还没有对Create的调用后的返回值有任何操作。

  • 下面，考虑到前序遍历的顺序，左在前，右在后、又考虑到所有返回的node节点都是上一次遍历过程中新建的node节点的子节点，所以，我们只需要把这些返回的子节点赋予到前面新建的node节点的左右节点中即可：

    1. BinaryTree Create(Lsit<int?> arr)
    2. {
    3.   if(arr == null || arr.Count == 0) return null;    //出口
    5.   if(arr[0] == null)
    6.   {
    7.       arr.RemoveAt(0);    //递归条件表达式在路径变换条件中的正常执行
    8.       return null;
    9.   }
    11.   var node = new BinaryTree() { Data = arr[0] };
    13.   //递归函数表达式
    14.   arr.RemoveAt(0);    //递归条件表达式
    15.   node.LeftNode = Create(arr);
    16.   node.RightNode = Create(arr);
    17.   //- End -
    19.   return node;
    20. }