Тема: Інфіксний вивід бінарного дерева пошуку
Добрий день,прошу допоможіть будь ласка дописати код.Терміново сьогодні потрібно здати.
Було завдання:Написати програму, яка створює збалансоване бінарне дерево. Написати процедуру, яка друкує (за один раз) всі вершини дерева.
Сказали зробити інфіксний вивід бінарного дерева,щоб було видно,що дерево збалансоване.Я не зовсім розумію,як зробити інфіксний вивід до цього коду.
class Node{
int key, height;
Node left, right;
public Node(int data) {
key=data;
height=1;
}
}
public class AVLTree {
Node root;
private int height(Node node) {
if (node == null)
return 0;
return node.height;
}
private int max(int a, int b) {
return (a > b) ? a : b;
}
/*
* В наступному методі відбувається
* правий поворот.
*/
private Node rightRotate (Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return x;
}
private Node leftRotate (Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}
private int getBalance(Node node) {
if (node == null) {
return 0;
}
return height(node.left) - height(node.right);
}
private Node insert(Node node, int key) {
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;
node.height = max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
if (balance > 1 && key < node.left.key)
return rightRotate(node);
if (balance < -1 && key > node.right.key)
return leftRotate(node);
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
private void preOrder(Node node) {
if(node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Дерево роздруковується в "
+ "наступному порядку: Корінь(30) -> Ліве Піддерево(20,10)"
+ " -> Праве Піддерево кореня 20(25)"+" -> Праве Піддерево(40,50)");
/*
30
/ \
20 40
/ \ \
10 25 50
*/
tree.preOrder(tree.root);
}
}