第三十二课 -二叉树的定义

版权声明版权声明版权声明版权声明 本课件及其印刷物本课件及其印刷物本课件及其印刷物本课件及其印刷物 视频的版权归成都国嵌信息技术有限公司所有视频的版权归成都国嵌信息技术有限公司所有视频的版权归成都国嵌信息技术有限公司所有视频的版权归成都国嵌信息技术有限公司所有 并保留所有权力并保留所有权力并保留所有权力并保留所有权力 任何单任何单任何单任何单 位或个人未经成都国嵌信息技术有限公司书面授权位或个人未经成都国嵌信息技术有限公司书面授权位或个人未经成都国嵌信息技术有限公司书面授权位或个人未经成都国嵌信息技术有限公司书面授权 不得使用该课件及其印刷物不得使用该课件及其印刷物不得使用该课件及其印刷物不得使用该课件及其印刷物 视频从事商业视频从事商业视频从事商业视频从事商业 教学活教学活教学活教学活 动动动动 已经取得书面授权的已经取得书面授权的已经取得书面授权的已经取得书面授权的 应在授权范围内使用应在授权范围内使用应在授权范围内使用应在授权范围内使用 并注明并注明并注明并注明 来源来源来源来源 国嵌国嵌国嵌国嵌 违反上述声明者违反上述声明者违反上述声明者违反上述声明者 我们将追究其我们将追究其我们将追究其我们将追究其 法律责任法律责任法律责任法律责任 第三十二课第三十二课第三十二课第三十二课 二叉树的定义二叉树的定义二叉树的定义二叉树的定义 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 通用树结构的讨论通用树结构的讨论通用树结构的讨论通用树结构的讨论 讨论中讨论中讨论中讨论中讨论中讨论中讨论中讨论中 小小小小B 通用树结构的创建真的非常复杂哦通用树结构的创建真的非常复杂哦通用树结构的创建真的非常复杂哦通用树结构的创建真的非常复杂哦 小小小小C 当然了当然了当然了当然了 通用树结构中的每个结点都可以有任意多通用树结构中的每个结点都可以有任意多通用树结构中的每个结点都可以有任意多通用树结构中的每个结点都可以有任意多 的孩子的孩子的孩子的孩子 并且还能当成单链表并且还能当成单链表并且还能当成单链表并且还能当成单链表 顺序的访问每个结点顺序的访问每个结点顺序的访问每个结点顺序的访问每个结点 小小小小D 我觉得平时很少能用到这么复杂的树我觉得平时很少能用到这么复杂的树我觉得平时很少能用到这么复杂的树我觉得平时很少能用到这么复杂的树 有没有办法有没有办法有没有办法有没有办法 简化呢简化呢简化呢简化呢 小小小小A 减少结点中孩子的数量应该就可以简化了吧减少结点中孩子的数量应该就可以简化了吧减少结点中孩子的数量应该就可以简化了吧减少结点中孩子的数量应该就可以简化了吧 但问但问但问但问 题是题是题是题是 这样简化后这样简化后这样简化后这样简化后 树还能通用吗树还能通用吗树还能通用吗树还能通用吗 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 通用树结构的回顾通用树结构的回顾通用树结构的回顾通用树结构的回顾 通用树结构是采用双亲孩子表示法模型建立的通用树结构是采用双亲孩子表示法模型建立的通用树结构是采用双亲孩子表示法模型建立的通用树结构是采用双亲孩子表示法模型建立的 每个结点都有一个指向其双亲的指针每个结点都有一个指向其双亲的指针每个结点都有一个指向其双亲的指针每个结点都有一个指向其双亲的指针 每个结点都有若干个指向其孩子的指针每个结点都有若干个指向其孩子的指针每个结点都有若干个指向其孩子的指针每个结点都有若干个指向其孩子的指针 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 另一种树结构模型另一种树结构模型另一种树结构模型另一种树结构模型 孩子兄弟表示法模型孩子兄弟表示法模型孩子兄弟表示法模型孩子兄弟表示法模型 每个结点都有一个指向其第一个孩子的指针每个结点都有一个指向其第一个孩子的指针每个结点都有一个指向其第一个孩子的指针每个结点都有一个指向其第一个孩子的指针 每个结点都有一个指向其第一个右兄弟的指针每个结点都有一个指向其第一个右兄弟的指针每个结点都有一个指向其第一个右兄弟的指针每个结点都有一个指向其第一个右兄弟的指针 A BC D E F H I J 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法 每个结点包含一个数据指针和两个结点指针每个结点包含一个数据指针和两个结点指针每个结点包含一个数据指针和两个结点指针每个结点包含一个数据指针和两个结点指针 数据指针数据指针数据指针数据指针 指向保存于树中的数据指向保存于树中的数据指向保存于树中的数据指向保存于树中的数据 孩子结点指针孩子结点指针孩子结点指针孩子结点指针 指向第一个孩子指向第一个孩子指向第一个孩子指向第一个孩子 兄弟结点指针兄弟结点指针兄弟结点指针兄弟结点指针 指向第一个右兄弟指向第一个右兄弟指向第一个右兄弟指向第一个右兄弟 孩子结点指针孩子结点指针孩子结点指针孩子结点指针 兄弟结点指针兄弟结点指针兄弟结点指针兄弟结点指针 兄弟结点指针兄弟结点指针兄弟结点指针兄弟结点指针 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法 孩子兄弟表示法的特点孩子兄弟表示法的特点孩子兄弟表示法的特点孩子兄弟表示法的特点 能够表示任意的树形结构能够表示任意的树形结构能够表示任意的树形结构能够表示任意的树形结构 每个结点中有且仅有三个指针域每个结点中有且仅有三个指针域每个结点中有且仅有三个指针域每个结点中有且仅有三个指针域 数据指针数据指针数据指针数据指针 孩子结点指针孩子结点指针孩子结点指针孩子结点指针 兄弟结点指针兄弟结点指针兄弟结点指针兄弟结点指针 每个结点的结构简单每个结点的结构简单每个结点的结构简单每个结点的结构简单 只有孩子结点指针和兄弟结点指针构成了只有孩子结点指针和兄弟结点指针构成了只有孩子结点指针和兄弟结点指针构成了只有孩子结点指针和兄弟结点指针构成了 树杈树杈树杈树杈 这不就是传说中的这不就是传说中的这不就是传说中的这不就是传说中的 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 二叉树的定义二叉树的定义二叉树的定义二叉树的定义 二叉树是由二叉树是由二叉树是由二叉树是由n n n n n n n n n n n n n n n n 0 0 0 0 0 0 0 0 个结点组成的有限集个结点组成的有限集个结点组成的有限集个结点组成的有限集 合合合合 该集合或者为空该集合或者为空该集合或者为空该集合或者为空 或者是由一个根结点加或者是由一个根结点加或者是由一个根结点加或者是由一个根结点加 上上上上两棵两棵两棵两棵分别称为分别称为分别称为分别称为左子树左子树左子树左子树和和和和右子树右子树右子树右子树的的的的 互不相交互不相交互不相交互不相交 的二叉树组成的二叉树组成的二叉树组成的二叉树组成 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 二叉树的定义二叉树的定义二叉树的定义二叉树的定义 二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态二叉树的五种不同形态 LLRR 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 特殊的二叉树特殊的二叉树特殊的二叉树特殊的二叉树 定义定义定义定义定义定义定义定义1 1 1 1 1 1 1 1满二叉树满二叉树满二叉树满二叉树满二叉树满二叉树满二叉树满二叉树 Full Binary Tree Full Binary Tree Full Binary Tree Full Binary Tree Full Binary Tree Full Binary Tree Full Binary Tree Full Binary Tree 如果如果如果如果二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为二叉树中所有分支结点的度数都为2 2 2 2 2 2 2 2 且叶子结点且叶子结点且叶子结点且叶子结点 且叶子结点且叶子结点且叶子结点且叶子结点 都在同一层次上都在同一层次上都在同一层次上都在同一层次上 则称这类二叉树为满二叉树则称这类二叉树为满二叉树则称这类二叉树为满二叉树则称这类二叉树为满二叉树 都在同一层次上都在同一层次上都在同一层次上都在同一层次上 则称这类二叉树为满二叉树则称这类二叉树为满二叉树则称这类二叉树为满二叉树则称这类二叉树为满二叉树 定义定义定义定义定义定义定义定义2 2 2 2 2 2 2 2完全二叉树完全二叉树完全二叉树完全二叉树完全二叉树完全二叉树完全二叉树完全二叉树 Complete Binary Tree Complete Binary Tree Complete Binary Tree Complete Binary Tree Complete Binary Tree Complete Binary Tree Complete Binary Tree Complete Binary Tree 如果一棵具有如果一棵具有如果一棵具有如果一棵具有如果一棵具有如果一棵具有如果一棵具有如果一棵具有n n n n n n n n个结点的高度为个结点的高度为个结点的高度为个结点的高度为个结点的高度为个结点的高度为个结点的高度为个结点的高度为k k k k k k k k的二叉树的二叉树的二叉树的二叉树 它的每一个它的每一个它的每一个它的每一个的二叉树的二叉树的二叉树的二叉树 它的每一个它的每一个它的每一个它的每一个 结点都与高度为结点都与高度为结点都与高度为结点都与高度为结点都与高度为结点都与高度为结点都与高度为结点都与高度为k k k k k k k k的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为的满二叉树中编号为1 1 1 1 1 1 1 1 n n n n n n n n的结点一一的结点一一的结点一一的结点一一的结点一一的结点一一的结点一一的结点一一 对应对应对应对应 则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树 从上到下从左从上到下从左从上到下从左从上到下从左对应对应对应对应 则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树则称这棵二叉树为完全二叉树 从上到下从左从上到下从左从上到下从左从上到下从左 到右编号到右编号到右编号到右编号 到右编号到右编号到右编号到右编号 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入式嵌入式嵌入式嵌入式Linux学习交流学习交流学习交流学习交流QQ群群群群 65212116 特殊的二叉树特殊的二叉树特殊的二叉树特殊的二叉树 完全二叉树的叶结点仅出现在最下面两层完全二叉树的叶结点仅出现在最下面两层完全二叉树的叶结点仅出现在最下面两层完全二叉树的叶结点仅出现在最下面两层 最下层的叶结点一定出现在左边最下层的叶结点一定出现在左边最下层的叶结点一定出现在左边最下层的叶结点一定出现在左边 倒数第二层的叶结点一定出现在右边倒数第二层的叶结点一定出现在右边倒数第二层的叶结点一定出现在右边倒数第二层的叶结点一定出现在右边 完全二叉树中度为完全二叉树中度为完全二叉树中度为完全二叉树中度为1 1 1 1的结点只有左孩子的结点只有左孩子的结点只有左孩子的结点只有左孩子 同样结点数的二叉树同样结点数的二叉树同样结点数的二叉树同样结点数的二叉树 完全二叉树的高度最小完全二叉树的高度最小完全二叉树的高度最小完全二叉树的高度最小 嵌入式嵌入式嵌入式嵌入式Linux技术咨询技术咨询技术咨询技术咨询QQ号号号号 550491596 嵌入