树的概念与性质（哈喜老师）

1、树的相关概念2、树的性质及其题目2.1树的性质2.22010年题5选B。根据树的性质1可求得答案为822.3题目23.二叉树3.1二叉树的概念3.2二叉树的基本形态3.3二叉树与度为2的树有什么区别3.4满二叉树与完全二叉树3.5二叉树的性质很重要3.6完全二叉树的性质很重要3.7:二叉树相关的题目题目1不难但比较综合重点看2009年题5有一点难度题目3很坑重点看4.二叉树的存储4.1采用顺序存储结构假设完全二叉树的结点个数为n完全二叉树中的结点采用从上到下从左往右的顺序存储若结点的下标从0开始编号因为数组的下标是从0开始的则对于下标为i的结点满足以下4条性质①根结点的下标为0②已知孩子结点的下标 i (i0), 求父结点的下标父结点的下标为(i-1) / 2整数除法③已知父结点的下标 i 求左孩子结点的下标则左孩子的下标为2 * i 1当2 * i 1n时无左孩子④已知父结点的下标 i 求右孩子结点的下标则右孩子的下标为2 * i 2当2 * i 2n时无右孩子4.2采用链式存储结构⼆叉树的链式存储结构底层结构用链表来实现二叉树。链式存储结构又分为⼆叉链表和三叉链表。当前我们学习中⼀般都是二叉链表。后面课程学到高阶数据结构如红黑树)会用到三叉链表。①二叉链表链表中每个结点由3个域组成分别是存储结点的值的数据域以及两个指针域(一个指针指向该结点的左孩子另一个指针指向该结点的右孩子)。②三叉链表链表中每个结点由4个域组成分别是存储结点的值的数据域以及三个指针域(一个指针指向该结点的左孩子另一个指针指向该结点的右孩子最后一个指针指向该结点的父结点)。4.2.1:重要结论