英文:
I'm having trouble in finding out Parent node in Binary Search Tree Java Program
问题
import java.util.*;
public class BSTOR {
static class Node {
int key;
Node left, right, parent;
}
static Node newNode(int item) {
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print("Node : " + root.key + " , ");
if (root.parent == null)
System.out.println("Parent : NULL");
else
System.out.println("Parent : " + root.parent.key);
inorder(root.right);
}
}
static Node insert(Node node, int key) {
if (node == null)
return newNode(key);
if (key < node.key) {
Node lchild = insert(node.left, key);
node.left = lchild;
lchild.parent = node;
} else if (key > node.key) {
Node rchild = insert(node.right, key);
node.right = rchild;
rchild.parent = node;
}
return node;
}
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
public static void main(String[] args) {
{
BSTOR ob = new BSTOR();
System.out.println("Insert the No. of your Employees");
Scanner sc = new Scanner(System.in);
Node root = null;
inorder(root);
int n = sc.nextInt();
int arr[] = new int[n];
System.out.println("Insert the Employee Id's of your Orgn");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
for (int i = 0; i < n; i++) {
System.out.println(arr[i] + "");
}
System.out.println("Insert the Employee ID which you want to search from the Orgn : ");
int x = sc.nextInt();
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Employee not present");
else
System.out.println("Report Manager of Employee");
sc.close();
}
}
}
英文:
This program is to find out the parent node out of the elements given in this array and if no parent node available we need to print the same element.
import java.util.*;
public class BSTOR {
static class Node
{
int key;
Node left, right, parent;
}
// A utility function to create a new BST Node
static Node newNode(int item)
{
Node temp = new Node();
temp.key = item;
temp.left = null;
temp.right = null;
temp.parent = null;
return temp;
}
enter code here
// A utility function to do inorder traversal of BST
static void inorder(Node root)
{
if (root != null)
{
inorder(root.left);
System.out.print("Node : "+ root.key + " , ");
if (root.parent == null)
System.out.println("Parent : NULL");
else
System.out.println("Parent : " + root.parent.key);
inorder(root.right);
}
}
/* A utility function to insert a new Node with
given key in BST */
static Node insert(Node node, int key)
{
/* If the tree is empty, return a new Node */
if (node == null) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node.key)
{
Node lchild = insert(node.left, key);
node.left = lchild;
// Set parent of root of left subtree
lchild.parent = node;
}
else if (key > node.key)
{
Node rchild = insert(node.right, key);
node.right = rchild;
// Set parent of root of right subtree
rchild.parent = node;
}
/* return the (unchanged) Node pointer */
return node;
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
enter code here
public static void main(String[] args) {
// TODO Auto-generated method stub
{
BSTOR ob = new BSTOR();
System.out.println("Insert the No. of your Employees");
Scanner sc= new Scanner(System.in);
Node root = null;
// print iNoder traversal of the BST
inorder(root);
int n = sc.nextInt();
int arr[]=new int[n];
System.out.println("Insert the Employee Id's of your Orgn");
for(int i=0; i<n; i++)
{
arr[i]= sc.nextInt();
}
for(int i=0; i<n; i++)
{
System.out.println(arr[i]+"");
}
System.out.println("Insert the Employee ID which you want to search from the Orgn : ");
int x = sc.nextInt();
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Employee not present");
else
System.out.println("Report Manager of Employee " );
sc.close();
}
}
}
</details>
专注分享java语言的经验与见解,让所有开发者获益!
评论