第6章树和二叉树 6.2二叉树的存储结构《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

第六章 树和二叉树 6.1 树的定义 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树的存储结构 6.5 哈夫曼树 二叉树的存储结构 1、 顺序存储结构 实现：按 满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树 a b c d e f g bt 0 1 2 3 4 5 6 7 8 9 10 11 结点 a b c d e ø ø ø ø f g 2、链式存储结构 －－－－ 二叉链表 typedef struct node { datatype data; struct node *lchild, *rchild; }bitree; lchild data rchild A B C D E F G 在n个结点的二叉链表中，有n+1个空指针域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ 空指针个数：2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1（性质3） =n+1 root 6.3 遍历二叉树和线索二叉树 二叉树的遍历 方法 先序遍历： （1）访问根结点，（2）先序遍历左子树，（3）先序遍历右子树 中序遍历： （1）中序遍历左子树，（2）访问根结点，（3）中序遍历右子树 后序遍历： （1）后序遍历左子树，（2）后序遍历右子树，（3）访问根结点 D L R LDR、LRD、DLR RDL、RLD、DRL A D B C D L R A D L R D L R > B > > D > > C D L R 先序遍历序列：A B D C 先序遍历: A D B C L D R B L D R L D R > A > > D > > C L D R 中序遍历序列：B D A C 中序遍历: A D B C L R D L R D L R D > A > > D > > C L R D 后序遍历序列： D B C A 后序遍历: B － ＋ / a * b － e f c d 先序遍历： 中序遍历： 后序遍历： - + a * b - c d / e f - + a * b - c d / e f - + a * b - c d / e f 练习： 算法 递归算法 前序遍历递归算法 (2) 中序遍历递归算法 (3) 后序遍历递归算法 void inorder(bitree *t) { if(t!=NULL) { inorder(t->lchild); printf("%d\t",t->data); inorder(t->rchild); } } void postorder(bitree *t) { if(t!=NULL) {printf("%d\t",t->data); postorder(t->lchild); postorder(t->rchild); } } ? ? next void preorder(bitree *t) { if(t!=NULL) { printf("%d\t",t->data); preorder(t->lchild); preorder(t->rchild); } } 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A C B D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T > 左是空返回 pre(T R); T > 左是空返回 T > 右是空返回 T > 左是空返回 T > 右是空返回 pre(T R); 先序序列：A B D C 以上采用的图示分析了先序遍历的结果，也可以采用第四章栈与队列所举