09年自考《数据结构》各章要点二[2]

满二叉树是一棵深度为k结点数为(^k)的二叉树完全二叉树是满二叉树在最下层自右向左去处部分结点

二叉树的顺序存储结构就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中(存储前先将其画成完全二叉树)

树的存储结构多用的是链式存储BinTNode的结构为lchild|data|rchild把所有BinTNode类型的结点加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构称为二叉链表它就是由根指针root唯一确定的共有n个指针域n+个空指针

根据访问结点的次序不同可得三种遍历先序遍历(前序遍历或先根遍历)中序遍历(或中根遍历)后序遍历(或后根遍历)时间复杂度为O(n)

利用二叉链表中的n+个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针这些附加的指针就称为线索加上线索的二叉链表就称为线索链表线索使得查找中序前趋和中序后继变得简单有效但对于查找指定结点的前序前趋和后序后继并没有什么作用

树和森林及二叉树的转换是唯一对应的

转换方法

·树变二叉树兄弟相连保留长子的连线

·二叉树变树结点的右孩子与其双亲连

·森林变二叉树树变二叉树各个树的根相连

树的存储结构

·有双亲链表表示法结点data | parent对于求指定结点的双亲或祖先十分方便但不适于求指定结点的孩子及后代

·孩子链表表示法为树中每个结点data | next设置一个孩子链表firstchild并将data | firstchild存放在一个向量中

·双亲孩子链表表示法将双亲链表和孩子链表结合

·孩子兄弟链表表示法结点结构leftmostchild |data | rightsibing附加两个分别指向该结点的最左孩子和右邻兄弟的指针域

[] [] [] [] [] [] [] [] [] [] [] []