1. 把二元查找树转变成排序的双向链表

把二元查找树转变成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。

'''
解析:
1. 二元查找树是计算机用语，指一棵空树或者具有下列性质的二元树：
    (1). 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
    (2). 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
    (3). 任意节点的左、右子树也分别为二元查找树；
    (4). 没有键值相等的节点
    　　10
　　    / \ 
　　   6  14
　　  / \ / \ 
　  　4 8 12 16
2. 二叉树遍历
    先(前)序遍历: 根左右
    中序遍历: 左根右
    后续遍历: 左右根
    层次遍历: 从上往下从左到右依次遍历
    前中后三种方式并称为深度优先遍历
    层次遍历即深度优先遍历
    　　10
　　    / \ 
　　   6  14
　　  / \ / \ 
　  　4 8 12 16
    
 转换成双向链表
4=6=8=10=12=14=16。
此题实质就是考察递归的使用以及树的遍历。中序遍历二元查找数的结果就是有序的目标节点顺序。
只需按中序遍历的顺序把节点链接到链表尾端即可
'''
class BinaryTree():
    """二叉树"""
    def __init__(self):
        self._data = None
        self._lchild = None
        self._rchild = None

    @property
    def data(self):
        return self._data

    @property
    def lchild(self):
        return self._lchild

    @property
    def rchild(self):
        return self._rchild

    @data.setter
    def data(self, value):
        self._data = value

    @lchild.setter
    def lchild(self, value):
        self._lchild = value

    @rchild.setter
    def rchild(self, value):
        self._rchild = value

    # 创建左右子节点
    def create_child(self, lchild, rchild):
        lnode = BinaryTree()
        rnode = BinaryTree()
        lnode.data = lchild
        rnode.data = rchild
        self.lchild = lnode
        self.rchild = rnode


# 递归遍历查找树
def btree_to_node(btree_root, node_head, node_last):
    '''
        10
　　    / \
　　   6  14
　　  / \ / \
　 　4 8 12 16

    '''
    # 当找到最小子节点时到达递归临界值
    if btree_root == None:
        return

    # 当左子树不为空时对左子树进行递归遍历
    if btree_root.lchild != None:
        btree_to_node(btree_root.lchild, node_head, node_last)

    # 调整节点指针
    # 将当前节点设为尾节点
    btree_root.lchild = node_last[0]
    if node_last[0] == None:
        # 如果头节点不存在时设置头节点, 头节点一定是最小的节点
        node_head[0] = btree_root
    else:
        # 如果头节点已存在, 则将上一个节点的尾节点替换为当前节点
        node_last[0].rchild = btree_root
    # 将node_last中的节点更改为当前节点, 用于传递给下一层递归调用
    node_last[0] = btree_root
    print(btree_root.data)

    if btree_root.rchild != None:
        # 如果存在右子树, 则递归右子树
        btree_to_node(btree_root.rchild, node_head, node_last)

def main():
    btree_root = BinaryTree()
    btree_root.data = 10
    btree_root.create_child(6, 14)
    btree_root.lchild.create_child(4, 8)
    btree_root.rchild.create_child(12, 16)
    print(btree_root)
    # 使用列表来达到引用存值的效果
    node_head = [None]
    node_last = [None]
    btree_to_node(btree_root, node_head, node_last)
    print(node_head[0].data)
    print(node_last[0].data)


if __name__ == "__main__":
    main()