二叉树的基本性质 性质1在二叉树的第层的结点个数最多2() ·性质2深度为k的二叉树的最大结点数为2k1 性质3任一二叉树T,如果其叶子结点数为no,度为 2的结点数为n2,则n=n2+1 n,+n1+n2=n=2n2+n,+1 ·性质4具有n个结点的完全二叉树深度为 [og2(n+1)]或Log2n+1 ypb@ustc.edu.cn 11 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 • 性质1 在二叉树的第i层的结点个数最多2 (i-1) • 性质2 深度为k的二叉树的最大结点数为2 k -1 • 性质3 任一二叉树T，如果其叶子结点数为n0，度为 2的结点数为n2，则n0=n2+1 n0+n1+n2=n=2n2+n1+1 • 性质4 具有n个结点的完全二叉树深度为 或 二叉树的基本性质 log 2 (n +1) log 2 n +1
S 性质5如果对一个有n个结点的完全二叉树T的结 点按层序（从第一层到第logn]+1层，层内从左到 右)从1开始编号，则对任意一个编号为i1<=i<=n) 的结点有： - 如果i=1,则该结点是二叉树的根，无双亲；如果 i>1,,则其双亲结点Parent(i)的编号为[i/2] -如果2i>n,则编号为i的结点没有左孩子，为叶子结 点；否则其左孩子LChild(i)的编号为2i 如果2+1>n,则编号为i的结点没有右孩子；否则其 右孩子RChild(i的编号为2i+1 ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 • 性质5 如果对一个有n个结点的完全二叉树T的结 点按层序（从第一层到第[logn]+1层，层内从左到 右）从1开始编号，则对任意一个编号为i(1<=i<=n) 的结点有： – 如果i＝1，则该结点是二叉树的根，无双亲；如果 i>1，，则其双亲结点Parent(i)的编号为[i/2] – 如果2i>n，则编号为i 的结点没有左孩子，为叶子结 点；否则其左孩子LChild(i)的编号为2i – 如果2i+1>n，则编号为i 的结点没有右孩子；否则其 右孩子RChild(i)的编号为2i+1
二叉树的存储结构 顺序存储结构 Const MAXSIZE=100 B 01234567 0123456 (a)完全二叉树 (b)一般二叉树 ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 • 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data; int nodenum; }SqBiTree 二叉树的存储结构
S root > 链式存侗 一二叉钱 域，找父亲 必须从 —m P N 4m人术 pare N 囚 ild data (a)二叉链表 root 结构 Ichild lata rchild (a)结点的逻辑 结构 )上 (b)三叉链表 ypb@ustc.edu.cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 ➢ 链式存储结构 – 二叉链表 包涵data，lchild，rchild三个域，找父亲 必须从根开始 – 三叉链表 包涵data，lchild，rchild，parent四个域， 找父亲容易 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;
5.3三叉树遍历 > 二叉树的先/中/后序（根)遍历 一对所有结点进行访问，且仅被访问一次 -LDR、LRD、DLR、DRL、RLD、RDL六种次序 -先序DLR、中序LDR、后序LRD(保留从左向右) -例：右图得三种遍历序列 ·先序遍历：ABDEC ·中序遍历：DBEAC ·后序遍历：DEBCA B B B D DD ypb@ustc.edu.cn 15 中国科学技术大学
ypb@ustc.edu.cn 15 中国科学技术大学 5.3二叉树遍历 ➢ 二叉树的先/中/后序（根）遍历 – 对所有结点进行访问，且仅被访问一次 – LDR、LRD、DLR、DRL、RLD、RDL六种次序 – 先序DLR、中序LDR、后序LRD（保留从左向右） –例：右图得三种遍历序列 • 先序遍历：ABDEC • 中序遍历：DBEAC • 后序遍历：DEBCA A B C D E A B D E C D B E A C D E B C A