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 宝宝新年祝福语大全简短