C ++中带有父指针的二进制搜索树插入
我们可以以递归方式将新节点插入BST。在这种情况下，我们返回每个子树的根地址。在这里，我们将看到另一种方法，其中需要维护父指针。父指针将有助于找到节点的祖先等。
这个想法是存储左和右子树的地址，我们在递归调用之后设置返回的指针的父指针。这确认在插入期间设置了所有父指针。root的父级设置为null。
算法
插入（节点，键）-
begin
if node is null, then create a new node and return
if the key is less than the key of node, then
create a new node with key
add the new node with the left pointer or node
else if key is greater or equal to the key of node, then
create a new node with key
add the new node at the right pointer of the node
end if
return node
end示例
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *left, *right, *parent;
};
struct Node *getNode(int item) {
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = temp->parent = NULL;
return temp;
}
void inorderTraverse(struct Node *root) {
if (root != NULL) {
inorderTraverse(root->left);
cout << root->data << " ";
if (root->parent == NULL)
cout << "NULL" << endl;
else
cout << root->parent->data << endl;
inorderTraverse(root->right);
}
}
struct Node* insert(struct Node* node, int key) {
if (node == NULL) return getNode(key);
if (key < node->data) { //to the left subtree
Node *left_child = insert(node->left, key);
node->left = left_child;
left_child->parent = node;
}
else if (key > node->data) { // to the right subtree
Node *right_child = insert(node->right, key);
node->right = right_child;
right_child->parent = node;
}
return node;
}
int main() {
struct Node *root = NULL;
root = insert(root, 100);
insert(root, 60);
insert(root, 40);
insert(root, 80);
insert(root, 140);
insert(root, 120);
insert(root, 160);
inorderTraverse(root);
}输出结果
40 60 60 100 80 60 100 NULL 120 140 140 100 160 140
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短