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