频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
初步学习二叉排序树
2015-03-08 11:11:14         来源:qinmusiyan的专栏  
收藏   我要投稿

1. 二叉排序树的性质如下:

(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

(3)左、右子树也分别为二叉排序树;

(4)没有键值相等的节点。

\

2.二叉树的实现

(1) 节点的定义:<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4KPHA+PHN0cm9uZz48L3N0cm9uZz48cHJlIGNsYXNzPQ=="brush:java;">typedef int KeyType; typedef struct Node { KeyType m_data; //数据成员 Node *m_pLChild;//左子树; Node *m_pRChild;//右子树; Node *m_pParent;//父节点; }BinaryTree, *PBinaryTree;


(2) 创建二叉树节点:

//创建二叉树节点
PBinaryTree createBinaryNode(KeyType key)
{
	PBinaryTree pNode = nullptr;
	pNode = (PBinaryTree)malloc(sizeof(BinaryTree));
	assert(nullptr != pNode);
	
	memset((void*)pNode, 0, sizeof(BinaryTree));
	pNode->m_data = key;
	return pNode;
}

(3) 插入节点到二叉排序树中:

在已知二叉排序树T中插入节点

1 若T为空则该节点作为根节点;

2 若插入节点值小于当前节点值则插入到左子树中;

3 若插入节点值大于当前节点值则插入到右子树中。

void insertBinaryNode(PBinaryTree * root, KeyType key)
{
	//若为空树,将插入节点作为根节点
	if (nullptr == (*root))
	{
		PBinaryTree pNode = createBinaryNode(key);
		(*root) = pNode;
		return;
	}

	//若key小于当前节点值, 且左子树为空
	if (nullptr == (*root)->m_pLChild && key < (*root)->m_data)
	{
		PBinaryTree pNode = createBinaryNode(key);
		(*root)->m_pLChild = pNode;
		pNode->m_pParent = (*root);
		return;
	}
	//若右子树为空,且key大于当前根节点值
	if (nullptr == (*root)->m_pRChild && key >(*root)->m_data)
	{
		PBinaryTree pNode = createBinaryNode(key);
		(*root)->m_pRChild = pNode;
		pNode->m_pParent = (*root);
		return;
	}

	if (key < (*root)->m_data)
		insertBinaryNode(&(*root)->m_pLChild, key);
	else if (key >(*root)->m_data)
		insertBinaryNode(&(*root)->m_pRChild, key);
	else
		return;
}

(4) 创建二叉排序树:

void createBinarySortTree(PBinaryTree * root, KeyType arr[], int length)
{
	for (int i = 0; i < length; i++)
	{
		insertBinaryNode(root, arr[i]);
	}
}


(5)对二叉排序树进行数据查找:

1若关键字恰好等于当前值,返回该节点;

2若关键字小当前节点值,在左子树中查找;

3若关键字大与当前节点值, 在右子树中查找;

4若不存在,返回空。

PBinaryTree searchNode(PBinaryTree root, KeyType key)
{
	if (nullptr == root)
		return nullptr;

	if (key == root->m_data)
		return root;
	else if (key < root->m_data)
		return searchNode(root->m_pLChild, key);
	else
		return searchNode(root->m_pRChild, key);
}

(6) 统计二叉排序树的非空节点:

对问题进行分割化,即先统计子树的非空节点,当子树非空节点已知后则比知该树的非空节点数

1计算左子树的非空节点数;

2计算右子树的非空节点数;

3计算该树的非空节点数;

int numInBinaryTree(PBinaryTree root)
{
	if (nullptr == root)
		return 0;

	return (1 + numInBinaryTree(root->m_pLChild) +
		numInBinaryTree(root->m_pRChild));
}

(6)获得二叉排序树的高度:

比较左子树和右子树的高度, 若左子树高度大于右子树高度,则该树的高度为左子树高度+1,否则为右子树高度+1。

int heightBinaryTree(PBinaryTree root)
{
	if (nullptr == root)
		return 0;

	int left, right;
	left = heightBinaryTree(root->m_pLChild);
	right = heightBinaryTree(root->m_pRChild);
	return (left > right) ? (left + 1) : (right + 1);
}

(7)中序遍历打印节点值:

//按照升序打印节点
void printBinaryTree(PBinaryTree root)
{
	if (nullptr == root)
		return;
	printBinaryTree(root->m_pLChild);
	cout << root->m_data << " ";
	printBinaryTree(root->m_pRChild);
}

测试:

int main()
{
	PBinaryTree binarySortTree = nullptr;
	int arr[100];
	int len;
	cout << "请输入不重复待排序元素的个数:";
	cin >> len;
	cout << "依次输入待排序元素:";
	for (int i = 0; i < len; i++)
		cin >> arr[i];

	createBinarySortTree(&binarySortTree, arr, len);

	cout << "输出排序结果如下:\n";
	printBinaryTree(binarySortTree);
	cout << endl;
	cout << "二叉排序树总共元素有: " << numInBinaryTree(binarySortTree) << endl;
	cout << "二叉排序树的高度为: " << heightBinaryTree(binarySortTree) << endl;

	return 0;
}

效果:





点击复制链接 与好友分享!回本站首页
相关TAG标签
上一篇:分页条中显示数字页码的计算方法
下一篇:算法导论学习之线性时间排序+排序算法稳定性总结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站