数据结构复习课件：Data Structure-Binary Tree.ppt

1、第五章 二叉树李李 睿睿College of SoftwareHunan UniversityChangsha Hunan P.R.CCopyright 2004 by Li Rui2 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。 5.1 树的定义和基本术语 定义：树(Tree)是n(n=0)个结点

2、的有限集T，T为空时称为空树，否则它满足如下两个条件： （1）有且仅有一个特定的称为根(Root)的结点；Copyright 2004 by Li Rui3(2)其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。5.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。5.2.1 二叉树的定义定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左

3、右子树都是二叉树。 这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。Copyright 2004 by Li Rui5二叉树的相关概念二叉树的相关概念 （1）结点的度。结点所拥有的子树的个数称为该结点的度。 （2）叶结点。度为0的结点称为叶结点，或者称为终端结点。 （3）分枝结点。度不为0的结点称为分支结点，或者称为非终端结点。一棵树的结点除叶结点外，其余的都是分支结点。 （4）左孩子、右孩子、双亲。树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。（5）路径、路径长度。如果一棵树的一串结点n1,n2,nk有

4、如下关系：结点ni是ni+1的父结点（1i=1)。 采用归纳法证明此性质。 当i=1时，只有一个根结点，2i-1=20 =1,命题成立。 现在假定多所有的j，1=j=1).深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，： EkI=1（第i层上的最大结点数）= EkI=12i-1=2k 1 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn0n1n2 (5-1)再看二叉树中的分支数，除根结点外，其余结点都有一

5、个进入分支，设B为二叉树中的分支总数， 则有：NB1。Copyright 2004 by Li Rui10由于这些分支都是由度为1和2的结点射出的，所有有： Bn1+2*n2 NB1n12n21 （52)由式（51）和（52）得到： n0+n1+n2=n1+2*n2+1 n0n21下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图5.9就是一棵满二叉树，对结点进行了顺序编号。如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图5.9 满二叉树1234561234571236

6、7(a)完全二叉树(b)非完全二叉树( c)非完全二叉树图5.10 完全二叉树则称这样的二叉树为完全二叉树，图5.10（b）、c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k1层。 （2）对任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为log2n 1。符号 x 表示不大于x的最大整数。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-11n=2k-1 或 2k-1=n2k取对数得到：k1=log2nk 因为k是整数。所以有：k log2n 1。 性质5

7、： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第 log2n +1层，每层从左到右),则对任一结点i（1=i1，则其双亲是结点 i/2 。 （2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。 I/2iI+12i2i+1 2(I+1)2i+3I+12(I+1)2i+3i2i2i+1图5.11 完全二叉树中结点I和i+1(a)I和i+1结点在同一层 (b)I和i+1结点不在同一层如图5.11所示为完全二叉树上结点及其左右孩子结点之间的关系。 在此过程中，可以从（2）和（3）推出（1），所以

8、先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3n，此时结点i无右孩子。对于i1，可分为两种情况： （1）设第j（1=jn，则无左孩子：其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1n，则无右孩子。 （2）假设第j（1=j=log2n)层上的某个结点编号为i（2e(j-1)=i=2ej-1),且2i11时，如果i为左孩子，即2（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕。Copyright 2004

9、 by Li Rui18二叉树的抽象数据类型二叉树结点的ADT template class BinNodepublic: virtual Elem& val()=0; virtual void setVal(const Elem&)=0; virtual BinNode* left()=0; virtual BinNode* right()=0; virtual void setLeft(BinNode*)=0; virtual void setLeft(BinNode*)=0 ; virtual bool isLeaf()=0;Copyright 2004 by Li Rui195.2.3

10、 二叉树的存储结构1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100Typedef telemtype sqbitreemax-tree-size;Sqbitree bt 从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ Copy

11、right 2004 by Li Rui20ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12完全二叉树abcdefghijklCopyright 2004 by Li Rui21ABCDEFG 表示该处没有元素存在仅仅为了好理解ABCDEFG一般二叉树Copyright 2004 by Li Rui22（2）二叉树的二叉动态链式存储表示二叉树的二叉动态链式存储表示1、结点结构和示例leftChild data rightChildABCDEFrootABCDEFrootCopyright 2004 by Li Rui23二叉树的二叉链表存储表示template c

