第6章树与森林 while(p-> leftThread=1)p=p-> leftchild;∥p即为q的后继 (2)搜索指定结点的在前序下的后继 g->leftThread ==0? 的后继为q-> lefichild q的后继为q-> righIchild while(p->rightThread==l&& o->righ/Child I=NULL)P=p->righrChild; f(p-> righIChild==NUL)q无后继: (3)搜索指定结点的在后序下的后继。 (p=parent(q ))=NULL? q无后继 >rightChild q的后继为p q的后继为p的右子树中后序下的第一个结点 可用一段遍历程序来实现寻找p的右子树中后序下的第一个结点:即该子树第一个找到的叶结点。 找到后立即返回它的地址 6-10已知一棵完全二叉树存放于一个一维数组Tn中,Tm中存放的是各结点的值。试设计一个算法, 从T0开始顺序读出各结点的值,建立该二叉树的二叉链表表示。 【解答】 template <class Type> ∥建立二叉树 istream& operator >> istream& in, Binary Tree<Type>& t) cout <<"Please enter the number of node Type*A= new Type[n+1; for( int i=0; i <n; i++)in >>A[: t. ConstructTree( T, n, 0, ptr ∥以数组建立一棵二叉树 return in: void Binary Tree<Type>: ConstructTree( Type TI int n, int 1, BinTreeNode<Type>*& ptr )i ∥有函数:将用Tn]顺序存储的完全二叉树,以i为根的子树转换成为用二叉链表表示的 ∥以p为根的完全二叉树。利用引用型参数pt将形参的值带回实参。 >=n)ptr =NULL; ptr=new BinTreeNode<Type>(To); ∥建立根结点 ConstructTree(T, n, 2*i+1, ptr->leftChild i ConstructTree(T, n, 2*i+2, ptr->rightChild )第 6 章 树与森林 50 while ( p->leftThread == 1 ) p = p->leftChild; // p 即为 q 的后继 (2) 搜索指定结点的在前序下的后继。 (3) 搜索指定结点的在后序下的后继。 可用一段遍历程序来实现寻找 p 的右子树中后序下的第一个结点：即该子树第一个找到的叶结点。 找到后立即返回它的地址。 6-10 已知一棵完全二叉树存放于一个一维数组 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 ); } } q->leftThread == 0 ? = q的后继为 q->leftChild ≠ q->rightThread == 0 ? = q 的后继为 q->rightChild ≠ p = q; while ( p->rightThread == 1 && p->rightChild != NULL ) p = p->rightChild; if ( p->rightChild ==NULL ) q 无后继; else 的后继为 p->rightChild ( p = parent (q ) ) == NULL ? = q 的后继为 p ≠ p->rightThread == 1 || p->rightChild == q ?= ≠ q 的后继为 p 的右子树中后序下的第一个结点 q 无后继