二分搜索树的第K个节点

树是重要的非线性数据结构. 直观地讲，它是一种结构，其中数据元素（在树中称为节点）是根据分支关系进行组织的，就像自然中的树一样. 树形结构广泛存在于客观世界中. 例如，人类社会和各种社会组织的家谱可以用树的图像表示.

树还广泛用于计算机领域. 例如，当按如下所示编译源程序时，可以使用树来表示源程序的语法结构，如下所示. 另一个例子是在系统中，树形结构也是信息组织的重要形式之一. 层次关系的所有问题都可以用树来描述. 完整的二叉树，完整的二叉树二叉排序树 构造，排序二叉树.

二叉搜索树（BinarySearchTree），（再次: 二叉搜索树，二叉排序树）它是空树还是具有以下属性的二叉树: 如果其左子树不为空，则所有的值左子树上的节点小于其根节点的值；如果其右子树不为空，则右子树上所有节点的值大于其根节点的值;其左和右子树也是二进制排序树.

给出二叉搜索树，请找到第k个最小的节点. 例如，在（5,3,7,2,4,6,8）中，按节点值顺序排列的第三小的节点的值为4.

分析: 二叉搜索树是每个节点X，该节点X大于其左子树的值，并且小于其右子树的值，其顺序在增加. 使用有序遍历，每个遍历一个节点k-1，直到k减小为1，这是第K个最小的节点

/ * functionTreeNode（x）{

this.val = x;

this.left = null;

this.right = null;

} * /

functionKthNode（pRoot，k）{

if（pRoot === null || k === 0）{

returnnull;

}

//为了跟踪k二叉排序树 构造，应该在此处定义KthNodeCore函数，并且k应该在KthNodeCore函数之外

functionKthNodeCore（pRoot）{

lettarget = null;

if（pRoot.left！== null）{

target = KthNodeCore（pRoot.left，k）;

}

如果（目标===空）{

如果（k === 1）{

target = pRoot;

}

k-;

}

if（target === null && pRoot.right！== null）{

target = KthNodeCore（pRoot.right，k）;

}

返回目标；

}

returnKthNodeCore（pRoot）;

}

二进制排序树的搜索过程与次优二进制树相似，通常采用二进制链接列表作为二进制排序树的存储结构. 以中间顺序遍历二进制排序树可以获得关键字的有序序列，通过构造二进制排序树可以将无序序列转换为有序序列，构造树的过程就是对无序序列过程进行排序.

插入的每个新节点都是二进制排序树中的新叶节点. 插入时，无需移动其他节点，只需将节点的指针从空更改为非空即可. 搜索，插入和删除的复杂度等于树的高度O（log（n））.

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-221639-1.html