12、lass BinaryTree;template class BinTreeNode firend class BinaryTree;private: Elem data; BinTreeNode * lchild; BinTreeNode * rchild;public: BinTreeNode()lchild=rchild=NULL; BinTreeNode(Elem e,BinNodePtr*l=NULL, BinNodePtr*r=NULL) data=e; lchild=l; rchild=r; BinTreeNode() Copyright 2004 by Li Rui24二叉树的

13、二叉链表存储表示Elem val()return data;void setVal(const Elem e)data=e;inline BinTreeNode* left()return lchild;inline BinTreeNode* right()return rchild;void setLeft(BinTreeNode* left)lchild=left;void setRight(BinTreeNode* right)rchild=right; bool isLeaf() return (lchild=NULL)&(rchild=NULL);有时也可用数组的下标来模拟指针,即开

14、辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;Copyright 2004 by Li Rui25template class BinaryTreeprivate: BinTreeNode *root; Elem Refvalue; BinTreeNode *Parent (BinTreeNode *start, BinTreeNode *current); void Traverse (BinTreeNode *current, ostream & out) const void destroy (BinTreeNode *current);pub

15、lic: Virtual BinaryTree (Elem value): root (NULL), Refvalue (value) Virtual BinaryTree( ) destroy (root); Virtual bool IsEmpty( ) return root = = NULL ? true :false; Virtual BinTreeNode *Parent (BinTreeNode *current) return Parent (root, current); Copyright 2004 by Li Rui263、部分成员函数的实现template void B

16、inaryTree : destroy (BinTreeNode *current) /删除以current为根的子树 if (current != NULL) destroy (current - leftChild); /删除current的左子树 destroy (current - rightChild); /删除current的右子树 delete current; /删除current 算法中，、两递归调用语句可互换，它只关系到左右子树中，哪一个先删，哪一个后删。 语句不能同和语句互换，因为那样将导致一个子树甚至两个子树无法删。Copyright 2004 by Li Rui27t

17、emplate BinTreeNode *BinaryTree : Parent (BinTreeNode *start, BinTreeNode *current) if (start = = NULL | | current = = start) return NULL; if (start - leftChild = = current | | start - rightChild = = current) return start; /start是双亲 BinTreeNode *p; if (p = Parent (start - leftChild, current) != NULL

18、) return p; /在左子树找 else return Parent (start - rightChild, current); /在右子树找template void Binary Tree : Traverse (BinTreeNode *current, ostream & out) const /搜索并输出根为current的二叉树 if (current != NULL) out data leftChild, out); /搜索并输出左子树 Traverse (current - rightChild, out); /搜索并输出右子树Copyright 2004 by Li

19、 Rui285.3 5.3 遍历二叉树（遍历二叉树（Traversal Binary TreeTraversal Binary Tree）一、一、TBT概述概述1、定义 按某种次序，访问所有结点，使每个节点都被访问且尽访问一次的运算叫TBT。 “访问”包括输出结点值，修改值，统计等以不破坏BT的结构为原则。 TBT是对二叉树进行运算的基础性操作。Copyright 2004 by Li Rui29一、一、TBT概述概述2、次序（V根，L左子树，R右子树） 先序遍历 中序遍历 后序遍历先右后左：VRLRVLRLV先左后右：VLRLVRLRVbtABCDEFGHIJVLR输出序列：A B D E

20、G HI J C FLVR输出序列：D B G EI H J A C FLRV输出序列：D G I JH E B F C ACopyright 2004 by Li Rui30二、二、TBT的递归算法的递归算法1、中序遍历（ inorder traversal）template void BinaryTree : InOrder ( ) InOrder (root); /公共函数，调用私有函数完成遍历template void BinaryTree : InOrder (BinTreeNode *current) if (current != NULL) /当current = = NULL，

