一，今天我們來(lái)介紹下二叉查找樹(shù)，其定義是這樣子的：

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

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

（3）左、右子樹(shù)也分別為二叉排序樹(shù)；

樹(shù)的定義如下

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é)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹(shù)。若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹(shù)。若子樹(shù)為空，查找不成功，如在遞歸的過(guò)程中遇到與關(guān)鍵字值相等的節(jié)點(diǎn)那么查找成功。

直接上代碼嘍

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é)點(diǎn)，如果找不到，那么直接失敗

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

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

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

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

上代碼嘍：

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

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

沒(méi)什么好說(shuō)的，上代碼：

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)注該公眾號(hào) 會(huì)定期推送一些技術(shù)文章