文章目录二叉树一、树的基本概念(一对多)二、二叉树的基本概念三、二叉树的遍历四、二叉树C语言实现4.1 二叉树的创建4.2 深度优先遍历算法4.2.1 前序遍历4.2.2 中序遍历4.2.3 后序遍历4.3 广度优先遍历算法4.3.1 层序遍历4.4 获取二叉树的节点总数4.5 获取二叉树的深度4.6 二叉树的销毁二叉树一、树的基本概念(一对多)树由根节点和若干个子节点构成的具有一对多关系的数据的集合称为树形结构。空树一个节点都没有。根节点最顶层的节点叶子节点终端节点没有子节点的节点称为叶子节点节点的度为0分支节点有子节点的节点。度树的深度树的层度树的度广度树中节点最大的度是该树的广度节点的度节点的子节点个数。二、二叉树的基本概念二叉树树的广度为二的树形结构称为二叉树且左右子节点不能交换。满二叉树在不增加层数的前提下无法再增加一个节点。K层满二叉树第K层的节点个数2k-1;K层总共节点个数2k-1;完全二叉树在满二叉树基础上按照从左至右从上至下的顺序增加节点该树是完全二叉树在满二叉树基础上按照从下至上从右至左的顺序删除节点该树是完全二叉树满二叉树一定是完全二叉树。三、二叉树的遍历前序遍历根、左子树、右子树中序遍历左子树、根、右子树后序遍历左子树、右子树、根上面三种称为深度优先遍历算法。层序遍历从上至下、从左至右、逐层遍历这种称为广度优先遍历算法。己知前序遍历和中序遍历结果可以唯一还原一棵二叉树;己知后序遍历和中序遍历结果可以唯一还原一棵二叉树;四、二叉树C语言实现对于二叉树的C语言实现我们需要一直使用函数递归的知识不知道的需要先去看看函数递归方面的知识。以此二叉树为例我们对其通过C语言实现4.1 二叉树的创建头文件#ifndef__TREE_H__#define__TREE_H__typedefcharTData_t;typedefstructtnode{TData_t data;structtnode*pl;structtnode*pr;}Tnode_t;全局字符数组str存储带空标记的先序字符串全局下标idx从 0 开始依次读取字符读到#时返回空指针表示空子树否则动态分配二叉树结点存入当前字符数据再递归构建其左子树、右子树最后返回新建结点完成整棵二叉树的构造。charstr[]ABF##GC###DH#I##E##;intidx0;Tnode_t*create_tree(){TData_t datastr[idx];if(data#){returnNULL;}Tnode_t*pnodemalloc(sizeof(Tnode_t));if(NULLpnode){printf(malloc error\n);returnNULL;}pnode-datadata;pnode-plcreate_tree();pnode-prcreate_tree();returnpnode;}4.2 深度优先遍历算法4.2.1 前序遍历接收二叉树根节点指针proot递归终止条件为结点为空直接返回不为空时先输出当前结点的数据再递归遍历打印左子树最后递归遍历打印右子树实现先序顺序输出整棵二叉树所有节点。voidpre_show_tree(Tnode_t*proot){if(NULLproot){return;}printf(%c ,proot-data);pre_show_tree(proot-pl);pre_show_tree(proot-pr);}4.2.2 中序遍历传入二叉树根节点指针proot递归结束条件结点为空则直接返回不为空时先递归访问左子树再打印当前节点的数据最后递归访问右子树按照左‑根‑右的顺序输出二叉树所有结点。voidmid_show_tree(Tnode_t*proot){if(NULLproot){return;}mid_show_tree(proot-pl);printf(%c ,proot-data);mid_show_tree(proot-pr);}4.2.3 后序遍历接收二叉树根结点指针proot递归终止条件结点为空函数直接返回。结点非空时先递归遍历左子树再递归遍历右子树最后打印输出当前结点的数据按照左‑右‑根的顺序输出二叉树全部节点。voidbe_show_tree(Tnode_t*proot){if(NULLproot){return;}be_show_tree(proot-pl);be_show_tree(proot-pr);printf(%c ,proot-data);}4.3 广度优先遍历算法4.3.1 层序遍历对于层序遍历我们需要借助队列的知识我在这直接使用了我之前的与队列相关的博文的C语言代码文章链接【数据结构学习3】队列之链式队列及循环队列【C语言】实现首先创建一个队列将二叉树根结点入队循环判断队列不为空时从队列头部取出一个结点并打印其数据如果该结点存在左孩子则左孩子入队如果存在右孩子则右孩子入队不断重复取结点、打印、孩子入队的操作直到队列为空遍历结束后销毁队列释放队列资源。voidfloor_show(Tnode_t*proot){Qlink_t*tquecreat_queue();Tnode_t*pop_data;insert_qnode(tque,proot);while(!is_empty_queue(tque)){goout_qlink(tque,pop_data);printf(%c ,pop_data-data);if(pop_data-pl!NULL){insert_qnode(tque,pop_data-pl);}if(pop_data-pr!NULL){insert_qnode(tque,pop_data-pr);}}printf(\n);destroy_qlink(tque);}4.4 获取二叉树的节点总数intget_sumnode_tree(Tnode_t*proot){if(NULLproot){return0;}return1get_sumnode_tree(proot-pl)get_sumnode_tree(proot-pr);}4.5 获取二叉树的深度传入二叉树根节点指针proot递归出口结点为空时返回结点数量 0若当前结点有效则总数 当前结点 (1) 左子树结点数 右子树结点数递归求出整棵树所有节点的数量并返回。intget_tree_deep(Tnode_t*proot){if(NULLproot){return0;}intcntlget_tree_deep(proot-pl);intcntrget_tree_deep(proot-pr);returncntlcntr?cntl1:cntr1;}4.6 二叉树的销毁通过函数递归释放二叉树所有结点内存销毁整棵二叉树。递归终止条件结点为空直接返回否则先递归销毁左子树再递归销毁右子树最后free释放当前结点。本质按照后序遍历的顺序完成内存释放避免先释放父节点造成子节点地址丢失、内存泄漏。voiddestroy_tree(Tnode_t*proot){if(NULLproot){return;}destroy_tree(proot-pl);destroy_tree(proot-pr);free(proot);}