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

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

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

设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;
}