#java #binary-tree #traversal
#java #двоичное дерево #обход
Вопрос:
Допустим, приведенный выше метод имеет два аргумента a and b :
- a: представляет корневой узел дерева, для которого нам нужно пройти, пока мы не получим правильный узел
- b: представляет узел, который будет добавлен к самому правому узлу a в качестве левого дочернего элемента.
Мне просто нужно знать, как добавить `узел к самому правому узлу дерева, но как левый дочерний элемент. На самом деле я решаю другую версию этой проблемы. Здесь проблема заключается в использовании правильных указателей.
Постройте дерево таким образом, чтобы его обход только через левые указатели генерировал предварительный обход дерева.
На самом деле это можно решить, пройдя по дереву и сохранив 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 8 3 5 2 4 6 какой pre-order traversal из дерева
Я знаю, что это можно сделать, используя `предыдущий указатель и выполняя другие действия. Я хочу, чтобы это было сделано таким образом.
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;
}
}
Комментарии:
1. На каком языке?
2. @ZainArshad Это на Java
3. вы пробовали что-нибудь?
4. void addToEnd(узел a, узел b) { if(a.right== null) a.right = b; else addToEnd(a.right, b) ; } // Я пытался добавить его в конце, но как правильный потомок
5. ну, я просто его кодировал… хахахаа рад, что ты решил это.. вы можете поделиться решением в ответе!
Ответ №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