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

86 阅读 0 评论 57 点赞

我是靠谱客的博主优雅蜻蜓，这篇文章主要介绍在平衡二叉树中的每个结点中增设一个域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);	//说明待查询结点在根结点的右子树中
}