可用一段遍历程序来实现寻找p的右子树中后序下的第一个结点:即该子树第一个找到的叶结点。 找到后立即返回它的地址 6-12已知一棵完全二叉树存放于一个一维数组Tl]中,T中存放的是各结点的值。试设计一个算法 从T0开始顺序读出各结点的值,建立该二叉树的二叉链表表示 【解答】 建立二叉树 istream& operator >> istream& in, BinaryTree<Type>&1)i int n: cout <<"Please enter the number of node: " in >>n Type A= new Type nm+1]: for int i=0; i<n; i++)in >>A0: ee( T, n, 0, ptr )i ∥以数组建立一棵二叉树 delete [A return in: template <class Type> void BinaryTree<Type>: ConstructTree(Type T[I, int n, int i, Bin TreeNode<type>*& ptr)t ∥有函数:将用Tn]顺序存储的完全二叉树,以i为根的子树转换成为用二叉链表表示的 以p为根的完全二叉树。利用引用型参数pr将形参的值带回实参 ∥建立根结点 ConstructTree(T, n, 2 i+1, ptr->lefiChild); ConstructUre(T,n,2·汁2,p-> righichild); 6-14写出向堆中加入数据4,2,5,8,3,6,10,14时,每加入一个数据后堆的变化。 【解答】以最小堆为例: 6-16请画出右图所示的树所对应的二叉树。可用一段遍历程序来实现寻找 p 的右子树中后序下的第一个结点：即该子树第一个找到的叶结点。 找到后立即返回它的地址。 6-12 已知一棵完全二叉树存放于一个一维数组 T[n]中，T[n]中存放的是各结点的值。试设计一个算法， 从 T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 【解答】 template <class Type> //建立二叉树 istream& operator >> ( istream& in, BinaryTree<Type>& t ) { int n; cout << "Please enter the number of node : "; in >> n; 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-14 写出向堆中加入数据 4, 2, 5, 8, 3, 6, 10, 14 时，每加入一个数据后堆的变化。 【解答】以最小堆为例： 6-16 请画出右图所示的树所对应的二叉树。 4 4 2 4 4 4 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 5 2 8 3 4 6 5 2 8 3 4 6 10 5 2 8 3 4 6 10 14