数据结构之二叉查找树

2/10/2017来源:ASP.NET技巧人气:295

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

(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;

}

}

}

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