《二叉树的基本知识精编版》由会员分享，可在线阅读，更多相关《二叉树的基本知识精编版（36页珍藏版）》请在金锄头文库上搜索。
1、树 SDUT ACM培训 数据对象D D是具有相同特性的数据元素的集合 若D为空集 则称为空树 否则 1 在D中存在唯一的称为根的数据元素root 2 当n 1时 其余结点可分为m m 0 个互不相交的有限集T1 T2 Tm 其中每一棵子集本身又是一棵符合本定义的树 称为根root的子树 数据关系R 结点 结点的度 树的度 叶子结点 分支结点 数据元素 若干指向子树的分支 分支的个数 树中所有结点的度的最大值 度为零的结点 度大于零的结点 从根到结点的 路径 孩子结点 双亲结点 兄弟结点 堂兄弟祖先结点 子孙结点 结点的层次 树的深度 由从根到该结点所经分支和结点构成 假设根结点的层次为1 第
2、l层的结点的子树根结点的层次为l 1 树中叶子结点所在的最大层次 任何一棵非空树是一个二元组Tree root F 其中 root被称为根结点 F被称为子树森林 森林 是m m 0 棵互不相交的树的集合 A root F 二叉树或为空树 或是由一个根结点加上两棵分别称为左子树和右子树的 互不交的二叉树组成 根结点 左子树 右子树 E F G 两类特殊的二叉树 满二叉树 指的是深度为k且含有2k 1个结点的二叉树 完全二叉树 树中所含的n个结点和满二叉树中编号为1至n的结点一一对应 二叉树的五种基本形态 N L R L R 空树 只含根结点 N N N 右子树为空树 左子树为空树 左右子树均不为
3、空树 二叉树的主要基本操作 查找类 插入类 删除类 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 value 给当前结点赋值 I
4、nsertChild T p i c 将以c为根的树插入为结点p的第i棵子树 ClearTree T 将树清空 删除类 DestroyTree T 销毁树的结构 DeleteChild T p i 删除结点p的第i棵子树 二叉树的重要特性 性质1 在二叉树的第i层上至多有2i 1个结点 i 1 性质2 深度为k的二叉树上至多含2k 1个结点 k 1 性质3 对任何一棵二叉树 若它含有n0个叶子结点 n2个度为2的结点 则必存在关系式 n0 n2 1 性质4 具有n个结点的完全二叉树的深度为 log2n 1性质5若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号 则对完全二叉树中任意一
5、个编号为i的结点 1 若i 1 则该结点是二叉树的根 无双亲 否则 编号为 i 2 的结点为其双亲结点 2 若2i n 则该结点无左孩子 否则 编号为2i的结点为其左孩子结点 3 若2i 1 n 则该结点无右孩子结点 否则 编号为2i 1的结点为其右孩子结点 二叉树的存储结构 二 二叉树的链式存储表示 一 二叉树的顺序存储表示 defineMAX TREE SIZE100 设二叉树的最大结点数typedefstruct ElemType data 初始化时分配存储空间intnodeNum 二叉树中的结点数目 SqBiTree 一 二叉树的顺序存储表示 0号单元存储根结点 例如 ABD 1 4
6、0 13 2 6 k 1 2 1 2k 1 C E F 二 二叉树的链式存储表示 1 二叉链表 2 三叉链表 3 双亲链表 root 结点结构 1 二叉链表 typedefstruct 结点结构TElemTypedata structBiTNode lchild rchild 左右孩子指针 BiTNode BiTree 结点结构 C语言的类型描述如下 root 2 三叉链表 结点结构 typedefstruct 结点结构TElemTypedata structTriTNode lchild rchild 左右孩子指针structTriTNode parent 双亲指针 TriTNode Tri
7、Tree 结点结构 C语言的类型描述如下 结点结构 3 双亲链表 LRTag LRRRL n 6 typedefstruct 结点结构TElemTypedata int parent 指向双亲的指针charLRTag 左 右孩子标志域 BPTNodetypedefstruct 树结构BPTNodenodes MAX NODE SIZE intnum node 树中含结点数目introot 根结点的位置 BPTree 树的三种存储结构 一 双亲表示法 二 孩子链表表示法 三 树的二叉链表 孩子 兄弟 存储表示法 r 0n 6 dataparent 一 双亲表示法 typedefstructPTN
8、ode Elemdata intparent 双亲位置域 PTNode defineMAX TREE SIZE100 结点结构 C语言的类型描述 typedefstruct PTNodenodes MAX TREE SIZE intr n 根结点的位置和结点个数 PTree 树结构 r 0n 6 datafirstchild 二 孩子链表表示法 1000224 parent typedefstructCTNode intchild structCTNode nextchild ChildPtr 孩子结点结构 C语言的类型描述 typedefstruct Elemdata ChildPtrfirstchild 孩子链的头指针 CTBox 双亲结点结构 typedefstruct CTBoxnodes MAX TREE SIZE intn r 结点数和根结点的位置 CTree 树结构 root 三 树的二叉链表 孩子 兄弟 存储表示法 root typedefstructCSNode Elemdata structCSNode firstchild nextsibling CSNode CSTree C语言的类型描述 结点结构 谢谢
