数据结构二进制排序树

//

/ *

二元排序树意味着根节点的左子树小于他，右子树大于他；

注意:

必须指定指针指针，并且不应允许指针随机指向. 这会造成不必要的麻烦. 有时，没有逻辑问题，但是输出存在问题. 指针可能有问题. 例如，我遇到的问题如下:

1;首先，删除5个节点时，没有逻辑问题. 结果输出一直处于1、3、4、10的循环中，问题是在findMIn中指向父节点的指针删除该节点后，未将其设置为NULL，从而导致了这种问题.

* /

使用命名空间标准；

typedef结构节点{

int数据；

node * rchild;

node * lchild;

}节点；

类树{

私人:

节点*头； //树的头节点

节点seachx（节点t，int数据）; //私有递归查询

void insertx（node *＆t，int数据）; //私有递归插入；

无效顺序（节点* p）; //中阶遍历

节点findMin（nodep，节点*父节点）; //在已删除节点的左侧子树中找到最大值，参数一，从该节点开始，参数二，该节点的父节点

bool isLeaf（节点* p）; //看是否是叶子节点

bool deleteNode（节点parnet，nodep，int数据，int方向）; //私有删除节点参数一，从该节点开始，参数二，该节点的父节点，参数三. 删除的数据，参数4，位于其中的子树中，左子树由1表示，右子树用0表示.

bool isHaveLeftChild（节点* p）;

公开

:

void searchTree（int数据）； //私有函数调用私有插入，找到节点

void inserTree（整数* a，整数长度）； //参数1: 将数组的长度作为参数传递给参数2. . 插入一个节点.

void deleteTree（int数据）； //删除节点.

void inorderTree（）;

树（）;

};

布尔树:: isHaveLeftChild（节点* p）{

if（p-> lchild！= NULL && p-> rchild == NULL）{

return true;

}

返回假；

}

树::树（）{

head = NULL;

}

/ *

查找是为了方便二叉树，寻找

* /

节点树:: seachx（node t，int data）{

if（t == NULL）{

return  NULL;

}

其他{

if(t->data == data) return t;
if(t->data < data) t = seachx(t->rchild, data);
if(t->data > data) t = seachx(t->lchild, data);

}

返回t;

}

/ *

Insert实际上实际上是连续插入叶节点，首先找到叶节点二叉排序树是，然后创建节点二叉排序树是，然后插入右侧的大节点和左侧的小节点.

第一个参数是引用的指针，因此无需返回值. 直接连接.

* /

无效树:: :: insertx（node *＆t，int data）{

if（t == NULL）{

t = new node;
t->lchild = t->rchild = NULL;
t->data = data;

}

其他{

if (t->data <data) insertx(t->rchild, data);
if (t -> data > data) insertx(t->lchild, data);

}

}

void Tree :: searchTree（int数据）{

节点* p =头;

p = seachx（p，data）;

cout <

cout <数据;

}

void Tree :: inserTree（整数* a，整数长度）{

for（int i = 0; i

insertx(head, a[i] );

}

}

空树::顺序（节点* p）{

if（p == NULL）{

return;

}

其他{

inorder(p->lchild);
cout<<p->data<<"\n";
inorder(p->rchild);

}

}

void Tree :: inorderTree（）{

节点* p =头;

顺序（p）;

}

节点树:: findMin（节点p，节点*父节点）{

cout <数据<<“ ::” <数据 lchild == NULL）{

//即就是找到了这个结点，然后将父结点的左子树设置为NULL
parent->lchild=NULL;
return p;

}

其他{

//否则就继续找
p = findMin(p->lchild, p);

}

返回p;

}

布尔树:: isLeaf（节点* p）{

if（p-> lchild == NULL && p-> rchild == NULL）{

return true;

}

返回假；

}

/ *

返回值是布尔值，用于判断是否已找到. 如果找不到左子树，请继续找到右子树.

* /

Bool Tree ::删除节点（节点parnet，nodep，int数据，int方向）{

if（p == NULL）{

//设置终止条件。
return false;

}

其他{

cout<<"parent"<<parnet->data<<endl;
cout<<"delete  NOde "<<p->data<<endl;
if(p->data == data){
    if(isLeaf( p) == true){
        //               这个结点是叶子结点
        if(diretcion == 1) {
            //左边
            parnet->lchild = NULL;delete p;
        }
        if(diretcion == 0) {
            //右边
            parnet->rchild = NULL;delete p;
        }
    }
    
    
    if(isHaveLeftChild(p) == true){
        //只有左子树
        if(diretcion == 1) {
            parnet->lchild = p->lchild;delete p;
        }
        if(diretcion == 0) {
            parnet->rchild = p->lchild;delete p;
        }
    }
    else {
        //有右子树
        node *t = findMin(p->rchild,p->rchild);//找到最替换的结点
        cout<<t->data<<endl;
        cout<<parnet->data<<endl;
        if(diretcion == 1) {
            if(p->rchild->lchild == NULL){
                //删除的结点的右子树的左子树 没有。
                parnet->lchild = t;
                cout<<p->data<<endl;
                t->rchild= p->rchild->rchild;
                t->lchild = p->lchild;
                delete p;
            }
            else{
                //要删除的结点的右子树有左子树。
                parnet->lchild = t;
                cout<<p->data<<endl;
                cout<<p->rchild->data<<endl;
                t->rchild= p->rchild;
                t->lchild = p->lchild;
                delete p;
            }
        }
        if(diretcion == 0) {
            if(p->rchild->lchild == NULL){
                parnet->rchild = t;
                t->rchild= p->rchild->rchild;
                t->lchild = p->lchild;
                delete p;
            }
            else{
                parnet->rchild = t;
                t->lchild = p->lchild;
                t->rchild = p->rchild;
                delete p;
            }
        }
        
    }
}
if( data > p->data){
    deleteNode(p, p->rchild, data, 0);
}
if(data < p->data){
    deleteNode(p, p->lchild, data, 1);
}
return true;

}

}

void Tree :: deleteTree（int数据）{

if（true == deleteNode（head，head，data，1））{

return;

}

其他{

deleteNode(head, head, data, 1);

}

}

int main（）{

树a;

int b [] = {28,5,4,16,3,1,29,19,17};

a.inserTree（b，9）;

a.inorderTree（）;

a.searchTree（1）;

a.deleteTree（3）;

cout <<“被删除的节点如下: n”;

a.inorderTree（）;

cout <返回1；

}

测试图片是上面提到的图片.

[二进制排序树-代码云地址]（查找/二进制排序树）

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-169293-1.html