一，今天我們來介紹下二叉查找樹，其定義是這樣子的：

（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于或等于它的根結(jié)點的值；

（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值；

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

};

二，其查找操作是這樣子的：

如果根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功，如在遞歸的過程中遇到與關(guān)鍵字值相等的節(jié)點那么查找成功。

直接上代碼嘍

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，首先查找給定值的節(jié)點，如果找不到，那么直接失敗

2，如果查找到的節(jié)點的左右子樹均為空，并且父節(jié)點也是空，那么直接把這個節(jié)點置空就可以了。否則直接把該節(jié)點的父節(jié)點的左子節(jié)點或者右子節(jié)點置空

3，如果查找到的節(jié)點的左子樹不是空的，但是右子樹不是空的，那么把該節(jié)點的左子節(jié)點的父節(jié)點指向該節(jié)點的父節(jié)點，（1）：該節(jié)點的父節(jié)點是空的，那么把該樹的根節(jié)點指向該節(jié)點的左子節(jié)點（2）：該節(jié)點的父節(jié)點不是空的，

4，如果查找到的節(jié)點的右子樹不是空的，與上述操作3相反

5，如果既有左子節(jié)點，又有右子節(jié)點，那么先找到其右字數(shù)中最小的節(jié)點，把最小節(jié)點的值復給一個臨時變量，然后遞歸刪除這個最小的節(jié)點，刪完自后，把臨時變量賦值給該節(jié)點的值就可以了。

上代碼嘍：

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，如果根節(jié)點為空，那么直接把新的節(jié)點賦值給根節(jié)點

2，如果值比根節(jié)點小，向左遞歸，否則向右遞歸

沒什么好說的，上代碼：

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;

}

}

}

歡迎掃描關(guān)注該公眾號 會定期推送一些技術(shù)文章