欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C二叉树基础

程序员文章站 2023-12-26 08:07:33
c二叉树基础:c二叉树又该怎么实现呢?希望下面的文章对大家有所帮助。 #include #include"linkqueue.h" //#include"lin...
c二叉树基础:c二叉树又该怎么实现呢?希望下面的文章对大家有所帮助。
#include
#include"linkqueue.h"
//#include"linkstack.h"

typedef char data_t;
typedef struct btnode {
	data_t data;
	struct btnode* lchild;
	struct btnode* rchild;
}btree_t;

 void* assertx(void* p)
{
	if(p == null) {
		printf("argument error\n");
		return null;
	}
	
}

/**
 *	@data: 节点数据指针
 *	@num:  节点位置编号从根1开始
 *	@len:  待存入树节点中的数据的长度
 */
btree_t* create_btree(data_t* data, int num, int len)
{
	btree_t *root;
	// 1.
	root = (btree_t*)malloc(sizeof(btree_t));
	if(root == null) {
		printf("allocate memory error\n");
		return null;
	}
	// 2.
	root->data = data[num];
	root->lchild = null;
	root->rchild = null;
	// 3. 这里利用满二叉树的特性
	if(2*num <= len) {
		root->lchild = create_btree(data, 2*num, len);

	}
	if(2*num+1 <= len) {
		root->rchild = create_btree(data, 2*num+1, len);
	}

	return root;
}
// 层次遍历
int btree_travers_layer(btree_t* root)
{
	assertx(root);
	btree_t* temp;
	linkqueue* queue = create_empty_linkqueue();

	// 1. root 入队列
	enter_linkqueue(queue, root);
	// 2. root 出队列,每出一个,拿到其孩子节点放入队尾
	// 直到队列为空,完成遍历
	while(!is_empty_linkqueue(queue)) {
		temp = delete_linkqueue(queue);
		printf("[%c] ", temp->data);
		if(temp->lchild != null) 
			enter_linkqueue(queue, temp->lchild);
		if(temp->rchild != null)
			enter_linkqueue(queue, temp->rchild);
	}
	printf("\n");
}
// 前序遍历
int btree_travers_preorder(btree_t* root)
{	
	if(root == null) {
		return -1;
	}
	printf("[%c] ", root->data);
	if(root->lchild != null) {
		btree_travers_preorder(root->lchild);
	}
	if(root->rchild != null) {
		btree_travers_preorder(root->rchild);
	}

	return 0;

}


// 中序遍历
int btree_travers_midorder(btree_t* root)
{	
	if(root == null) {
		return -1;
	}
	if(root->lchild != null) {
		btree_travers_midorder(root->lchild);
	}
	printf("[%c] ", root->data);
	if(root->rchild != null) {
		btree_travers_midorder(root->rchild);
	}

	return 0;

}
// 后序遍历
int btree_travers_postorder(btree_t* root)
{	
	if(root == null) {
		return -1;
	}
	if(root->lchild != null) {
		btree_travers_postorder(root->lchild);
	}
	if(root->rchild != null) {
		btree_travers_postorder(root->rchild);
	}
	printf("[%c] ", root->data);

	return 0;

}
/*****************************************************
 * 计算树的高度
 *	思路: 
 *	    用两个队列a,b。第一层节点入a队列,弹出a
 *	队列中的元素所有元素,每出一个,判读其左右孩子
 *	若果存在孩子,则孩子入b队列。层数累加。然后弹出
 *	所有b的元素,同样每出一个,判断左右孩子,存在则
 *	入a队列,层数累加。如此直到队列为空。
 *****************************************************/
unsigned int count_btree_height(btree_t* root)
{
	unsigned int count = 0;
	btree_t* temp;
	linkqueue*	aq = create_empty_linkqueue();
	linkqueue*	bq = create_empty_linkqueue();
	linkqueue*  	tq;

	if(root == null) {
		return 0;
	}

	enter_linkqueue(aq, root);
	while(!is_empty_linkqueue(aq)) {		// 判断也就是上一层的孩子构成的队列是否为空
		while(!is_empty_linkqueue(aq)) {	// 出队直到整个队列元素都被处理
			temp = delete_linkqueue(aq);	// 
			if(temp->lchild != null) {
				enter_linkqueue(bq, temp->lchild);
			}
			if(temp->rchild != null) {
				enter_linkqueue(bq, temp->rchild);
			}
		}
		count++;
		tq = aq;		// 为了简化代码: 交换 aq和bq,就是下次操作之前层的孩子队列
		aq = bq;
		bq = tq;
	}
	
	return count;
}



int main()
{
	char ca[] = {  0, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',  'k', 'l', 'm', 'n'};
	btree_t* tree = create_btree(ca, 1, sizeof(ca)/sizeof(ca[0]) - 1);
	printf("layer travers: ");
	btree_travers_layer(tree);
	printf("pre   travers: ");
	btree_travers_preorder(tree);
	printf("\n");
	printf("mid   travers: ");
	btree_travers_midorder(tree);
	printf("\n");
	printf("post  travers: ");
	btree_travers_postorder(tree);
	printf("\n");
	printf("btree height: %d\n", count_btree_height(tree));

	return 0;
}
这里使用了队列和递归的思维解决问题。
gcc输出:
layer travers: [a] [b] [c] [d] [e] [f] [g] [h] [i] [j] [k] [l] [m] [n]
pre  travers: [a] [b] [d] [h] [i] [e] [j] [k] [c] [f] [l] [m] [g] [n]
mid  travers: [h] [d] [i] [b] [j] [e] [k] [a] [l] [f] [m] [c] [n] [g]
post travers: [h] [i] [d] [j] [k] [e] [b] [l] [m] [f] [n] [g] [c] [a]
btree height: 4

上一篇:

下一篇: