第6章树与森林 Type "A= new Type[n+1]; for int 1=0; i<n;i++)in >>A0; t. ConstructTree( T, n, O,ptr ∥以数组建立一棵二叉树 []A return in: template <class Type> void Binary Tree<Type>: ConstructTree( Type TI int n, int 1, BinTreeNode<Type>*& ptr )i ∥有函数:将用Tn]顺序存储的完全二叉树,以i为根的子树转换成为用二叉链表表示的 ∥以pt为根的完全二叉树。利用引用型参数pt将形参的值带回实参。 if (i >=n) ptr =NULL; tr= new BinTreeNode<Type>(To); ∥建立根结点 ConstructTree(T, n, 2 i+l, ptr->leftChild ) ConstructTree(T, n, 2*i+2, ptr->rightChild ) 6-13试编写一个算法,把一个新结点1作为结点s的左子女插入到一棵中序线索化二叉树中,s原来的 左子女变成l的左子女。 【解答】 template<class Type> void thre ead Tree<Type>: leftlnsert(ThreadNode<Type>*s, ThreadNode<Type>"I)i (sI= NULL &&Il=NULL )i l-> leftchild=s-> leftchild;l-> leftthread=s-> leftThread;∥预先链接 1->rightChild =s; 1->rightThread =1 新插入结点的后继为s s->leftchild =I: s->leftThread =03 ∥成为*s的左子女 if (l->leftThread ==0) ∥1的左子女存在 ThreadNode<Type.p=l->leftChild while( p->rightThread ==0) ∥找1的左子树中序下最后一个结点 p=p-right Child: p->rightChild =I; ∥该结点的后继为 6-14写出向堆中加入数据4,2,5,8,3,6,10,14时,每加入一个数据后堆的变化。 【解答】以最小堆为例:第 6 章 树与森林 74 Type *A = new Type[n+1]; for ( int i = 0; i < n; i++ ) in >> A[i]; t. ConstructTree( T, n, 0, ptr ); //以数组建立一棵二叉树 delete [ ] A; return in; } template <class Type> void BinaryTree<Type> :: ConstructTree ( Type T[ ], int n, int i, BinTreeNode<Type> *& ptr ) { //私有函数 : 将用 T[n]顺序存储的完全二叉树, 以 i 为根的子树转换成为用二叉链表表示的 //以 ptr 为根的完全二叉树。利用引用型参数 ptr 将形参的值带回实参。 if ( i >= n ) ptr = NULL; else { ptr = new BinTreeNode<Type> ( T[i] ); //建立根结点 ConstructTree ( T, n, 2*i+1, ptr->leftChild ); ConstructTree ( T, n, 2*i+2, ptr->rightChild ); } } 6-13 试编写一个算法，把一个新结点 l 作为结点 s 的左子女插入到一棵中序线索化二叉树中，s 原来的 左子女变成 l 的左子女。 【解答】 template<class Type> void ThreadTree<Type> :: leftInsert ( ThreadNode<Type> *s, ThreadNode<Type> * l ) { if ( s != NULL && l != NULL ) { l->leftChild = s->leftChild; l->leftThread = s->leftThread; //预先链接 l->rightChild = s; l->rightThread = 1; //新插入结点*l 的后继为*s s->leftChild = l; s->leftThread = 0; //*l 成为*s 的左子女 if ( l->leftThread == 0 ) { //*l 的左子女存在 ThreadNode<Type> * p = l->leftChild; while ( p->rightThread == 0 ) //找*l 的左子树中序下最后一个结点 p = p->rightChild; p->rightChild = l; //该结点的后继为*l } } } 6-14 写出向堆中加入数据 4, 2, 5, 8, 3, 6, 10, 14 时，每加入一个数据后堆的变化。 【解答】以最小堆为例： 4 4 2 4 4 4 2 2 5 5 5 2 2 8 8 4 3