Как написать код для «addToRightMostChildAsLeftChild (Node a, Node b)»?

Question

Допустим, у приведенного выше метода есть два аргумента a and b:

• a : представляет корневой узел дерева, для которого нам нужно пройти, пока мы не получим правильноеузел
• b : представляет узел, который будет добавлен к крайнему правому узлу как левый дочерний элемент.

Мне просто нужно знать, как добавить `узел к самому правому узлу дерева, но как левый потомок .Я на самом деле решаю другую версию этой проблемы.Здесь проблема заключается в использовании правых указателей .

Построить дерево таким образом, чтобы при обходе его только через левые указатели генерировалось обхода предварительного заказа дерева.

На самом деле это может быть решено путем обхода дерева и поддержания previous node and linking them in the way we want : prev.left = current`.

Мой способ решения этой проблемы: Если естьДерево выглядит следующим образом

(просто добавьте узлы 2–5 в качестве левого потомка, затем 5–3 в качестве левого потомка и, наконец, 6–4 в качестве левого потомка.)

                 10
                 / \
                8   2
               / \ / \
              3  5 4  6


               10
               /
              8
             / \
            3   5
               /
              2
             / \
            4   6

             10
             /
            8
           / 
          3
         /
        5
       /
      2 
     / \
    4   6
             10
             /
            8
           / 
          3
         /
        5
       /
      2
     /
    4
   /
  6

10 83 5 2 4 6 который является pre-order traversal дерева

Я знаю, что это можно сделать с помощью указателя prev и выполнения чего-либо.Я хочу, чтобы это было сделано следующим образом.

                 10        
                 / \
                8   2      
               / \ / \
              3  5 4  6

                 ||
                 \/

                10
               /
              8
             / 
            3
           /
          5
         /
        2
       /
      4
     /
    6

Узел определен как:

 class Node{
    int data;
    Node left,right;
    Node(int d)
    {
        data=d;
        left=null;
        right=null;
    }
}

Answer 1

Подумав, я смог это сделать.

void addToRightMostNodeAsLeftChild(Node root,Node toBeAdded)
{
    if(root.left==null)
    {
        root.left=toBeAdded;
    }
    else
    {
        Node k=getRMNode(root.left);
        if(k.left==null)
        {
            k.left=toBeAdded;
        }
        else
            addToRightMostNodeAsLeftChild(k, toBeAdded);
    }
    root.right=null;
}

Итак, когда я хочу разместить узел 2 как левого потомка из 5, то есть самый правый узел узла 8 (здесь добавляется как левый дочерний элемент к самому правому узлу некоторого узла XYZ, здесь XYZ равен 8) Когда метод вызывается следующим образом:

addToRightMostNodeAsLeftChild(root,X) /*root represents node 10 and X represents node 2*/

он получаетпреобразуется в:

           10
           /
          8
         / \
        3   5
           /
          2
         / \
        4   6