满二叉树( full binary tree):所有结点度为2,叶子 结点在同一层次 完全二叉树( complete binary tree):深度h,h-l为 满二叉树,h层的结点都集中在左侧 二叉树的基本操作 ) 89101112131415 (a)满二叉树 (b)完全二叉树 pboustc. edu. cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 •LeftSibling(T,e) •RightSibling(T,e) •InsertChild(T,p,LR,C) •DeleteChild(T,p,LR) •PreOrderTraverse(T,visit()) •InOrderTraverse(T,visit()) •PostOrderTraverse(T,visit()) •Traverse(T) •InitBiTree(&T) •DestroyBiTree(&T) •CreateBiTree(&T,definition) •BiTreeEmpty(T) •BiTreeDepth(T) •Parent(T,e) •LeftChild(T,e) •RightChild(T,e) – 满二叉树（full binary tree）：所有结点度为2，叶子 结点在同一层次 – 完全二叉树（complete binary tree）：深度h，h-1为 满二叉树，h层的结点都集中在左侧 – 二叉树的基本操作
③62.2二叉树的几个基本性质 性质1在二叉树的第层的结点个数最多2(1 性质2深度为k的二叉树的最大结点数为2k-1 性质3任一二叉树T,如果其叶子结点数为n,度 为2的结点数为n2,则n=n2+1 n+n1+n2=n=2n2+n1+1 性质4具有n个结点的完全二叉树深度为logn+1 log(n+1) pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 • 性质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个结点的完全二叉树深度为logn+1 log(n+1) 6.2.2二叉树的几个基本性质
性质5如果对一个有n个结点的完全二叉树T的结 点按层序(从第一层到第[ogn]+层,层内从左到 右)从1开始编号,则对任意一个编号为(1<==n) 的结点有: 如果i=1,则该结点是二叉树的根,无双亲;如果 1>1,则其双亲结点 Parent(的编号为[2 如果21>n,则编号为i的结点没有左孩子,为叶子结 点;否则其左孩子 IChilo(i的编号为2i 如果2+1>n,则编号为i的结点没有右孩子;否则其 右孩子RChd(i的编号为2计+1 pboustc. edu. cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 • 性质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
③62.3二叉树的存储结构 顺序存储结构 Const MaXSIze=100 Q 2 2 3 ⑥5604 60 70 01234567 01234567 完全二叉树 (b)一般二叉树 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 • 顺序存储结构 Const MAXSIZE＝100 typedef struct{ ElemType *data; int nodenum; }SqBiTree 6.2.3二叉树的存储结构
链式存 二叉区 LS 个域,找父亲 必须 arent四个域, 找父面 (a)二叉链表 root hild 结点结构 Child data rchild 哎团 a)结点的 结点结构 四的面 b)三叉链表 pboustc. edu. cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 • 链式存储结构 – 二叉链表 包涵data，lchild，rchild三个域，找父亲 必须从根开始 – 三叉链表 包涵data，lchild，rchild，parent四个域， 找父亲容易 typedef BiTNode{ ElemType data; struct BiTNode *lchild,*rchild[,*parent]; }BiTNode,*BiTree;