数据结构严蔚敏第六章.ppt

第六章 树和二叉树 ;教学目的和要求;;树形结构;A;6.1 树的类型定义;6.1 树的类型定义;数据对象 D：;A; 基本操作：; Root(T) // 求树的根结点 ;InitTree(T) // 初始化置空树 ; ClearTree(T) // 将树清空 ;对比树型结构和线性结构的结构特点;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;基 本 术 语;结点:;(从根到结点的)路径：;任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林;6.2 二叉树的类型定义 ; 二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。;二叉树的五种基本形态：; 二叉树的主要基本操作：; Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());; InitBiTree(T); Assign(T, e, value); CreateBiTree(T, definition); InsertChild(T, p, LR, c);;ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR);;二叉树的重要特性; 性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i≥1);性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。; 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。;两类特殊的二叉树：; 性质 4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n? +1 。;性质 5 ：;6.3 二叉树的存储结构;#define MAX_TREE_SIZE 100 // 二叉树的最大结点数 typedef TElemType SqBiTree[MAX_ TREE_SIZE]; // 0号单元存储根结点 SqBiTree bt;;例如:;二、二叉树的链式存储表示;A;typedef struct BiTNode { // 结点结构 TElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;;A; typedef struct TriTNode { // 结点结构 TElemType data; struct TriTNode *lchild, *rchild; // 左右孩子指针 struct TriTNode *parent; //双亲指针 } TriTNode, *TriTree;;0 1 2 3 4 5 6; typedef struct BPTNode { // 结点结构 TElemType data; int *parent; // 指向双亲的指针 char LRTag; // 左、右孩子标志域 } BPTNode typedef struct BPTree{ // 树结构 BPTNode nodes[MAX_TREE_SIZE]; int num_node; // 结点数目 int root; // 根结点的位置 } BPTree;