创建B树,动态添加节点,并使用三种遍历算法对树进行遍历
2023-09-27 14:26:06 时间
ks17:algorithm apple$ cat btree_test.c ///*************************************************************** /// @Filename: btree_test.c /// @Brief: 尝试构建b树,并使用三种遍历算法对树进行遍历 /// /// /// @notice: 在函数里面申请空间给指针,是不能返回的,必须包装一层,赋值给指针的指针方式,否则函数返回后赋值结果是NULL /// @Author: kuang17 /// @Last modified: 2019-06-17 18:51 ///*************************************************************** #include "stdio.h" #include "stdlib.h" #include "string.h" ///定义结构 typedef struct treeNode { int data; struct treeNode* parent; struct treeNode* lch; struct treeNode* rch; }TreeNode; typedef struct BtreeData { TreeNode* rootNode; }Btree; ///定义参数 struct BtreeData* m_btree; ///定义函数 TreeNode* mallocNode(); int initTree(Btree* btree, int rootData); int perorderTraversalTree(TreeNode* pnode); int inorderTraversalTree(TreeNode* pnode); int postorderTraversalTree(TreeNode* pnode); int addNode(TreeNode* parentNode, int newData); ///主函数 int main(int argc, char** argv) { int originData[100] = {0, 0, 0}; int count = 0; //init tree m_btree = (struct BtreeData*)malloc(sizeof(struct BtreeData)); initTree(m_btree, atoi(argv[1])); if(m_btree->rootNode != NULL) printf("root data is: %d\n", m_btree->rootNode->data); //create tree char input[12] = "{\0}"; int is_end = 1; while (is_end) { gets(input); printf("input is %s\n", input); if (strcmp(input, "end") == 0){ printf("end input.\n"); is_end = 0; } else{ //add to tree addNode(m_btree->rootNode, atoi(input)); originData[count++] = atoi(input); } } //perorder traversal printf("perorder traversal :\n"); perorderTraversalTree(m_btree->rootNode); //inorder traversal printf("inorder traversal :\n"); inorderTraversalTree(m_btree->rootNode); //postorder traversal printf("postorder traversal: \n"); postorderTraversalTree(m_btree->rootNode); printf("\norigin is :\n"); for(int i = 0; i < count; i++) { printf("%d\n", originData[i]); } printf("end\n"); } // ********************************************************************* /// @Brief mallocNode 申请空间 /// /// @Returns // ********************************************************************* TreeNode* mallocNode() { TreeNode* newNode; newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->data = 0; newNode->parent = NULL; newNode->lch = NULL; newNode->rch = NULL; return newNode; } // ********************************************************************* /// @Brief initTree 初始化树 /// /// @Param btree /// @Param rootData /// /// @Returns // ********************************************************************* int initTree(Btree* btree, int rootData) { TreeNode* rootNode; rootNode = mallocNode(); rootNode->data = rootData; btree->rootNode = rootNode; return 0; } // ********************************************************************* /// @Brief addNode 添加节点 /// /// @Param parentNode /// @Param newData /// /// @Returns // ********************************************************************* int addNode(TreeNode* parentNode, int newData) { TreeNode* newNode; newNode = mallocNode(); newNode->data = newData; if(newData <= parentNode->data) { printf("parent data is: %d, add lch\n", parentNode->data); if(parentNode->lch == NULL) { //这里没法直接给parentNode赋值,只能给他的节点赋值 parentNode->lch = newNode; }else { addNode(parentNode->lch, newData); } } if(newData > parentNode->data) { printf("parent data is: %d, add rch\n", parentNode->data); if(parentNode->rch == NULL){ parentNode->rch = newNode; } else { addNode(parentNode->rch, newData); } } return 0; } // ********************************************************************* /// @Brief perorderTraversalTree 先序遍历 /// /// @Param pnode /// /// @Returns // ********************************************************************* int perorderTraversalTree(TreeNode* pnode) { if(pnode == NULL) return 0; perorderTraversalTree(pnode->lch); printf("%d\n", pnode->data); perorderTraversalTree(pnode->rch); return 1; } // ********************************************************************* /// @Brief inorderTraversalTree 中序遍历 /// /// @Param pnode /// /// @Returns // ********************************************************************* int inorderTraversalTree(TreeNode* pnode) { if(pnode == NULL) return 0; printf("%d\n", pnode->data); inorderTraversalTree(pnode->lch); inorderTraversalTree(pnode->rch); return 1; } // ********************************************************************* /// @Brief postorderTraversalTree 后序遍历 /// /// @Param pnode /// /// @Returns // ********************************************************************* int postorderTraversalTree(TreeNode* pnode) { if(pnode == NULL) return 0; postorderTraversalTree(pnode->lch); postorderTraversalTree(pnode->rch); printf("%d\n", pnode->data); return 1; }
相关文章
- 【LeetCode】被围绕的区域 [M](深度优先遍历)
- jQuery 遍历函数
- 最短路径算法:迪杰克斯拉(Dijkstra)算法(基于贪心思想)【从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题】【能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低】
- Twaver-HTML5基础学习(18)数据容器(1)_增删查改、遍历数据容器、包含网元判断
- 【Java 基础】数组:基本概念、遍历方式、三种排序(冒泡、选择、插入)
- 0083-Go-range 遍历
- 【GoLang】GoLang 遍历 map、slice、array方法
- Struts2使用OGNL遍历各种map总结
- 折纸的折痕(RVL中序遍历)
- 二叉排序树的构造 && 二叉树的先序、中序、后序遍历 && 树的括号表示规则
- Java小技巧:巧用函数方法实现二维数组遍历
- vue中v-for遍历数组
- LeetCode·117.填充每个节点的下一个右侧节点指针||·层次遍历
- C语言中字符串数组的遍历和比较
- 算法学习 - 图的广度优先遍历(BFS) (C++)
- Python语言及其应用 - 知识点遍历
- C#中的遍历、迭代、递归
- jackson中JSON字符串节点遍历和修改
- 树节点遍历-异步工作流方法研究
- python、java实现二叉树,细说二叉树添加节点、深度优先(先序、中序、后续)遍历 、广度优先 遍历算法
- 关于DOM节点的深度优先和广度优先遍历