一，今天我们来介绍下二叉查找树，其定义是这样子的：
（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;
}
}
}
欢迎扫描关注该公众号 会定期推送一些技术文章
