在平衡二叉树中的每个结点中增设一个域lsize,存储以该结点为根的左子树中的结点个数加1.确定树中第k(k＞=1)个结点的位置

二叉排序树中第k个结点，即为二叉排序树中序序列中顺序号为k的结点，根结点的Lsize域中存放的是根结点的顺序号。要确定二叉排序树中第k个结点，先需将k与根结点的顺序号进行比较，若相等，则找到；若k小于根结点的顺序号，k继续与根的左孩子结点的顺序号比较，依次类推。(注意，右孩子结点的顺序号等于根结点的顺序号与右孩子结点的Lsize域值之和。)

下面给出一幅图加以理解:

算法代码如下:

结构体定义:

typedef struct BTNode
{
	int data;
	int lsize;
	struct BTNode* lchild;
	struct BTNode* rchild;
};

实现算法:

BTNode* search_small(BTNode* t, int k)
{
	if (t == NULL || k < 1)
		return NULL;				//树空且k不存在，直接返回Null
	if (t->lsize==k)
		return t;					//k恰好是中序序列下第k个结点，相等直接返回该结点
	if (t->lsize > k)
		return search_small(t->lchild, k);		//说明待查询结点在根结点的左子树中
	else
		return search_small(t->rchild, k - t->lsize);	//说明待查询结点在根结点的右子树中
}

最后

以上就是优雅蜻蜓为你收集整理的在平衡二叉树中的每个结点中增设一个域lsize,存储以该结点为根的左子树中的结点个数加1.确定树中第k(k＞=1)个结点的位置的全部内容，希望文章能够帮你解决在平衡二叉树中的每个结点中增设一个域lsize,存储以该结点为根的左子树中的结点个数加1.确定树中第k(k＞=1)个结点的位置所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。