栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

简单的二叉树代码

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

简单的二叉树代码

给一个源代码, 演示了如何使用结构,指针,构造一个有序,无序二叉树,递归函数的调用过程

#include 
#include 
#include 
#include 

typedef struct stBinaryNode
{
	int _value;
	struct stBinaryNode* _left;
	struct stBinaryNode* _right;
}BinaryNode;

BinaryNode* createNode()
{
	BinaryNode* lpNode = malloc(sizeof(BinaryNode));
	memset(lpNode, 0, sizeof(BinaryNode));
	return lpNode;
}

BinaryNode* insertLeftNode(BinaryNode* lpParent, int v)
{
	if (!lpParent)
	{
		return NULL;
	}
	while (lpParent->_left)
	{
		lpParent = lpParent->_left;
	}
	BinaryNode* lpNode = createNode();
	lpParent->_left = lpNode;
	lpNode->_value = v;
	return lpNode;
}

BinaryNode* insertRightNode(BinaryNode* lpParent, int v)
{
	if (!lpParent)
	{
		return NULL;
	}
	while (lpParent->_right)
	{
		lpParent = lpParent->_right;
	}

	BinaryNode* lpNode = createNode();
	lpNode->_value = v;

	lpParent->_right = lpNode;

	return lpNode;
}
// 有序插入新节点
void insertNodeWithOrder(BinaryNode* lpParent, int v)
{
	if (!lpParent)
	{
		return;
	}

	if (v < lpParent->_value)
	{
		if (lpParent->_left)
		{
			insertNodeWithOrder(lpParent->_left, v);
		}
		else
		{
			insertLeftNode(lpParent, v);
		}
	}
	else if (v > lpParent->_value)
	{
		if (lpParent->_right)
		{
			insertNodeWithOrder(lpParent->_right, v);
		}
		else
		{
			insertRightNode(lpParent, v);
		}
		
	}
}


// 递归添加子节点,建立10层二叉树结构
void insertNode(BinaryNode *lpParent, int layer, int maxLayer, int *index )
{
	if (layer >= maxLayer)
	{
		return;
	}
	// 当前节点插入左子节点, 节点的值为*index, 此值设定为每插入一个新节点, 就自增1
	BinaryNode* lpLeft = insertLeftNode( lpParent, *index);
	(*index)++;
	// 递归调用自己,直到layer>=10
	insertNode(lpLeft, layer + 1, maxLayer, index);
	// 当前节点插入右节点, 同样插入的值为*index, 此值设定为每插入一个新节点就自增1
	BinaryNode* lpRight = insertRightNode(lpParent, *index);
	(*index)++;
	insertNode(lpRight, layer + 1, maxLayer, index);
}
// 前序打印
void prePrintNode(BinaryNode* lpNode)
{
	if (!lpNode)
	{
		return;
	}
	printf("%dn", lpNode->_value);

	prePrintNode(lpNode->_left);
	prePrintNode(lpNode->_right);
}
// 中序打印
void middlePrintNode(BinaryNode* lpNode)
{
	if (!lpNode)
	{
		return;
	}


	middlePrintNode(lpNode->_left);
	printf("%dn", lpNode->_value);
	middlePrintNode(lpNode->_right);
}

// 在这里完成后序打印



// 销毁二叉树

void destoryNode(BinaryNode* lpNode)
{
	if (!lpNode)
	{
		return;
	}
	if(lpNode->_left)
	{
		destoryNode(lpNode->_left);
		lpNode->_left = NULL;
	}

	if (lpNode->_right)
	{
		destoryNode(lpNode->_right);
		lpNode->_right = NULL;
	}

	free(lpNode);
}


int main(int argc, char* argv[])
{
	// 初始化随机数
	srand((int)time(NULL));

	int index = 0;
	BinaryNode* lpRoot = createNode();
	lpRoot->_value = index;
	index++;

	insertNode(lpRoot, 0, 5, &index);
	prePrintNode(lpRoot);
	printf("=============================n");
	middlePrintNode(lpRoot);

	destoryNode(lpRoot);
	lpRoot = NULL;

	BinaryNode* lpRoot2 = createNode();
	// 随机数赋值
	lpRoot2->_value = rand() % 100;
	for (int i = 0; i < 100; i++)
	{
		// 随机数赋值
		insertNodeWithOrder(lpRoot2, rand() % 100);
	}

	printf("lproot2====================================n");
	prePrintNode(lpRoot2);

	printf("lpRoot2 middle ===============================n");
	middlePrintNode(lpRoot2);
	destoryNode(lpRoot2);
	lpRoot2 = NULL;


	return 0;
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/985482.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号