Итак, вот класс Node:
public class Node
{
private int _info;
private Node _left;
private Node _right;
public Node()
{
//this._info = Integer.MIN_VALUE;
this._left = null;
this._right = null;
}
public int getInfo()
{
return _info;
}
public void setInfo(int _info)
{
this._info = _info;
}
public Node getLeft()
{
return _left;
}
public void setLeft(Node _left)
{
this._left = _left;
}
public Node getRight()
{
return _right;
}
public void setRight(Node _right)
{
this._right = _right;
}
}
Как создать дерево:
public class BalancedBinaryTree
{
private ArrayList<Integer> _numbers;
private Node _root;
public BalancedBinaryTree(ArrayList<Integer> numbers)
{
this._numbers = new ArrayList<>();
this._numbers.addAll(numbers);
Collections.sort(this._numbers);
this._root = new Node();
this.create(this._root, 0, this._numbers.size());
}
private void create(Node tree, int i, int j)
{
if (i < j)
{
int m = i + (j - i) / 2;
tree.setInfo(this._numbers.get(m));
tree.setLeft(new Node());
create(tree.getLeft(), i, m);
tree.setRight(new Node());
create(tree.getRight(), m + 1, j);
}
}
Этот метод вычисляет глубину:
public static int getDepth(Node node)
{
if (node == null)
{
return 0;
}
else
{
int max = 0;
if (getDepth(node.getLeft()) > getDepth(node.getRight()))
{
max = getDepth(node.getLeft());
}
else
{
max = getDepth(node.getRight());
}
return max + 1;
}
}
И эти два вместе должны напечатать дерево по его уровням:
public static void printLevel(Node node, int levelToDisplay, int currentLevel)
{
if (node != null)
{
printLevel(node.getLeft(), levelToDisplay, currentLevel);
if (currentLevel == levelToDisplay)
{
System.out.print(node.getInfo() + " ");
}
currentLevel++;
printLevel(node.getRight(), levelToDisplay, currentLevel);
}
}
public static void printLevels(Node node)
{
for (int i = 0; i < getDepth(node); i++)
{
System.out.println("Level :" + i);
printLevel(node, i, 0);
System.out.println();
}
}
В тестовом классе у меня есть:
testNumbers.add(15);
testNumbers.add(20);
testNumbers.add(25);
testNumbers.add(30);
testNumbers.add(35);
testNumbers.add(40);
testNumbers.add(45);
BalancedBinaryTree tree = new BalancedBinaryTree(testNumbers);
BalancedBinaryTree.printLevels(tree.getRoot());
И я получаю этот вывод:
Level :0
0 15 20 30
Level :1
0 0 25 0 35 40
Level :2
0 0 0 45
Level :3
0
Я должен получить
Level :0
30
Level :1
20 40
Level :2
15 25 35 45
- Что не так с методом
getDepth, поскольку кажется, что он возвращает 4 уровня вместо 3?
- Почему существуют дополнительные узлы? (эти нули)
Я почти уверен, что решил проблемы, но мне понадобится объяснение следующего:
Это модифицированный printlevel метод:
public static void printLevel(Node node, int levelToDisplay, int currentLevel)
{
if (node.getLeft() != null && node.getRight() != null)
{
printLevel(node.getLeft(), levelToDisplay, currentLevel+1);
if (currentLevel == levelToDisplay)
{
System.out.print(node.getInfo() + " ");
}
printLevel(node.getRight(), levelToDisplay, currentLevel+1);
}
}
Как вы можете видеть, я проверяю, есть ли у текущего узла дочерние элементы, вместо того, чтобы проверять, существует ли текущий узел, и именно поэтому эти нули появляются, потому что обход достиг листьев, у которых не было информации, назначенной для их правого и левого дочерних элементов.
Вещь, которую я хочу понять, - это разница между увеличением currentLevel и последующей передачей его на вызов printLevel и простой передачей currentLevel+1 на вызов. Разве это не должно быть то же самое?
И функция getDepth:
public static int getDepth(Node node)
{
if (node.getLeft() == null && node.getRight() == null)
{
return 0;
}
else
{
int max = 0;
if (getDepth(node.getLeft()) > getDepth(node.getRight()))
{
max = getDepth(node.getLeft());
}
else
{
max = getDepth(node.getRight());
}
return 1 + max;
}
}
То же самое и здесь: прохождение достигло листьев и получило еще один вызов для своих потомков, возвращая, таким образом, один дополнительный уровень, так что снова, решение состоит в том, чтобы проверить, есть ли у текущего узла потомки, а не проверять, выходит ли текущий узел.