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 老公生日祝福语简短好看