making a correct binary tree

    private void dcHullForUpperHull(List<Point> list, Point p,开发者_如何学Python Point q) {
    List<Point> upperH = new ArrayList<Point>();
    List<Point> lowerH = new ArrayList<Point>();
    int low = 0;
    int high = list.size()-1;

    System.out.println(list);
    if(low<high) {

        Point pivot = list.get((low+high)/2);

        for (Point point : list) {
            boolean bool = Determinate.isPointLeftSide(q, pivot, point);

            if (bool == true ) {
                upperH.add(point);
            }
        }
        for (Point point : list) {
            boolean bool = Determinate.isPointLeftSide(pivot, p, point);
            boolean bool1 = Determinate.isPointOnLine(pivot, p, point);
            if (bool == true || bool1==true) {
                lowerH.add(point);
            }
        }

        System.out.println(pivot.toString());
        System.out.println(upperH.toString());
        System.out.println(lowerH.toString());

        dcHullForUpperHull(upperH, pivot, q);           
        dcHullForUpperHull(lowerH, p, pivot);



    }
}

and it prints:

[X :132.0  Y: 140.0angle0.0, X :162.0  Y: 116.0angle0.0, X :210.0  Y: 112.0angle0.0, `enter code here`X:258.0  Y: 117.0angle0.0]
X :162.0  Y: 116.0angle0.0
[X :210.0  Y: 112.0angle0.0, X :258.0  Y: 117.0angle0.0]
[X :132.0  Y: 140.0angle0.0, X :162.0  Y: 116.0angle0.0]
[X :210.0  Y: 112.0angle0.0, X :258.0  Y: 117.0angle0.0]
X :210.0  Y: 112.0angle0.0
[X :258.0  Y: 117.0angle0.0]
[X :210.0  Y: 112.0angle0.0]
[X :258.0  Y: 117.0angle0.0]
[X :210.0  Y: 112.0angle0.0]
[X :132.0  Y: 140.0angle0.0, X :162.0  Y: 116.0angle0.0]
X :132.0  Y: 140.0angle0.0
[]
[X :132.0  Y: 140.0angle0.0]
[]
[X :132.0  Y: 140.0angle0.0]

And it is clear that my binary tree is not OK!! also a method "isPointLeftSide" will say that the point is left of one line with its determinate.But my main problem is that : the binary tree is not OK.and I will have some empty external nodes. please help me thanks

This code doesn't make a binary tree. It is almost quicksorting (well, you do the pivot, the partition and the recursive call, but don't put the sorted list together again; hence almost) the original list. Can you specify what you actually are thinking of doing?

You can see a perfect example of a working unbalanced binary tree at Litterate Programs. But you know, if i were you, i would instead use either TreeSet or TreeMap, which are perfect implementations, provided you give them a valid comparator, which you already have written, in one form or one another.

Thins kind of thing is almost impossible to debug just by looking at it. I suggest writing a validation method that checkes the tree structure for correctness, then calling it after each operation on the tree. That should help you pinpoint when and where exactly things go wrong.

This is the code i used to implement binary tree and its operations:

<?php

class Node { public $data; public $leftChild; public $rightChild;

public function __construct($data) { $this->data=$data; $this->leftChild=null; $this->rightChild=null; } public function disp_data() { echo $this->data; }

}//end class Node class BinaryTree { public $root; //public $s; public function __construct() { $this->root=null; //$this->s=file_get_contents('store');

} //function to display the tree public function display() { $this->display_tree($this->root);

} public function display_tree($local_root) {

if($local_root==null) return; $this->display_tree($local_root->leftChild); echo $local_root->data."
"; $this->display_tree($local_root->rightChild);

} // function to insert a new node public function insert($key) { $newnode=new Node($key); if($this->root==null) { $this->root=$newnode; return; } else { $parent=$this->root; $current=$this->root; while(true) { $parent=$current; //$this->find_order($key,$current->data); if($key==($this->find_order($key,$current->data))) { $current=$current->leftChild; if($current==null) { $parent->leftChild=$newnode; return; }//end if2 }//end if1 else { $current=$current->rightChild; if($current==null) { $parent->rightChild=$newnode; return;
} //end if1
} //end else }//end while loop }//end else

} //end insert function

//function to search a particular Node public function find($key) { $current=$this->root; while($current->data!=$key) { if($key==$this->find_order($key,$current->data)) { $current=$current->leftChild; } else { $current=$current->rightChild; } if($current==null) return(null);

      }
     return($current->data); 

}// end the function to search public function delete1($key) { $current=$this->root; $parent=$this->root;

$isLeftChild=true;
 while($current->data!=$key)
      {
       $parent=$current;
       if($key==($this->find_order($key,$current->data)))
         {
          $current=$current->leftChild;
          $isLeftChild=true;
         }   
       else
         {
          $current=$current->rightChild;
          $isLeftChild=false;   
         } 
        if($current==null)
          return(null);
      }//end while loop 

  echo "<br/><br/>Node to delete:".$current->data;
 //to delete a leaf node 
 if($current->leftChild==null&&$current->rightChild==null)
   {
       if($current==$this->root)
          $this->root=null;  
      else if($isLeftChild==true)
       {
        $parent->leftChild=null;
       }  
     else
       {
        $parent->rightChild=null;
       }
     return($current);       
   }//end if1
 //to delete a node having a leftChild 

else if($current->rightChild==null) { if($current==$this->root) $this->root=$current->leftChild; else if($isLeftChild==true) { $parent->leftChild=$current->leftChild; } else { $parent->rightChild=$current->leftChild; }
return($current); }//end else if1 //to delete a node having a rightChild else if($current->leftChild==null) { if($current==$this->root) $this->root=$current->rightChild; else if($isLeftChild==true) { $parent->leftChild=$current->rightChild; }
else { $parent->rightChild=$current->rightChild; }
return($current); }
//to delete a node having both childs else { $successor=$this->get_successor($current); if($current==$this->root) { $this->root=$successor;

      }
    else if($isLeftChild==true)
      {
       $parent->leftChild=$successor;
      }
    else
      {
       $parent->rightChild=$successor;
      }     
     $successor->leftChild=$current->leftChild;
    return($current);
   }   

}//end the function to delete a node //Function to find the successor node public function get_successor($delNode) { $succParent=$delNode; $successor=$delNode; $temp=$delNode->rightChild; while($temp!=null) { $succParent=$successor; $successor=$temp; $temp=$temp->leftChild; } if($successor!=$delNode->rightChild) { $succParent->leftChild=$successor->rightChild; $successor->rightChild=$delNode->rightChild; } return($successor); } //function to find the order of two strings public function find_order($str1,$str2) { $str1=strtolower($str1); $str2=strtolower($str2); $i=0; $j=0;

 $p1=$str1[i];
 $p2=$str2[j]; 

while(true) {
if(ord($p1)

       return($str1);
     }
  else
     {
       if(ord($p1)==ord($p2))
         {
          $p1=$str1[++$i];
          $p2=$str2[++$j];
          continue;
         }
      return($str2); 
     }

}//end while

} //end function find string order

public function is_empty() { if($this->root==null) return(true); else return(false); } }//end class BinaryTree ?>