JAva二叉ソートツリー検索挿入親ノードアルゴリズム

説明、Tはこのツリーのルートであり、keyは検索するキーワードであり、fは現在のノードの親ノードを格納するために使用され、pはkeyが見つかった場合、keyは現在のノードであるが、見つからなかった場合、現在のこの空のノードの親ノードfであることを示す
検索に成功したらtrueを返し、失敗したらfalseを返し、新しいノードをfの子供に挿入します.

boolean Search(BiTree T, int key, BiTree f, BiTree p)
{
    if(T==null)
    {
        p == f;
        return false;
    }
    if(T.data == key)
    {
        p == T;
        return true;
    }
    else if(T.data > key)
    {
           return Search(T.lchild,key,T,p);
     }
     else
    {
           return Search(T.rchild,key,T,p);
    }
}

ノードを動的に挿入し、ツリーを作成する

boolean Insert(BiTree T, int key)
{
    if(!Search(T,key,null,p))
    {
        BiTree e = new BiTree(key);
        if(p==null)//  f null，           
       {
         T = e;
       }
        else if(p.data > key)
                     p.lchild = e;
               else
                     p.rchild = e;
      retrun true;
    }else{

 return false //       node

}
    
}

    //親ノードを求める、ノードクラスBSTreeNodeを定義する際には、親ノードを明示していないので、ここではわざわざparentを用いて親ノード

を出力する.

    public BSTreeNode parent(BSTreeNode k){  

        BSTreeNode p=rootNode;  

        BSTreeNode tmp=null;  

        while(p!=null&&p.data!=k.data){//最後のpはp.dataはk.dataのノードに等しく、tmpはpの親ノードである  

            if(p.data>k.data){  

                tmp=p;//父親ノードを一時保存  

                p=p.left;  

            }else{  

                tmp=p;//父親ノードを一時保存  

                p=p.right;  

            }  

        }  

        return tmp;  

    }