二叉树基本知识.pptVIP

typedef struct CTNode { int child; struct CTNode *nextchild; } *ChildPtr; 孩子结点结构: child nextchild C语言的类型描述: typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 } CTBox; 双亲结点结构 data firstchild typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; 树结构: A B C D E F G root A B C E D F G A B C E D F G 三、树的二叉链表 (孩子-兄弟）存储表示法 root typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; C语言的类型描述: 结点结构: firstchild data nextsibling 谢谢！ SDUT_ACM 培训 数据对象 D： D是具有相同特性的数据元素的集合。 若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, …, Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。 数据关系 R： 结点: 结点的度: 树的度: 叶子结点: 分支结点: 数据元素+若干指向子树的分支 分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点 D H I J M (从根到结点的)路径： 孩子结点、双亲结点、 兄弟结点、堂兄弟 祖先结点、子孙结点 结点的层次: 树的深度： 由从根到该结点所经分支和结点构成 A B C D E F G H I J M K L 假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1 树中叶子结点所在的最大层次 任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点， F 被称为子树森林 森林： 是 m（m≥0）棵互 不相交的树的集合 A root B E F K L C G D H I J M F 二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。 A B C D E F G H K 根结点 左子树 右子树 E F G 两类特殊的二叉树： 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j 二叉树的五种基本形态： N L R L R 空树 只含根结点 N N N 右子树为空树 左子树为空树 左右子树均不为空树 二叉树的主要基本操作： 查 找 类 插 入 类 删 除 类 Root(T) // 求树的根结点 查找类： Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeEmpty(T) // 判定树是否为空树 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历 InitTree(T) // 初始化置空树 插入类： CreateTree(T, definition) // 按定义构造树 Assign(T, cur_e,