数据结构第五章树与二叉树教案.ppt

5.4 二叉树其他运算 2. 建立二叉树 设: i 结点所在为h 层 i=(2h-1-1)+1= 2h-1 j 结点所在 为h+1 层 j=(2h -1)+1 = 2h 结论: j=2i 1 2 3 4 5 6 7 8 9 10 11 12 i j 5.2.3 二叉树 的抽象数据类型 基本操作: void InitBTree(BTreeType BT)； void CreateBTree (BTreeType BT, char* a); bool BTreeEmpty(BTreeType BT); void TraverseBTree(BTreeType BT); int BTreeDepth(BTreeType BT); void PrintBTree(BTreeType BT); void ClearBTree(BTreeType BT); 1．顺序存储结构 #define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef { ElemType SqBiTree[MAX_TREE_SIZE]; // 0号单元存储根结点 }SqBiTree bt; 5.2.4 二叉树的存储结构 例如: 1 A B C D E F 2 5 14 3 7 A B D C E F 0 1 2 3 4 5 6 7 8 9 10 1112 1314 2．链接存储结构 二叉链表 2．带双亲链表 E ? A D B C F ? ? ? ? ? ? root left data right 结点结构: 1. 二叉链表 struct BTreeNode { ElemType data; BTreeNode * left; BTreeNode * right; }; 类型描述如下: left data right 结点结构: A E ? D ? B ? C ? ? F ? ? root ? 2．三叉链表 parent left data right 结点结构: 5.3 二叉树 的遍历 顺着某一条有哪些信誉好的足球投注网站路径巡访二叉树 中的结点，使得每个结点均被访 问一次，而且仅被访问一次。 一、问题的提出 “访问”的含义可以很广 如：输出结点的信息等。 对“二叉树”而言，可以有三条有哪些信誉好的足球投注网站路径： 1．先上后下的按层次遍历； 2．先左（子树）后右（子树） 的遍历； 3．先右（子树）后左（子树） 的遍历。 二、先左后右的遍历算法 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法 若二叉树为空树，则空操作； 否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 先（根）序的遍历算法： D L R D L R A B C D E F A B C D E F 先序遍历 D L R 先序遍历序列: A B C D E F A B D C E H G F K 先序遍历序列: A B D C E H G F K 若二叉树为空树，则空操作； 否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 中（根）序的遍历算法： D L R L D R A B C D E F A B C D E F 中序遍历 L D R 中序遍历序列: B C A D F E A B D C E H G F K 中序遍历序列: B C D A E F G K H F K G H E C D B A B C D A E F G K H 若二叉树为空树，则空操作； 否则 （1）后序遍历左子树； （2）后序遍历右子树。 （3）访问根结点； 后（根）序的遍历算法： D L R L R D A B C D E F A B C D E F 后序遍历 L R D 后序遍历序列: C B F E D A A B C G F H E I D 后序遍历序列: G D H E B I F C A A B C G F H E I