清华大学出版社 TSINGHUA UNIVERSITY PRESS 5.2.2二叉树的基本性质 性质1在二叉树的第k层上,最多有2-1k≥1) 结点。 性质2深度为m的二叉树最多有2m-1个结点。 性质3在任意一棵二叉树中,度为0的结点 (即叶子结点)总是比度为2的结点多一个。 性质4具有n个结点的二叉树,其深度至少为 Logon]+1 其中[log2n]表示取1og2n的整数部分
5.2.2 二叉树的基本性质 性质1 在二叉树的第k层上，最多有2 k－1(k≥1) 个 结点。 性质2 深度为m的二叉树最多有2 m－1个结点。 性质3 在任意一棵二叉树中，度为0的结点 （即叶子结点）总是比度为2的结点多一个。 性质4 具有n个结点的二叉树，其深度至少为 [log2n]＋1 其中[log2n]表示取log2n的整数部分
清华大学出版社 TSINGHUA UNIVERSITY PRESS 5.2.3满二叉树与完全二叉树 1.满二叉树 风 圆回回国向囟面立面囟血面回 深度为2的满二叉树深度为3的满二叉树 深度为4的满二叉树
5.2.3 满二叉树与完全二叉树 1.满二叉树
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.完全二叉树 风 回回回回 深度为3的完全二叉树
2.完全二叉树
清华大学出版社 TSINGHUA UNIVERSITY PRESS 面山由也 深度为4的完全二叉树
清华大学出版社 TSINGHUA UNIVERSITY PRESS 二叉树及其基本性质 性质5具有n个结点的完全二叉树的深度为[og2n]+1 性质6设完全二叉树共有n个结点。如果从根结点开始, 按层序(每一层从左到右)用自然数1,2,…,n 给结点进行编号,则对于编号为k(k=1,2,…,n) 的结点有以下结论: (1)若k=1,则该结点为根结点,它没有父结点; 若k>1,则该结点的父结点编号为INT(k/2)。 (2)若2k≤n,则编号为k的结点的左子结点编号为2k; 否则该结点无左子结点(显然也没有右子结点 (3)若2k+1≤n,则编号为k的结点的右子结点编号 为2k+1;否则该结点无右子结点
二叉树及其基本性质 性质5 具有n个结点的完全二叉树的深度为[log2n]＋1。 性质6 设完全二叉树共有n个结点。如果从根结点开始， 按层序（每一层从左到右）用自然数1，2，…，n 给结点进行编号，则对于编号为k(k＝1，2，…，n) 的结点有以下结论： (1)若k＝1，则该结点为根结点，它没有父结点； 若k＞1，则该结点的父结点编号为INT(k/2)。 (2)若2k≤n，则编号为k的结点的左子结点编号为2k； 否则该结点无左子结点（显然也没有右子结点）。 (3)若2k＋1≤n，则编号为k的结点的右子结点编号 为2k＋1；否则该结点无右子结点