Parent 初始条件:二叉树T存在,e是T中某个结点 操作结果:若e是T的非根结点,则返回它的双亲, 否则返回"空" Leftchild T,e); 操作结果:返回e的左孩子。若e无左孩子,则 返回"空"。 Rightchild(t, e: 个结点 操作结果:返向e的右孩子。若e无右孩子,则 返回"空"。 Leftsibling(T, e) 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的左兄弟。若e是其双亲的左 孩子或无左兄弟,则返回空
• Parent(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：若e是T的非根结点，则返回它的双亲， 否则返回"空" 。 LeftChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左孩子。若 e 无左孩子，则 返回"空" 。 RightChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的右孩子。若 e 无右孩子，则 返回"空" 。 LeftSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左兄弟。若 e 是其双亲的左 孩子或无左兄弟，则返回"空"
° Rightsibling(Te) 操结某:返e的若凭第。著是箕爰亲的右孩子或无 右兄弟,则返回"空"。 PreOrderTraverse(T, visit 初始条件:二文树T存在,st是对结点操作的应用函数。 操作结果:先序遍历T,对每个结点调用函数vsit一次且 仅一次。一旦vst0失败,则操作失败。 InOrder Traverse(T, vs 撰作结巢:中序通历,对每个结点调用函数Vst—次置” 仅一次。一旦 visit0失败,则操作失败。 PostorderTraverse(T visito 初始条件:二叉树T存在,vs是对结点操作的应用函数。 操作结果:后序遍历T,对每个结点调用函数Ⅴst→次且 仅一次。一旦vst0失败,则操作失败
• RightSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 的结点。 操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无 右兄弟，则返回"空" 。 PreOrderTraverse(T, visit()); 初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且 仅一次。一旦 visit() 失败，则操作失败。 InOrderTraverse(T, vsit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且 仅一次。一旦 visit() 失败，则操作失败。 PostOrderTraverse(T, visit()); 初始条件：二叉树T存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次且 仅一次。一旦 visit() 失败，则操作失败
LevelOrderTraverse(T, visito) 初始条件:二又树T存在,vst是对结点操作 的应用函数。 操作结果:层序遍历T,对每个结点调用函数 vit一次且仅一次。一旦vs敢t(失败,则操作失败。 加工型操作} ClearBiTree(&T); 初始条件:二叉树T存在。 操作结果:将二叉树T清为空树。 Assign(&T, &e, value) 初始条件:二叉树T存在,e是T中某个结点。 操作结果:结点e赋值为vaue
• LevelOrderTraverse(T, visit()); 初始条件：二叉树 T 存在，visit 是对结点操作 的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 {加工型操作} ClearBiTree(&T); 初始条件：二叉树 T 存在。 操作结果：将二叉树 T 清为空树。 Assign(&T, &e, value); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：结点 e 赋值为 value
Insertchild(&T, p, LR,c); 初始条件:二叉树T存在,p指向T中某个结 点,LR为0或1,非空二叉树c 不相女且石子树 为空 操作结果:根据LR为0或1,插入c为T中 所指结点的左或右子树。p所指结点原有左或右子树 为c的右子树。 Delete Child( &T, p, LR 初始条件:二叉树T存在,p指向T中某个结 点,LR为0或1。 操作结果:根据LR为0或1,删除T中p所 指结点的左或右子树。 3 ADT BinaryTree
• InsertChild(&T, p, LR, c); 初始条件：二叉树 T 存在，p 指向 T 中某个结 点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树 为空。 • 操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指结点原有左或右子树成 为 c 的右子树。 DeleteChild(&T, p, LR); 初始条件：二叉树 T 存在，p 指向 T 中某个结 点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所 指结点的左或右子树。 } ADT BinaryTree
622二叉树的几个特性 在二叉树的第i层上至多有21个结点 深度为k的二叉树中至多含有2k-1个结点, (k1) 三、对任何一棵二叉树T,如果其终端结点数 为n,度为2的结点数为n2,则n=n2+1
6.2.2 二叉树的几个特性 • 一、在二叉树的第 i 层上至多有 2 i-1 个结点 (i≥1)。 • 二、深度为k的二叉树中至多含有 2 k -1 个结点， (k≥1)。 • 三、对任何一棵二叉树 T，如果其终端结点数 为n0，度为2的结点数为n2，则n0 =n2+ 1