二叉树及其遍历.ppt

*/39 二叉树遍历及其算法 主讲人: 程玉胜 2008.06.17 《数据结构》申报精品课程录像 内容提要 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 内容提要 (一) 二叉树的定义 度不大于2，且子树有左右之分，不能颠倒 二叉树的5种基本形态 D D L D L R D R (a) (b) (c) (d) (e) 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 (一) 二叉树性质应用(1) 如果一棵二叉树有10个叶子结点，有8个结点仅有左孩子，12个结点仅有右孩子，问该二叉树有多少个结点？ 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 思考 解 易知：n=n0+n1+n2 已知：n0＝10，n1＝8＋12＝20 P124，性质3知：n2＝n0-1=9 所以，n=10＋20＋9＝39 (一) 二叉树性质应用(2） 已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？ 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 思考 解1 P124，性质4知：树的深度1＋log2100＝7 P124，性质2知：上面6层结点数26-1=63 所以，第7层有100－63＝37个叶子 它们是第6层中19个结点的孩子， 因此第6层中没有孩子的结点是32－19＝13 所以，叶子结点数37＋13＝50 第6层 26-1=32 (一) 二叉树性质应用(2） 已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？ 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 思考 解2 P124，性质5知：编号100的结点父亲是100/2=50 因此从51～100是叶子结点 所以，叶子结点数100－50＝50 i 2i+1 2i i/2 内容提要 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 内容提要 (二) 二叉树存储结构(1) 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 顺序存储结构 a b c d a b c d … 二叉链表存储结构 typedef char datatype typedef struct BiTNode { datatype data; struct BiTNode *lchild,*rchild;//左右指针 } (二) 二叉树存储结构(2) 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 二叉链表存储结构 a ^ b ^ c ^ ^ d ^ 图有多少个空指针？5 在n个结点的二叉链表中，空(^)指针数有多少个？ 思考 解 n个结点,共有2n个指针 其中,n-1个结点有父亲（根除外） 所以，2n-(n－1）=n+1 n+1 (二) 二叉树遍历方法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 遍历二叉树定义： 指按照某种顺序访问二叉树的每个结点一次且仅被“访问”一次。 常见“访问”的方法： void visit(datatype e) { printf(e); } //实际使用时，加上格式控制符 D L R 遍历时，限定先左后右： LDR；DLR；LRD (二) 先序遍历算法 复习 二叉树遍历及算法 遍历序列求解 遍历算法的拓展 遍历非递归算法 先序(DLR)遍历 (2)遍历左子树(L) (3)遍历右子树(R) (1)访问根结点(D) void PreOrder(struct BiTNode *T) { if (T!=NULL) visit(T-data); PreOrder(T-lchild); PreOrder(T-rchild); }