c/c++语言开发共享C二叉树基础

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 errorn");  		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 errorn");  		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: %dn", 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