使用双指针而不是单指针

Question

我正在使用二进制搜索树.

所以,这是用于表示节点的结构:

typedef struct TreeNode
{
int num;
struct TreeNode *left,*right;
}TREENODE;

要在树中插入节点,我有以下方法签名

void InsertNode(TREENODE **root,int data);

在上面的方法中为什么我们需要双指针.我们可以使用单个指针!

我们使用双指针避免重复吗？

Answer 1

不,这是重新平衡的必要条件.重新平衡root后可以更改.

好的,我会扩展.双指针允许您修改指针.那么你的案例中的树根是什么？指针TREENODE.某些操作(如搜索)永远不会修改它.但是某些操作可能需要更改它,以便另一个节点成为新的根节点.因此,他们必须能够访问您以root身份使用的变量.他们可能需要它的一个例子是重新平衡,参见AVL树.