PreOrder Traverse(l, visito) InOrder Traverse(l, visito) PostOrder Traverse(l, visito) LevelOrder(l, visito) 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 PreOrderTraverse(T, Visit()) InOrderTraverse(T, Visit()) PostOrderTraverse(T, Visit()) LevelOrderTraverse(T, Visit())
InitBitree(&T) 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(&t) Delete child(t, p, Lr) 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 ClearBiTree(&T) DestroyBiTree(&T) DeleteChild(T, p, LR)
二叉树 的重要特性 ☆y 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 二叉树 的重要特性
性质1 在二叉树的第i层上至多有x1个结点。 (i≥1) 用归纳法证明 归纳基:i=1层时,只有一个根结点 21=20=1 归纳假设:假设对所有的j,1≤j<,命题成立; 归纳证明:二叉树上每个结点至多有两棵子树, 则第i层的结点数≤2×2=21。 如大学计算机软学院
四川大学 计算机(软件)学院 • 性质 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