数据结构之二叉查找树

一，今天我们来介绍下二叉查找树，其定义是这样子的：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

树的定义如下

typedef struct node

{

int         data;

struct node     *parent;

struct node     *left;

struct node     *right;

}Node;

class Tree

{

public:

Tree()

{

m_root = NULL;

}

int insertTree(int x)

{

return insert(m_root, x);

}

Node* findTree(int x)

{

return find(m_root, x);

}

int delTree(int x)

{

return delnode(m_root, x);

}

PRivate:

int insert(Node* &node, int x);

Node* find(Node* node, int x);

int delnode(Node* &node, int x);

private:

Node    *m_root;

};

二，其查找操作是这样子的：

如果根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功，如在递归的过程中遇到与关键字值相等的节点那么查找成功。

直接上代码喽

Node* Tree::find(Node* node, int x)

{

if(node == NULL)

{

return NULL;

}

if(x<node->data)

{

return find(node->left, x);

}

else if(x>node->data)

{

return find(node->right, x);

}

else

{

return node;

}

}

三，其删除操作是这样子的

1，首先查找给定值的节点，如果找不到，那么直接失败

2，如果查找到的节点的左右子树均为空，并且父节点也是空，那么直接把这个节点置空就可以了。否则直接把该节点的父节点的左子节点或者右子节点置空

3，如果查找到的节点的左子树不是空的，但是右子树不是空的，那么把该节点的左子节点的父节点指向该节点的父节点，（1）：该节点的父节点是空的，那么把该树的根节点指向该节点的左子节点（2）：该节点的父节点不是空的，

4，如果查找到的节点的右子树不是空的，与上述操作3相反

5，如果既有左子节点，又有右子节点，那么先找到其右字数中最小的节点，把最小节点的值复给一个临时变量，然后递归删除这个最小的节点，删完自后，把临时变量赋值给该节点的值就可以了。

上代码喽：

int Tree::delnode(Node* &node, int x)

{

int temp;

Node *find_node = findTree(x);

if(!find_node)

{

return -1;

}

else if(find_node->left==NULL && find_node->right==NULL)

{

if(find_node->parent==NULL)

{

cout << "delete root" << endl;

free(find_node);

node=NULL;

}

else

{

cout << "delete root not null" << endl;

if(find_node->parent->left->data == x)

{

find_node->parent->left = NULL;

}

else

{

find_node->parent->right = NULL;

}

}

}else if(find_node->left!=NULL && find_node->right==NULL)

{

cout << "delete left not null" << endl;

find_node->left->parent = find_node->parent;

if(find_node->parent == NULL)

{

node = find_node->left;

}

else

{

find_node->parent->left = find_node->left;

}

ree(find_node);

}

else if(find_node->right!=NULL && find_node->left==NULL)

{

         cout << "delete right not null" << endl;

           find_node->right->parent = find_node->parent;

if(find_node->parent == NULL)

{

node = find_node->right;

}

else 

{

find_node->parent->right = find_node->right;

}

free(find_node);

}

else

{

               Node *p = find_node->right;

while(p->left)

{

p = p->left;

}

int min_data = p->data;

delnode(node, min_data);

find_node->data = min_data;

}

return 0;

}

四，插入操作的步骤：

1，如果根节点为空，那么直接把新的节点赋值给根节点

2，如果值比根节点小，向左递归，否则向右递归

没什么好说的，上代码：

int Tree::insert(Node* &node, int x)

{

if(node == NULL)

{

cout << "insert null" << endl;

Node *p = (Node *)malloc(sizeof(Node));

p->left = NULL;

p->right= NULL;

p->parent = NULL;

p->data = x;

node = p;

return 0;

}

else

{

if(node->left==NULL && x<node->data)

{

Node *p = (Node *)malloc(sizeof(Node));

p->left = NULL;

p->right= NULL;

p->parent = node;

p->data = x;

node->left = p;

return 0;

}

else if(node->right==NULL && x>node->data)

{

Node *p = (Node *)malloc(sizeof(Node));

p->left = NULL;

p->right= NULL;

p->parent = node;

p->data = x;

node->right = p;

return 0;

}

else if(x<node->data)

{

insert(node->left, x);

}

        else if(x>node->data)

{

insert(node->right, x);

}else

{

return -1;

}

}

}

欢迎扫描关注该公众号 会定期推送一些技术文章