将二元查找树转变为排序双向链表|微软经典面试题解析

---答题基础知识储备---


二元树(二叉树):在计算机科学中,二叉树指的是每个节点最多只能有两个子树的树结构,二叉树的两个子树有左右之分,次序不能颠倒,通常两个子树分别被称为左子树和右子树;

遍历二叉树:遍历是对树的一种最基本运算,所谓遍历二叉树,就是按照某一顺序,走完二叉树的所有节点,使每个节点都会被访问一次,且只被访问一次。由于二叉树非线性结构,遍历性质上其实就是将二叉树转化为线性序列来表示。

设L、D、R分别表示遍历左子树、访问根节点、遍历右子树,则对一棵二叉树的遍历有三种情况:DLR(先根次序遍历,先序遍历)、LDR(中根次序遍历,中序遍历)、LRD(后根次序遍历,后序遍历)。

另外的,还有层次遍历:即按照上下层次来进行访问,由上至下,由左至右,先访问根节点,然后访问子节点,然后访问子节点的子节点...越往下,层次越低,两个子节点层次相等;通常使用队列来实现。

层次遍历队列实现原理:1.初始化,将第一个节点压入队列;2.弹出当前队列第一个元素;3.判断这个元素的左右子节点,如果存在则由左到右压入;4.继续2的步骤,直到队列中没有元素。

二元查找树:一种为了“查找”的诞生的二叉树,在二元查找树的每一个单位二叉树中,左子节点 < 根节点 < 右子节点;主要用于快速查找,结果大于根节点->右子节点,结果小于根节点->左子节点,直到找到合适的值为止。

------

题目:

输入一棵二元查找树,将该二元查找树转化为一个排序的双向链表;要求不能创建新的节点,只调整指针的指向。

示例输入:

    10
    / \
 6     14
/ \    / \
4 8  12 16

转换成双向链表输出:

4=6=8=10=12=14=16

首先,我们定义的二元查找树节点的数据结构如下:

struct BSTreeNode  
{  
  int m_nValue; // value of node  
  BSTreeNode *m_pLeft; // left child of node  
  BSTreeNode *m_pRight; // right child of node  
};


答题分析:

本题要求是将输入的树结构转化为链表结构,所以可以使用遍历来实现;同时,本题要求对输入树元素进行排序,根据二元查找树的特性(左>根>右),应当使用中序遍历来实现。


解答:

BSTreeNode *pHead = NULL;
BSTreeNode *pListIndex=NULL;
//中序遍历二元树
void ergodicBSTree(BSTreeNode * pCurrent){
    if(pCurrent == NULL){return ;}
    //左子树不为空
    if(pCurrent->m_pLeft!=NULL){
        ergodicBSTree(pCurrent->m_pLeft);
    }
    //将节点加入链表
    convertToDoubleList(pCurrent);
    //右子树不为空
    if(pCurrent->m_pRight!=NULL){
        ergodicBSTree(pCurrent->m_pRigth);
    }
}
//将二叉树转化成List
void converToDoubleList(BSTreeNode * pCurrent){
    // 当前链表元素的左指针指向前一个元素
    pCurrent->m_pLeft = pListIndex;
    if(pListIndex!=NULL){
        // 如果不是第一个元素  前一个元素的右指针指向当前元素
        pListIndex->m_pRight=pCurrent;
    }else{
        //头指针
        pHead = pCurrent;
    }
    // 将pListIndex赋值为当前指针
    pListIndex = pCurrent;
    cout<<pCurrent->m_nValue<<endl;
}




评论

海绵体大战括约肌:楼主功底不错,写得很好
10月21日 01:23
布耀布耀德:好文要多读几遍,并实践
10月21日 02:38
匿名用户:文章写的真棒!
10月21日 03:42
唐尸三摆手:好文,期待后续~~~
10月21日 06:27
这个手刹不太灵:感谢感谢!看完茅塞顿悟!
10月21日 06:55
北落师门:看起来不错~~
10月21日 07:20
我老公:幸苦了,写的很好。
10月21日 09:09
辇道增七:期待你的更新
10月21日 09:35
李佳音:好文,特意来顶
10月21日 12:25
李献计:通俗易懂 贊
10月21日 18:38

赞助商