1. 树型结构 如图所示1.1 概念树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。它具有以下的特点有一个特殊的结点称为根结点根结点没有前驱结点。树是递归定义的。1.2 树的详细概念结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点共10个双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林1.3 树的存储结构class TreeNode { int val; TreeNode left; // 左子树指针 TreeNode right; // 右子树指针 TreeNode(int x) { valx; } }1.4 树的典型应用数据查找与排序BST、红黑树表达式解析表达式树前序对应前缀、后序对应后缀数据压缩哈夫曼编码数据库索引结构编译器语法树路由算法、决策树模型。2. 二叉树2.1概念一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。从上图可以看出二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的2.2 特殊的二叉树满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2k2^{k}2k−1 个 则它就是满二叉树。完全二叉树:是计算机中极其核心的数据结构它是效率极高的树形结构也是堆Heap、优先队列等底层实现的基础。与同深度满二叉树的编号 1~n 一一对应最后一层叶子靠左满二叉树是特殊的完全二叉树。2.3核心性质第 k 层根为第 1 层最多有2k−12^{k-1}2k−1个节点深度为 h 的二叉树最多有2h2^{h}2h−1 个节点满二叉树的情况对任何二叉树n0 的叶子节点数 n2 的节点数 1具有 n 个节点的完全二叉树深度为log2(n1)\log_2(n1)log2(n1)完全二叉树按层序编号1 开始对节点 i左孩子为 2i右孩子为 2i1父节点为 i/2。具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有①若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点②若2i1n左孩子序号2i1否则无左孩子③若2i2n右孩子序号2i2否则无右孩子例题1 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为多少 叶子节点 n0n211991200。 例题2 在具有 2n 个结点的完全二叉树中叶子结点个数为多少 总节点 叶子 n 1 n 2 2nn01(n0−1) 因为 n2n0−1 2n2n0 n0n 叶子节点是总数的一半 例题3 一个具有767个节点的完全二叉树其叶子节点个数为多少 767÷2383.5向上取整是 384。 例题4 一棵完全二叉树的节点数为531个那么这棵树的高度为多少 找 2 的幂次 2^9 512 2^10 1024 因为 512≤5311024 高度 h9110。2.4 二叉树的存储二叉树的存储结构分为顺序存储和类似于链表的链式存储// 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 }2.5 二叉树的遍历一、 核心口诀前序遍历根→ 左 → 右中序遍历左 →根→ 右后序遍历左 → 右 →根层序遍历从上到下从左到右按层二、 经典例子1. 前序遍历根在前顺序根 → 左 → 右过程先访问 A再走左子树 B访问 B再走 B 的左 D访问 DD 没孩子回退访问 B 的右 E回退访问根 C。结果A → B → D → E → C2. 中序遍历根在中顺序左 → 根 → 右过程走到最左 D访问 D回父节点 B访问 B走右 E访问 E回根 A访问 A走右 C访问 C。结果D → B → E → A → C3. 后序遍历根在后顺序左 → 右 → 根过程先访问最底层左右 D、E访问父 B再访问右 C最后访问根 A。结果D → E → B → C → A4. 层序遍历按层排队顺序第 1 层 → 第 2 层 → 第 3 层结果A → B → C → D → E// 前序遍历 void preOrder(Node root); // 中序遍历 void inOrder(Node root); // 后序遍历 void postOrder(Node root);例题 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列是 前序遍历ABDHECFG 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点是 ①. 找根节点 先序遍历的第一个元素是 E → 这就是整棵二叉树的根节点。 ②. 验证中序中定位根 在中序遍历序列 H F I E J K G 中找到 E - E 左边的 H F I → 是根节点 E 的左子树 - E 右边的 J K G → 是根节点 E 的右子树。 - 层序遍历为 E F G H I J K 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为 第一步用后序找根中序分左右 - 后序序列b d e c a → 最后一个是 a所以整棵树的根是 a。 - 中序序列b a d c e → 在 a 处切开 - 左子树b - 右子树d c e 第二步处理右子树 dce - 后序序列中a 之前的是 b d e c对应右子树的后序是 d e c → 最后一个 c 是右子树的根。 - 中序序列中 d c e 切开 - 左子树d - 右子树e 第三步拼接前序根→左→右 前序遍历序列为abcde 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为多少 第一步核心规律 - 后序遍历左 → 右 → 根 → 最后一个节点是整棵树的根。 - 中序遍历左 → 根 → 右 → 根节点左侧是左子树右侧是右子树。 第二步推导树结构 1.确定根节点后序序列最后一个是 F所以根是 F。 - 中序序列 ABCDEF 中F 在最右侧 → 左子树为 ABCDE无右子树。 2. 处理左子树 ABCDE - 后序子序列为 ABCDE根是 E。 - 中序子序列 ABCDE 中E在最右侧 → 左子树为 ABCD无右子树。2.6 二叉树的基本操作// 获取树中节点的个数 int size(Node root); // 获取叶子节点的个数 int getLeafNodeCount(Node root); // 子问题思路-求叶子结点个数 // 获取第K层节点的个数 int getKLevelNodeCount(Node root,int k); // 获取二叉树的高度 int getHeight(Node root); // 检测值为value的元素是否存在 Node find(Node root, int val); //层序遍历 void levelOrder(Node root); // 判断一棵树是不是完全二叉树 boolean isCompleteTree(Node root);
二叉树的详细介绍
发布时间：2026/5/21 13:41:55
1. 树型结构 如图所示1.1 概念树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。它具有以下的特点有一个特殊的结点称为根结点根结点没有前驱结点。树是递归定义的。1.2 树的详细概念结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6叶子结点或终端结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点共10个双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4非终端结点或分支结点度不为0的结点 如上图D、E、F、G…等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点 如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林1.3 树的存储结构class TreeNode { int val; TreeNode left; // 左子树指针 TreeNode right; // 右子树指针 TreeNode(int x) { valx; } }1.4 树的典型应用数据查找与排序BST、红黑树表达式解析表达式树前序对应前缀、后序对应后缀数据压缩哈夫曼编码数据库索引结构编译器语法树路由算法、决策树模型。2. 二叉树2.1概念一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。从上图可以看出二叉树不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树注意对于任意的二叉树都是由以下几种情况复合而成的2.2 特殊的二叉树满二叉树: 一棵二叉树如果每层的结点数都达到最大值则这棵二叉树就是满二叉树。也就是说如果一棵二叉树的层数为K且结点总数是2k2^{k}2k−1 个 则它就是满二叉树。完全二叉树:是计算机中极其核心的数据结构它是效率极高的树形结构也是堆Heap、优先队列等底层实现的基础。与同深度满二叉树的编号 1~n 一一对应最后一层叶子靠左满二叉树是特殊的完全二叉树。2.3核心性质第 k 层根为第 1 层最多有2k−12^{k-1}2k−1个节点深度为 h 的二叉树最多有2h2^{h}2h−1 个节点满二叉树的情况对任何二叉树n0 的叶子节点数 n2 的节点数 1具有 n 个节点的完全二叉树深度为log2(n1)\log_2(n1)log2(n1)完全二叉树按层序编号1 开始对节点 i左孩子为 2i右孩子为 2i1父节点为 i/2。具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有①若i0双亲序号(i-1)/2i0i为根结点编号无双亲结点②若2i1n左孩子序号2i1否则无左孩子③若2i2n右孩子序号2i2否则无右孩子例题1 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为多少 叶子节点 n0n211991200。 例题2 在具有 2n 个结点的完全二叉树中叶子结点个数为多少 总节点 叶子 n 1 n 2 2nn01(n0−1) 因为 n2n0−1 2n2n0 n0n 叶子节点是总数的一半 例题3 一个具有767个节点的完全二叉树其叶子节点个数为多少 767÷2383.5向上取整是 384。 例题4 一棵完全二叉树的节点数为531个那么这棵树的高度为多少 找 2 的幂次 2^9 512 2^10 1024 因为 512≤5311024 高度 h9110。2.4 二叉树的存储二叉树的存储结构分为顺序存储和类似于链表的链式存储// 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 }2.5 二叉树的遍历一、 核心口诀前序遍历根→ 左 → 右中序遍历左 →根→ 右后序遍历左 → 右 →根层序遍历从上到下从左到右按层二、 经典例子1. 前序遍历根在前顺序根 → 左 → 右过程先访问 A再走左子树 B访问 B再走 B 的左 D访问 DD 没孩子回退访问 B 的右 E回退访问根 C。结果A → B → D → E → C2. 中序遍历根在中顺序左 → 根 → 右过程走到最左 D访问 D回父节点 B访问 B走右 E访问 E回根 A访问 A走右 C访问 C。结果D → B → E → A → C3. 后序遍历根在后顺序左 → 右 → 根过程先访问最底层左右 D、E访问父 B再访问右 C最后访问根 A。结果D → E → B → C → A4. 层序遍历按层排队顺序第 1 层 → 第 2 层 → 第 3 层结果A → B → C → D → E// 前序遍历 void preOrder(Node root); // 中序遍历 void inOrder(Node root); // 后序遍历 void postOrder(Node root);例题 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列是 前序遍历ABDHECFG 2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点是 ①. 找根节点 先序遍历的第一个元素是 E → 这就是整棵二叉树的根节点。 ②. 验证中序中定位根 在中序遍历序列 H F I E J K G 中找到 E - E 左边的 H F I → 是根节点 E 的左子树 - E 右边的 J K G → 是根节点 E 的右子树。 - 层序遍历为 E F G H I J K 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为 第一步用后序找根中序分左右 - 后序序列b d e c a → 最后一个是 a所以整棵树的根是 a。 - 中序序列b a d c e → 在 a 处切开 - 左子树b - 右子树d c e 第二步处理右子树 dce - 后序序列中a 之前的是 b d e c对应右子树的后序是 d e c → 最后一个 c 是右子树的根。 - 中序序列中 d c e 切开 - 左子树d - 右子树e 第三步拼接前序根→左→右 前序遍历序列为abcde 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为多少 第一步核心规律 - 后序遍历左 → 右 → 根 → 最后一个节点是整棵树的根。 - 中序遍历左 → 根 → 右 → 根节点左侧是左子树右侧是右子树。 第二步推导树结构 1.确定根节点后序序列最后一个是 F所以根是 F。 - 中序序列 ABCDEF 中F 在最右侧 → 左子树为 ABCDE无右子树。 2. 处理左子树 ABCDE - 后序子序列为 ABCDE根是 E。 - 中序子序列 ABCDE 中E在最右侧 → 左子树为 ABCD无右子树。2.6 二叉树的基本操作// 获取树中节点的个数 int size(Node root); // 获取叶子节点的个数 int getLeafNodeCount(Node root); // 子问题思路-求叶子结点个数 // 获取第K层节点的个数 int getKLevelNodeCount(Node root,int k); // 获取二叉树的高度 int getHeight(Node root); // 检测值为value的元素是否存在 Node find(Node root, int val); //层序遍历 void levelOrder(Node root); // 判断一棵树是不是完全二叉树 boolean isCompleteTree(Node root);