21、则递归终结 InOrder (current - leftChild); /中序遍历左子树 cout data; /访问根结点 InOrder (current - rightChild); /中序遍历右子树/abcdef 对 a+b*(c-d)-e/f 表达式的语法树，中序遍历得到其中缀表示： a + b * c d e / f Copyright 2004 by Li Rui312、先序遍历（ preorder Traversal）template void BinaryTree : PreOrder (BinTreeNode *current) /私有函数 if (current !=

22、NULL) cout data; PreOrder (current - leftChild); PreOrder (current - rightChild); /abcdef 对表达式a+b*(c-d)-e/f 的语法树进行先序遍历得到其前缀表示： + a * b c d / e f二、二、TBT的递归算法的递归算法Copyright 2004 by Li Rui323、后序遍历（ postorder traversal）template void BinaryTree : PostOrder (BinTreeNode *current) /私有函数 if (current != NULL

23、) PostOrder (current - leftChild); PostOrder (current - rightChild); cout data; 二、二、TBT的递归算法的递归算法/abcdef 对表达式 a+b*(c-d)-e/f 的语法树进行后序遍历得到其后缀表示： a b c d * + e f / Copyright 2004 by Li Rui33三、三、TBT的非递归算法的非递归算法1、递归算法中栈的使用TBT递归算法的简化traversal (BinTreeNode *current) if (current != NULL) traversal (current

24、- leftChild); traversal (current - rightChild); Copyright 2004 by Li Rui34三、三、TBT的非递归算法的非递归算法1、递归算法中栈的使用执行过程中栈的情况和current的变化举例当左向递归则current的值进栈若current = = NULL，则出栈，current以栈顶值去执行右向递归直到栈空（top = -1）和current = = NULL为止currenttopad1ad2ad3ad4ad5stackAB C DE ad1ad2ad3ad4ad5-1 0 1 2 3Copyright 2004 by Li

25、Rui352、利用栈的前序和中序遍历非递归算法template void BinaryTree : PreOrder ( ) stack BinTreeNode * st; BinTreeNode *p = root; do while (p != NULL) cout data; st. Push (p); p = p -leftChild; if ( St. length()!=0) st. pop (p ); p = p - rightChild; while (p != NULL | | st.length ( )!=0);算法描述 p不空则p进栈，沿左子树方向传递指针 若p空但栈不空

26、，出栈，p以栈顶值沿右子树方向传递指针 循环下去，直到p和栈都空为止执行中栈的情况和指针的变化与递归程序相同对于中序遍历只需调整输出语句位置即可三、三、TBT的非递归算法的非递归算法Copyright 2004 by Li Rui363、层次遍历template void BinaryTree : LevelOrder ( ) queue BinTreeNode * qu; BinTreeNode *p = root; qu.Enqueue(p); while (qu.DeQueue (p ) cout data leftChild != NULL) qu.EnQueue (p - leftC

27、hild); if (p - rightChild != NULL) qu.EnQueue (p - rightChild);三、三、TBT的非递归算法的非递归算法Copyright 2004 by Li Rui37层次遍历是指直上至下，从左到右访问结点只有采用队列来存放结点地址才能实现层次遍历3、层次遍历frpad1ad2ad3ad4ad5ad60 1 2 3 4 5 6 7ABCDEFrootad1ad2ad3ad4ad5ad6Copyright 2004 by Li Rui385.4 5.4 线索化二叉树线索化二叉树一、概述一、概述1、问题提出 遍历是二叉树最基本的运算，为避免再次遍历的

28、麻烦，可将首次遍历得到的信息存于一个线性结构中。 具有n个结点的链式存贮的二叉树中，有n+1个链域是空的，能否充分利用这些空的链域来存放结点的前趋指针和后继指针呢？Copyright 2004 by Li Rui39一、概述一、概述2、实现策略结点中增加两个标记域 两标记域取值范围是0，1。各只占一个二进制位，只增加很少的额外空间开销。rightChildleftChild leftThread data rightThread指向左孩子0指向前驱1指向右孩子0指向后继1Copyright 2004 by Li Rui403、线索二叉树 指向前驱和指向后继的指针叫做线索（Thread）。 具有

29、线索的二叉树叫做线索二叉树。 因遍历的次序有三种，所以线索二叉树也分前、中、后序这三种。 中序遍历线索二叉树结构示例 若根的左子树不空，侧其最左下角的结点为中序遍历的第一个结点，否则根为中序遍历的第一个结点。 若根的右子树不空，侧其最右下角的结点为中序遍历的最后一个结点，否则根为中序遍历的最后一个结点。0E0 0B0 1F0 0D1 1G1 1C1 1A1 rootEDGrootBAFCNULLNULLCopyright 2004 by Li Rui41二、中序线索二叉树的类定义二、中序线索二叉树的类定义1、类声明template class ThreadTree;template class

30、 ThreadNode friend class ThreadTree ;private: int leftThread, rightThread; ThreadNode * leftChild, rightChild; Elem data;public: ThreadNode (const Elem item) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) Elem getData ( ) const return data;Copyright 2004 by Li Ru

