我在查找二叉搜索树 Java 程序中的父节点时遇到了问题。

huangapple 未分类评论47阅读模式
英文:

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(&quot;Node : &quot;+ root.key + &quot; , &quot;);  
	        if (root.parent == null)  
	        System.out.println(&quot;Parent : NULL&quot;);  
	        else
	        System.out.println(&quot;Parent : &quot; + 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 &lt; node.key)  
	    {  
	        Node lchild = insert(node.left, key);  
	        node.left = lchild;  
	  
	        // Set parent of root of left subtree  
	        lchild.parent = node;  
	    }  
	    else if (key &gt; 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 &gt;= 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] &gt; 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(&quot;Insert the No. of your Employees&quot;);
	    	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(&quot;Insert the Employee Id&#39;s of your Orgn&quot;);
	    	for(int i=0; i&lt;n; i++)
	    	 {
	    		 arr[i]= sc.nextInt(); 
	    	 }
	    	
		    for(int i=0; i&lt;n; i++)
		   	 {
		    	 System.out.println(arr[i]+&quot;&quot;);
		   	 }
	    	System.out.println(&quot;Insert the Employee ID  which you want to search from the Orgn : &quot;); 
	        int x = sc.nextInt(); 
	        int result = ob.binarySearch(arr, 0, n - 1, x); 
	        if (result == -1) 
	            System.out.println(&quot;Employee not present&quot;); 
	        else
	            System.out.println(&quot;Report Manager  of Employee  &quot;   ); 
	        sc.close();
		} 
		}  
	}




</details>


huangapple
  • 本文由 发表于 2020年5月30日 02:22:52
  • 转载请务必保留本文链接:https://java.coder-hub.com/62092423.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定