InitBiTree(&D) Assign(t, &e, value); CreateBiTree(&t, definition) InsertChild(t, p, Lr, c);
InitBiTree(&T); Assign(T, &e, value); CreateBiTree(&T, definition); InsertChild(T, p, LR, c);
Clear bitree(&t); Destroy Bitree(&D); Delete Child(T, p, lr)
ClearBiTree(&T); DestroyBiTree(&T); DeleteChild(T, p, LR);
二叉树 的重要特性
二叉树 的重要特性
性质 在二叉树的第i层上至多有 2个结点。 (1≥1) 用归纳法证明 归纳基:i=层时,只有一个根结点 1=0- 归纳假设:假设对所有的j,1j<;,命题成立; 归纳证明:二叉树上每个结点至多有两棵子树, 则第i层的结点数=22×2=2l
性 质 1 ： 在二叉树的第 i 层上至多有 2 i-1个结点。 (i≥1) 用归纳法证明： 归纳基： 归纳假设： 归纳证明： i = 1 层时，只有一个根结点： 2 i-1 = 2 0 = 1； 假设对所有的 j，1≤ j i，命题成立； 二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2 i-2 2 = 2 i-1
性质2 深度为k的二叉树上至多含2k-1 个结点(k≥1)。 证明 基于上一条性质,深度为k的二叉 树上的结点数至多为 20+21+ +2k1=2k-1
性质 2 ： 深度为 k 的二叉树上至多含 2 k -1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉 树上的结点数至多为 2 0+21+ +2k-1 = 2k -1