31、i42template class ThreadTree private : ThreadNode *root; InThread (ThreadNode *current, ThreadNode *pre);public : ThreadTree( ) : root(NULL) ; ThreadNode *First(ThreadNode *current); ThreadNode *Last(ThreadNode * current); ThreadNode *Next(ThreadNode *current); ThreadNode *Prior(ThreadNode *current)

32、; void Inorder( ); /从第一个结点开始沿着后继方向遍历二叉树 Copyright 2004 by Li Rui432、成员函数的实现template ThreadNode * ThreadTree: First(ThreadNode * current) /返回以current为根指针的线索二叉树中序序列下的第一个结点 ThreadNode * p = current; while(p - leftThread = = 0) p = p - leftChild; /找最左下角的结点 return p;template ThreadNode * ThreadTree : Nex

33、t (ThreadNode * current) ThreadNode *p = current - rightChild; if (current - rightThread = = 0) return first (p); else return p;currentpnextCopyright 2004 by Li Rui44template ThreadNode * ThreadTree: last(ThreadNode * current) ThreadNode * p = current; while(p - rightThread = = 0) p = p - rightChild

34、; /找右下角结点 return p;template ThreadNode * ThreadTree : Prior (ThreadNode * current) ThreadNode *p = current - leftChild; if (current - leftThread = = 0) return last (p); else return p;pcurrentpriorCopyright 2004 by Li Rui45template void ThreadTree : InOrder ( ) ThreadNode * p;/在线索二叉树中进行中序遍历 for (p =

35、first(root); p != NULL; p = Next(p) cout data endl; template void ThreadTree : InThread (ThreadNode * current, ThreadNode * &pre) /通过中序遍历对以current为根的二叉树进行线索化 if (current != NULL) InThread (current - leftChild, pre); /左子树线索化 if (current - leftChild = = NULL) current - leftChild = pre; current - leftT

36、hread = 1; /建立当前结点的前驱线索 if (pre != NULL & pre - rightChild = = NULL) pre - rightChild = current; pre - rightThread = 1; /建前驱的后继线索 pre = current; InThread (current - rightChild, pre); /右子树线索化Copyright 2004 by Li Rui465.5 二叉搜索树（二叉搜索树（Binary Search Tree）一、基本概念一、基本概念1、定义或是空、或是具有下列性质的二叉树：每个结点有一个作为搜索依据的关键

37、码（Key）。左子树上所有关键码小于根结点关键码。右子树上所有关键码大于根结点关键码。2、举例中序遍历结果：09，17，23，45，53，65，78，81，87，94显然是有序的，故又称二叉排序树。53658187094523177894Copyright 2004 by Li Rui47一、基本概念一、基本概念 3、BST是基于二叉树的动态搜索结构，其删除和插入结点可能要改变树的结构。 4、BST类定义特点 类定义基于二叉链存贮表示 与一般二叉树类定义十分相似 可以继承一般二叉树类的定义 基本运算Find, Insert 和 Remove 都用递归实现所以在类定义中包括私有和公用两种性质的声

38、明Copyright 2004 by Li Rui48二叉查找树的C+类说明template class BST: public Dictionaryprivate: BinTreeNode * root; Elem RefValue int nodecount; void clearhelp(BinTreeNode*); BinTreeNode* inserthelp(BinTreeNode*,const Elem&); BinTreeNode* deletemin(BinTreeNode*,BinTreeNode*& ) ; BinTreeNode* removehelp(BinTreeN

39、ode*, const Key&, BinTreeNode*&); bool findhelp(BinTreeNode*, int) const; void printhelp(BinTreeNode* ,int) const;Copyright 2004 by Li Rui49public: BST( ) root=NULL; nodecount=0; BST()clearhelp(root); void clear()clearhelp(root); root=NULL; nodecount=0; bool insert(const Elem& e) root=inserthelp(roo

40、t,e); nodecount+; return true; bool remove(const Key&K, Elem& e) BinTreeNode*t=NULL; root=removehelp(root, K, t); e=t-val(); nodecount-; delete t; return true; bool removeAny(Elem& e) if(root=NULL) return false; root=deletemin(root, t); e=t-val(); delete t; nodecount-; return true;Copyright 2004 by

41、Li Rui50 bool find(counst Key& K, Elem& e) const return findhelp(root, K,e); int size()return nodecount; void print()const if(root=NULL) count“The BST is empty.n”; else printHelp(root, 0); ;Copyright 2004 by Li Rui51二、二、BST上的搜索上的搜索1、基本方法从根开始将给定值 x 与结点值进行比较若 x 小，沿着左子树继续搜索若 x 大，沿着右子树继续搜索若与 x 等则成功返回结点地

42、址，若为空则失败2、举例 x = 2353658187094523177894 成功，比较次数为4 x = 88 失败，比较次数为4 比较次数不大于 h + 1Copyright 2004 by Li Rui523、递归算法template bool BST:findHelp (BinNode*subroot, constKey &K,Elem&e) const if (subroot = = NULL) return false; else if (KEComp:lt(K,subroot-val() return findHelp (subroot-left(),K,e); else if

43、(KEComp:gt(K,subroot-val() return findHelp (subroot-rightt(),K,e); else e=subroot-val(); return true; 该算法的递归调用语句都于程序的最尾，称为尾递归 返回时返回到上一层调用处的下条语句去执行 因为是最尾语句，程序结束，不必用栈保存返回地址和局部变量的值 该算法可以不用栈，采用迭代方法改写成非递归程序二、二、BST上的搜索上的搜索Copyright 2004 by Li Rui534、迭代算法template bool BST:findHelp (BinTreeNode*subroot, con

44、stKey &K,Elem&e) if (subroot != NULL) BinTreeNode * temp = subroot; while (temp != NULL) if (KEComp:eq(K, temp-val() e=temp-val(); return true; if (KEComp:gt(K, temp-val() temp = temp -rightChild;else temp = temp - leftChild; return false; 一般对尾递归或单向递归的情形，都可利用迭代方法，不使用栈将递归过程改为非递归过程二、二、BST上的搜索上的搜索Copyr

45、ight 2004 by Li Rui54三、三、BST中的插入中的插入1、方法先搜索BST中有无该结点，只有无才插入插入是作为叶子插入，插入后仍满足BST插入位置应是搜索操作停止（指针ptr为空）的地方2、算法template BinNode* BST: inserthelp(BinNode* subroot, const Elem& val) if (subroot = NULL) / Empty: create node return new BinNodePtr(val,NULL,NULL); if (EEComp:lt(val, subroot-val() subroot-setLe

46、ft(inserthelp(subroot-left(), val); else subroot-setRight( inserthelp(subroot-right(), val); / Return subtree with node inserted return subroot;Copyright 2004 by Li Rui553、建BST 逐次输入关键码序列建一棵BST，是从空开始逐步插入结点 每次从根开始搜索插入位置，然后将新结点作为叶子插入 关键码集合相同但输入序列不同得到的BST也不同若输入次序：81, 65, 78, 94, 87, 88, 23, 45 , 09, 17,

47、 538187172378096594455388三、三、BST中的插入中的插入Copyright 2004 by Li Rui56四、四、BST中的结点删除中的结点删除1、原则删除结点所断开的链要重新接起来删除链接后仍是BST重新链接后树的高度不增加2、方法 被删结点为叶子，只需将双亲结点的相应指针置为空 被删结点无右子树，拿左孩子结点顶替它的位置 被删结点无左子树，拿右孩子结点顶替它的位置 被删结点左右子树都有，在右子树中找中序遍历第一个结点，用它的值填补到被删结点，然后再来删这个结点 结点删除是一个递归的过程Copyright 2004 by Li Rui573、有左右子树的结点删除举例

48、 删除关键码78的结点 右子树中序第一结点是8181复盖7881结点无左子树，用右孩 子88顶替5365819409452317788881四、四、BST中的结点删除中的结点删除8188Copyright 2004 by Li Rui58template BinTreeNode* BST:deletemin(BinTreeNode*subroot,BinTreeNode*&min)if(subroot-left()=NULL) min=subroot; return subroot-right();else subroot-SetLeft(deletemin(subroot-left(),mi

49、n); return subroot; template BinTreeNode* BST: removehelp(BinTreeNode*subroot, constKey&K,BinTreeNode*&t) if(subroot=NULL)return NULL;else if(KEComp:lt(K,subroot-val() subroot-setLeft(removehelp(subroot-left(),K,t); Copyright 2004 by Li Rui59else if(KEComp:gt(K,subroot-val() subroot-setRight(removeh

50、elp(subroot-right(),K,t);else BinTreeNode*temp; t=subroot; if(subroot-left()=NULL) subroot=subroot-right(); else if(subroot-right()=NULL)subroot=subroot-left(); else subroot-setRight(deletemin(subroot-right(),temp); Elem te=subroo-val(); subroot-setVal(temp-val(); temp-setVal(te); t=temp return subr