二分搜索树

Question

root = insert(root, key, value);
在二分搜索树中，返回了的节点更新了搜索树的根节点，那么下一次再次插入的时候怎么找到根节点root，我感觉这个root应该是不能改变的吧

Answer 1

liuyubobobo 2017-02-14 21:48:23

root是一个指针，他只是指向一个节点而已。如果我们不能改变root，最开始建立一个空二叉树，root为NULL，当我们添加第一个节点的时候，肯定就要改变root，指向第一个添加的节点啊：）

不过对于二分搜索树来说，确实，一旦添加了一个节点，这个根节点其实不会改变了。但是，如果是平衡二叉树，节点就需要不断移动以保持整棵二分搜索树的平衡，这种情况下，root所指向的根节点就是需要不断变换的。不过平衡二叉树在我们这个课程中没有具体讲解，有兴趣可以查查看：）

理解根节点的变动，也可以以链表为例。链表里的head作为头指针，它所指向的内容是可以变化的。比如，如果我们实现一个在链表起始位置添加元素的方法，那么每次调用这个方法，链表的头指针head所指向的内容都会发生改变。

当然，像我之前所说，对于二分搜索树来说，一旦添加一个节点，根节点其实不会改变了。我们写成这种形式，只是方便递归的书写而已。我们完全可以写一个不需要返回值的递归函数，不妨自己试试看：）