二叉搜索树

注意: 所有问题的代码都是参考v_JULY_v或您自己编写的，答案中的分析就是您的想法.

1. 将二叉搜索树转换为排序的双向链表

标题:

输入二进制搜索树，然后将二进制搜索树转换为排序的双向链表.

要求不能创建任何新节点，只能调整指针.

10

/ /

6 14

/ / / /

4 8 12 16

转换为双向链接列表

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

首先，我们定义的二叉搜索树节点的数据结构如下:

struct BSTreeNode

{

int m_nValue; //节点的值

BSTreeNode * m_pLeft; //节点的左子节点

BSTreeNode * m_pRight; //节点的右子节点

};

答案:

在此问题中，我们通过在每次访问当前树节点之前记录最后访问的节点来进行修改（因为该节点是循环列表中当前访问节点的前任节点），以修改二分搜索树的结构实现两个结构之间的转换.

在分析此问题期间二叉排序树查找 算法，我再次深刻理解了树遍历的顺序. 在预遍历过程中，由于当前访问的节点由其左，右子节点优先二叉排序树查找 算法，因此访问该节点时，无法修改左，右子树中的指针. 在中阶遍历过程中，由于在访问当前节点之前已访问了其左子树的所有节点，因此可以修改其左子树的结构，而不会影响树的正确中阶遍历行为，但这是仍然无法修改其右侧子树中节点的结构. 同样，在后遍历过程中，由于访问节点时已访问左右子树，因此修改左右子树的结构不会影响后续的树遍历行为.

代码:

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-257642-1.html