第五树和二叉树.pptVIP

张乃孝 算法与数据结构——C语言描述 树的子表表示法 小 结 树、树林、二叉树的一些基本概念和术语； 二叉链表存储结构 树、二叉树的周游 哈夫曼树的构造方法及应用 采用顺序表示，类型声明如下： struct SeqBTree /* 顺序树类型定义 */ { DataType nodelist[MAXNODE]; int n; /* 改造成完全二叉树后， 结点的个数 */ }； typedef struct SeqBTree *PSeqBTree; 5.4.2 链接表示 二叉树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。 struct BinTreeNode; /* 二叉树中结点 */ typedef struct BinTreeNode *PBinTreeNode; /* 结点的指针类型 */ struct BinTreeNode { DataType info; /* 数据域 */ PBinTreeNode llink; /* 指向左子女 */ PBinTreeNode rlink; /* 指向右子女 */ }; typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; A B D C E F I H G t A B ^ C ^ E F ^ I ^ ^ H ^ ^ G ^ ^ D ^ 图5.15 二叉树的二叉链表表示 t A ? B ? D ? ? C E ? F I ? ? H ? ? G ? ? 图5.15 三叉链表表示 t a ? b ? d c ? e ? ? h ? i ? j ? ? f ? g ? 图5.7 树的长子兄弟表法 5.2.2 树林的存储表示 父指针表示法 子表表示法 长子-兄弟表示法 树林的父结点表示方法 1 2 ? 3 ? 5 9 ? 8 ? 6 ? 7 树林的子表表示法 t A ? B D ? C ? E ? H ? J ? ? K ? F ? G ? 树林的长子兄弟表示法 5.3 二叉树 5.3.1 二叉树的基本概念 5.3.2 二叉树的性质 5.3.3 二叉树的基本运算 5.3.4 二叉树的周游 5.3.5 树、树林与二叉树的转换 二叉树： 它是结点的有限集合，这个集合或者为空集 或者由一个根及两棵不相交的分别称作这个根 的“左子树”和“右子树”的二叉树组成。 它的每一个结点至多有两棵子树，并且子树 有左右之分，不能随意颠倒。 5.3.1 二叉树的基本概念 二叉树的基本形态： ? 左子树 右子树 右子树 左子树 （1）空二叉树 （2）只有一个根结点 （3）有根结点 和左子树 （4）有根结点 和右子树 （5）有根结点 和左，右子树 二叉树不是树的特殊情形，它们是两个概念。 树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。 （3）和（4）是两棵不同的二叉树，但作为树，它们是相同的