java生成正确的二叉树

Question

    private void dcHullForUpperHull(List<Point> list, Point p, 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);



    }
}

它会打印：

[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]

很明显，我的二叉树是不好的！！还有一种方法"isPointLeftSide"会说该点位于一条直线的左侧，且其确定值为。但我的主要问题是：二叉树是不好的。我将有一些空的外部节点。 请帮帮我 谢谢

Answer 1

这种事情几乎不可能仅仅通过查看它来调试。我建议编写一个验证方法来检查树结构的正确性，然后在树上的每个操作之后调用它。这将有助于你准确地指出事情到底何时何地出了问题

Answer 2

您可以在Litterate Programs处看到一个工作不平衡二叉树的完美示例。 但是你知道，如果我是你，我会使用TreeSet或TreeMap，它们都是完美的实现，只要你给它们一个有效的比较器，你已经以一种或另一种形式编写了这个比较器

Answer 3

这段代码不构成二叉树。它几乎是对原始列表进行快速排序（好吧，您可以执行pivot、partition和递归调用，但不要再将排序列表放在一起；因此几乎是）。你能具体说明你实际上想做什么吗

Answer 4

这是我用来实现二叉树及其操作的代码：

<?php

类节点 { 公共数据； 公共儿童； 公共儿童基金会

公共函数构造（$data） { $this->；data=$data； $this->；leftChild=null； $this->；rightChild=null； } 公共函数disp_data（） { echo$this->；数据 }

}//结束类节点 类二叉树 { 公共$root； //公帑＄s； 公共函数构造（） { $this->；root=null； //$this->；s=文件获取内容（“存储”）

} //函数来显示树 公共功能显示（） { $this->；显示树（$this->；root）

} 公共函数显示树（$local\u root） {

if（$local_root==null） 回来 $this->；显示目录树（$local\u root->；leftChild）； echo$local_root->；数据“
”； $this->；显示目录树（$local\u root->；rightChild）

} //函数插入新节点 公共功能插入（$key） { $newnode=新节点（$key）； 如果（$this->；root==null） { $this->；root=$newnode； 回来 } 其他的 { $parent=$this->；根 $current=$this->；根 while（true） { $parent=$current； //$this->；查找订单（$key、$current->；数据）； 如果（$key==（$this->；查找订单（$key，$current->；数据））） { $current=$current->；左撇子； 如果（$current==null） { $parent->；leftChild=$newnode； 回来 }//结束if2 }//结束if1 其他的 { $current=$current->；右孩； 如果（$current==null） { $parent->；rightChild=$newnode； 返回
}//结束if1
}//结束其他 }//边结束边循环 }//结束其他

}//结束插入函数

//用于搜索特定节点的函数 公共函数查找（$key） { $current=$this->；根 while（$current->；data！=$key） { 如果（$key==$this->；查找订单（$key$current->；数据）） { $current=$current->；左撇子； } 其他的 { $current=$current->；右孩； } 如果（$current==null） 返回（空）

      }
     return($current->data); 

}//结束要搜索的函数 公共函数delete1（$key） { $current=$this->；根 $parent=$this->；根

$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） { 如果（$current==$this->；root） $this->；root=$current->；左撇子； else if（$isLeftChild==true） { $parent->；leftChild=$current->；左撇子； } 其他的 { $parent->；rightChild=$current->；左撇子； }
回报（当前）； }//如果1，则结束 //删除具有rightChild的节点的步骤 else if（$current->；leftChild==null） { 如果（$current==$this->；root） $this->；root=$current->；右孩； else if（$isLeftChild==true） { $parent->；leftChild=$current->；右孩； }
其他的 { $parent->；rightChild=$current->；右孩； }
回报（当前）； }
//删除同时具有两个子节点的节点 其他的 { $succession=$this->；获取继任者（$current）； 如果（$current==$this->；root） { $this->；root=$succession

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

}//结束删除节点的函数 //函数以查找后续节点 公共函数get_后继（$delNode） { $succParent=$delNode； $successiver=$delNode； $temp=$delNode->；右孩； while（$temp！=null） { $succParent=$SUCCURENT； $succession=$temp； $temp=$temp->；左撇子； } 如果（$succession！=$delNode->；rightChild） { $succParent->；leftChild=$succession->；右孩； $继任者->；&DelRightNode=$RightNode；右孩； } 回报（继任者）； } //函数查找两个字符串的顺序 公共函数查找顺序（$str1，$str2） { $str1=strtolower（$str1）； $str2=strtolower（$str2）； $i=0； $j=0

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

while（true） {
如果（作战需求文件（$p1）

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

}//结束时

}//结束函数查找字符串顺序

公共函数为_empty（） { 如果（$this->；root==null） 返回（真）； 其他的 返回（假）； } }//端类二叉树 ?&燃气轮机