习题选讲-Complete Binary Search Tree.pdf

《习题选讲-Complete Binary Search Tree.pdf》由会员分享，可在线阅读，更多相关《习题选讲-Complete Binary Search Tree.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、树之 习题选讲树之 习题选讲 Complete Binary Search Tree 完 全二 叉 搜 索 树完 全二 叉 搜 索 树 题意理解题意理解 二叉搜索树二叉搜索树完全二叉树完全二叉树 R 小小 大大 输入：输入：1 2 3 4 5 6 7 8 9 0 输出：输出：6 3 8 1 5 7 9 0 2 4 0 12 3456 789 6 38 1579 024 树的表示法：链表树的表示法：链表 vs. 数组数组 需要的操作需要的操作 填写数字（某种遍历）填写数字（某种遍历） 层序遍历层序遍历 完全二叉树，不浪费空间完全二叉树，不浪费空间 层序遍历层序遍历 = 直接顺序输出直接顺序输出

2、数组完胜！数组完胜！ 核心算法核心算法 二叉搜索树二叉搜索树完全二叉树完全二叉树 R 小小 大大 输入：输入：1 2 3 4 5 6 7 8 9 0 0 12 3456 789 6 38 1579 024 排序：排序：0 1 2 3 4 5 6 7 8 9 核心算法核心算法 void solve( int ALeft, int ARight, int TRoot ) /* 初始调用为初始调用为 solve(0, N-1, 0) */ n = ARight ALeft + 1; if (n=0) return; L = GetLeftLength(n); /* 计算出计算出n个结点的树其左子树有

3、多少个结点个结点的树其左子树有多少个结点 */ TTRoot = AALeft + L; LeftTRoot = TRoot * 2 + 1; RightTRoot = LeftTRoot + 1; solve(ALeft, ALeft+L-1, LeftTRoot); solve(ALeft+L+1, ARight, RightTRoot); 排序后的排序后的 输入序列输入序列A结果树结果树T 从从A段中选出正确的数字，填到段中选出正确的数字，填到 TTRoot中中 排序排序 #include int main() qsort(A, N, sizeof(int), compare); int compare(const void*a, const void*b) return *(int*)a-*(int*)b; 计算左子树的规模计算左子树的规模 h = 1; n1= 21-1 h = 2; n2= 22-1 h = 3; n3= 23-1 2H 1 X 2H 1 + X = N H = log2(N+1X) log2(N+1) L = 2H1 1 + X? 最小最小X = 0 最大最大X = ？2H1 X = min X, 2H1