二叉树：高效数据结构解析

一、先解答上次的思考题问KMP 里 next 数组的作用是什么答当匹配失败时主串 i 不回退只通过 next 数组让模式串 j 跳到合适位置避免重复比较大幅提高效率。二、今天学习目标理解什么是树结构为什么要用树掌握二叉树的基本概念与形态二叉树的重要性质面试常问二叉树节点定义 简单构建代码三、什么是树Tree前面学的数组、链表、栈、队列都是线性结构像一条线。树结构是非线性结构像一棵倒过来的树有一个根节点最上面下面有子节点子节点又可以有子节点生活中的例子文件目录结构公司组织架构家谱特点一对多关系没有环路不能自己指向自己从根到任意节点只有一条路径四、什么是二叉树二叉树 每个节点最多只有两个子节点的树两个孩子分别叫左孩子右孩子五种基本形态空树只有根节点只有左子树只有右子树左右子树都有五、二叉树重要性质面试常考第 i 层最多有2^(i-1)个节点深度为 k 的二叉树最多有2^k - 1个节点叶子节点数 度为 2 的节点数 1满二叉树每一层都满完全二叉树除最后一层外都满且节点靠左这些不用死记做题多了自然记住。六、二叉树节点结构定义C 语言#include stdio.h #include stdlib.h // 二叉树节点结构 struct TreeNode { int data; // 数据域 struct TreeNode *left; // 左孩子 struct TreeNode *right; // 右孩子 }; // 创建一个新节点 struct TreeNode* createNode(int val) { struct TreeNode* node (struct TreeNode*)malloc(sizeof(struct TreeNode)); node-data val; node-left NULL; node-right NULL; return node; }七、手动构建一棵简单二叉树我们来构建一棵如下的树1 / \ 2 3 / \ 4 5// 主函数构建二叉树 int main() { // 根节点 struct TreeNode* root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); printf(二叉树构建完成\n); printf(根节点%d\n, root-data); printf(左孩子%d\n, root-left-data); printf(右孩子%d\n, root-right-data); return 0; }运行结果二叉树构建完成 根节点1 左孩子2 右孩子3八、今日小练习构建下面这棵二叉树并输出根节点、左孩子、右孩子10 / \ 20 30 \ 40直接套用上面代码修改数字即可完成。九、思考题已经建好一棵二叉树怎么按顺序把所有节点打印出来