感情论坛,搜房网登陆,幻之盛唐txt
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
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论