树的基本操作 | |
| 注意： | 本文涉及大量的二级指针，如果有不熟悉的地方，希望读者能够查阅相关资料。 |
/* 文件名称： tree.h 作用描述： 理解树（结构题的基本操作）*/# ifndef __TREE_H__# define __TREE_H__typedef int treeNodeData;struct binaryTreeNode{ treeNodeData data; // 数据 struct binaryTreeNode * lchild; // 左孩子 struct binaryTreeNode * rchild; // 右孩子};typedef struct binaryTreeNode treeNode; // 方便使用/* 函数名称： initializeTree 函数传参： 二级指针 函数返回： void 函数功能： 对外部定义的树的跟节点进行初始化 函数描述： 根据值初始化，方便后续生成红黑树，或者平衡二叉树*/void initialBinaryTree(treeNode ** root);/* 函数名称： destoryBinaryTree 函数传参： 二级指针 函数返回： void 函数功能： 销毁二叉树 函数描述： */void destoryBinaryTree(treeNode ** root);/* 函数名称： preTravelTree 函数传参： 二级指针 函数返回： void 函数功能： 先序遍历整棵树 函数描述： */void preTravelTree(treeNode ** root);/* 函数名称： inTravelTree 函数传参： 二级指针 函数返回： void 函数功能： 中序遍历整棵树 函数描述： */void inTravelTree(treeNode ** root);/* 函数名称： postTravelTree 函数传参： 二级指针 函数返回： void 函数功能： 后序遍历整棵树 函数描述： */void postTravelTree(treeNode ** root);/* 函数名称： insertTreeNode 函数传参： 根节点二级指针 函数返回： void 函数功能： 插入排序二叉树节点 函数描述： 所有小于中间节点的字节点都在左边 所有大于中间节点的子节点都在右边 没有等于中间节点的子节点*/void insertTreeNode(treeNode ** root, int val);# endif /* 文件名称： tree.c 作用描述： 基本函数的实现 理解树（结构题的基本操作）*/# include "tree.h"# include# include void initialBinaryTree(treeNode ** root){ // 入参检测 if (root == NULL) { return; } *root = NULL;}void destoryBinaryTree(treeNode ** root){ if (root == NULL) { return; } if (*root == NULL) { return; } destoryBinaryTree(&((*root)->lchild)); destoryBinaryTree(&((*root)->rchild)); (*root)->lchild = NULL; (*root)->rchild = NULL; free(*root); *root = NULL;}void preTravelTree(treeNode ** root){ if (root == NULL) { return; } if (*root == NULL) { return; } printf("%d ", (*root)->data); preTravelTree(&((*root)->lchild)); preTravelTree(&((*root)->rchild));}void inTravelTree(treeNode ** root){ if (root == NULL) { return; } if (*root == NULL) { return; } inTravelTree(&((*root)->lchild)); printf("%d ", (*root)->data); inTravelTree(&((*root)->rchild));}void postTravelTree(treeNode ** root){ if (root == NULL) { return; } if (*root == NULL) { return; } postTravelTree(&((*root)->lchild)); postTravelTree(&((*root)->rchild)); printf("%d ", (*root)->data);}static void insertTreeNodePnode(treeNode ** root, treeNode * node){ if (*root == NULL) { *root = node; /* 注意 */ return; } if (node == NULL) { return; } if ((*root)->data > node->data) { insertTreeNodePnode(&((*root)->lchild), node); } else if ((*root)->data < node->data) { insertTreeNodePnode(&((*root)->rchild), node); } else { return; }}void insertTreeNode(treeNode ** root, int val){ // 将val值创建成节点 treeNode * node = NULL; if (root == NULL) { return; } node = (treeNode *)malloc(sizeof(treeNode)); if (node == NULL) { return; } node->data = val; node->rchild = NULL; node->lchild = NULL; insertTreeNodePnode(root, node);}
测试函数main函数
/* 文件名称： mian.c 作用描述： 对树进行测试*/# include "tree.h"# includeint main(void){ // pTreeNode p; treeNode * root = NULL; initialBinaryTree(&root); insertTreeNode(&root, 10); insertTreeNode(&root, 9); insertTreeNode(&root, 12); insertTreeNode(&root, 123); insertTreeNode(&root, 111); insertTreeNode(&root, 110); preTravelTree(&root); printf("\n"); destoryBinaryTree(&root); return 0;}
编译过程 makefile文件
src=*.ctree:$(src) gcc $(src) -o tree -Wall .PHONY:clean: rm tree
运行过程：
将main.c tree.c tree.h 放在同一目录下
新建makefile文件，将填写如上内容
执行make
运行./tree