树第五章方效林
方效林 第五章 树
本章主要内容树的基本概念二叉树二叉树的存储表示二叉树的遍历及其应用■二叉树遍历的非递归算法二叉树的计数树与二叉树的转换堆Huffman树及其应用
本章主要内容 ◼ 树的基本概念 ◼ 二叉树 ◼ 二叉树的存储表示 ◼ 二叉树的遍历及其应用 ◼ 二叉树遍历的非递归算法 ◼ 二叉树的计数 ◼ 树与二叉树的转换 ◼ 堆 ◼ Huffman树及其应用
堆(Heap)关键字按完全二叉树顺序存储在一维数组中称为最小堆口若K,≤K2i+1&&K,≤K2i+2(小于孩子),口若K;≥K2i+1 && K;≥K2i+2(大于孩子),称为最大堆不失一般性，只介绍最小堆完全二叉树顺序表示完全二叉树顺序表示K; ≤K2i1 && K,≤ K2i+2K,≥ K2i1 && K, ≥K2i+2
堆(Heap) ◼ 关键字按完全二叉树顺序存储在一维数组中 若Ki K2i+1 && Ki K2i+2(小于孩子)，称为最小堆 若Ki K2i+1 && Ki K2i+2(大于孩子)，称为最大堆 完全二叉树顺序表示 Ki K2i+1 && Ki K2i+2 完全二叉树顺序表示 Ki K2i+1 && Ki K2i+2 不失一般性，只介绍最小堆
堆(Heap)将一组用数组存放的任意数据调整成堆口自下向上扫描（从（n-2)/2位置开始），向下调整向下调整过程：每次与更小的孩子交换直到没有孩子，或比两个孩子都小，则停止3从i=3开始扫描，这是由于共有n=8个数，从i=（n-2)/2=3开始扫描（即最后一个叶子结点的父结点开始，09小于孩子，不用调整
堆(Heap) ◼ 将一组用数组存放的任意数据调整成堆 自下向上扫描(从(n-2)/2位置开始)，向下调整 从i = 3开始扫描，这是由于共有n=8个数， 从i = (n-2)/2=3开始扫描(即最后一个 叶子结点的父结点开始)， 09小于孩子，不用调整 i=3 向下调整过程： 每次与更小的孩子交换， 直到没有孩子，或比两个孩子都小，则停止
堆(Heap)将一组用数组存放的任意数据调整成堆自下向上扫描（从（n-2)/2位置开始），向下调整向下调整过程：每次与更小的孩子交换直到没有孩子，或比两个孩子都小，则停止扫描到i=278大于其中一孩子，向下调整78与孩子中更小的69交换
堆(Heap) ◼ 将一组用数组存放的任意数据调整成堆 自下向上扫描(从(n-2)/2位置开始)，向下调整 i=2 扫描到i = 2 78大于其中一孩子，向下调整 78与孩子中更小的69交换 向下调整过程： 每次与更小的孩子交换， 直到没有孩子，或比两个孩子都小，则停止