关于二叉检索树（BST）的一些问题

比眉伴天荒 2021-11-17 12:48 246阅读 0赞

1，给定一个BST，其中的节点出了key和左右孩子指针left,right之外，还有另一个指针neighbour，当前BST中所有节点的neighbour指针全部为空，要求写一个算法，能够将所有指针neighour指向其相邻的右兄弟节点(最右边的兄弟指向下一层最左边的孩子节点)。

解答：感觉这个题目应该是二叉树层序遍历的一个应用，二叉树层序遍历其实是图广度优先搜索BFS的一个特殊情况。利用一个先进先出队列即可实现，算法如下：

Set\_Neighbour(Node\* root)

//我们定义一个队列，它支持进队enqueue和出队dequeue操作，还有判断队列是否为空的的操作isEmpty

> Queue queue;

> if ( root == NULL)

> > return;
> 
> queue.enqueue(root);

> Node \*pre = NULL;    //表示当前访问节点的前一个节点

> Node \*curr = NULL;  //表示当前访问的节点

> while( ! queue.isEmpty() )

> \{

> > curr=queue.dequeue();
> 
> > if( pre != NULL )

> > > pre -> neighbour = curr;

> > if( curr -> left != NULL)

> > > queue.enqueue(curr -> left);

> > if( curr -> right != NULL)

> > > queue.enqueue(curr -> right);

> > pre = curr;    //更新pre指针

> \}

2，给定一个BST，写一个算法以这个BST为输出，要求输出一个有序链表，(假设每个节点只有关键字域key和指向左右孩子的指针left和right)。

解答：这个题目起始是二叉检索树中序遍历的一个应用，我们知道二叉检索树的中序遍历输出的是一个有序序列，我们只需要把这个序列建成链表即可。但要注意，我们在建立链表的时候，每次都是从链表头插入一个元素，然后更新链表头，如果是按照常规的中序遍历构建的有序链表将是倒序的（当然我们可以通过O(n)操作的链表自逆来变成升序），所以我们可以在遍历BST的时候遵循先右再根再左的思路来进行，那么得到的序列将会是一个有序（倒序）的序列，我们一次来逐步插入到链表中，所得的链表就是一个升序的有序链表。下面是算法：

build\_List(head,root)   //算法的输入是一个空单向链表的头指针head和一个BST的根节点root

> if (root == NULL)

> > return;

> build\_List(head, root -> right);
> 
> //中序访问的过程，即向链表中插入节点的过程
> 
> Node \*val= new Node( root -> key)  //新建立一个链表元素节点，并把当前节点的key值复制进相应的key域
> 
> if (head == NULL)

> > head = val;

> else
> 
> \{

> > val -> next = head;
> 
> > head = val;

> \}
> 
> build\_List(head, root -> left);

最后得到的以head为头的链表就是一个升序链表。

3，给定两个BST：B1和B2，写一个算法，能够判断这两个树之间是否有重复元素（这里的重复指的是关键字域的重复，不包括指针域）

解答：这个题目打眼看上去就有一个很trivial的解法，就是遍历B1的所有元素，然后在B2中去找，如果找到相同的则返回true，遍历完所有的节点返回false，时间代价是O(n\*log(n))的，算法如下:

bool compare\_BST(B1, B2)  //这里B1和B2分别表示两个BST的根节点，

> if( B1 == NULL)

> > return false;

> //后序遍历B1

> compare\_BST(B1 -> left, B2);

> compare\_BST(B1 -> right, B2);
> 
> //访问当前节点，其实就是在B2中去寻找是否有相同元素  
> 
> 
> Node \*match=binary\_search(B2, B1 -> key);  
> 
> 
> if (match == NULL)
> 
> > return false;
> 
> else
> 
> > return true;

Node\* binary\_search(root, val)   // root为当前树根，val为要寻找的节点对应的关键字

> if(root == NULL || root -> key == val )

> > return root;

> if(val< root -> key)

> > binary\_seach(root -> left, val);

> else

> > binary\_search(root -> right, val);

当然这个问题有比上面的O(n\*log(n))更好的算法。

其实上面这个算法并没有有效利用B1也是一个BST这个性质，我们下面给出的算法可以综合利用这两个BST的性质来同步进行查找，

1，如果当前在第一个BST访问的节点B1比当前在第二个访问的节点B2的关键字小，那么：

1）我们继续遍历B1的右边孩子，B2不变，继续比较，

2）我们继续遍历B2的左孩子，B1不变，继续比较

2，如果当前在第一个BST访问的节点B1比当前在第二个访问的节点B2的关键字大，那么：

1）我们继续遍历B2的右边孩子，B1不变，继续比较，

2）我们继续遍历B1的左孩子，B2不变，继续比较

3，如果两个节点相同，则返回true

bool improved\_binary\_compare(B1, B2)

> if( B1 != NULL && B2 != NULL)
> 
> \{

> > bool left, right;
> 
> > if( B1->key == B2->key)

> > > return true;

> > else
> 
> > \{

> > > //B1和B2不相同的时候，我们既可以沿着左边找匹配，同时又可以沿着右边找匹配，只要两边至少有一个匹配，那么就成功
> 
> > > left=compare\_left(B1, B2);        //子过程，在左边同步比较
> 
> > > right=compare\_right(B1, B2);       //子过程，在右边同步比较
> 
> > > if( left || right)

> > > > return true;

> > \}

> \}
> 
> return false;

bool compare\_left(B1, B2)

> if( B1 != NULL && B2 != NULL)
> 
> \{

> > if( B1->key == B2->key)

> > > return true;

> > else if (B1->key < B2->key)

> > > return compare\_left(B1, B2->left);

> > else

> > > return compare\_left(B1->left, B2);

> \}
> 
> return false