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
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607847.html