词条 | 二叉数的遍历 |
释义 | 二叉树的遍历 · Preorder前序遍历——访问结点的操作发生在遍历其左右子树之前 · Inorder中序遍历——访问结点的操作发生在遍历其左右子树之间 · Postorder后序遍历——访问结点的操作发生在遍历其左右子树之后 · Level order层次遍历——按每一层的节点,从左到右逐次访问 Preorder traversal(中->左->右) template<class T> void PreOrder(BinaryNode<T>* t) // preorder traversal of *t. { if(t) { visit(t); PreOrder(tàLeft); PreOrder(tàRight); } } Inorder traversal(左->中->右) //递归算法 template<class T> void InOrder(BinaryNode<T>* t) { if(t) { InOrder(tàLeft); visit(t); InOrder(tàRight); } } //非递归算法 void Inorder(BinaryNode <T> * t) { Stack<BinaryNode<T>*> s(10); BinaryNode<T> * p = t; for ( ; ; ) { 1) while(p!=NULL) { s.push(p); p = p->Left; } 2) if (!s.IsEmpty( )) { p = s.pop( ); cout << p->element; p = p->Right; } else return; } } Postorder traversal(左->右->中) //递归算法 template<class T> void PostOrder(BinaryNode<T>* t) { if(t) { PostOrder(tàLeft); PostOrder(tàRight); visit(t); } } //非递归算法 struct StkNode { BinaryNode <T> * ptr; int tag; } void Postorder(BinaryNode <T> * t) { Stack <StkNode<T>>s(10); StkNode<T> Cnode; BinaryNode<T> * p = t; for( ; ; ) { 1)while (p!=NULL) { Cnode.ptr = p; Cnode.tag = 0; s.push(Cnode); p = p->Left; } 2)Cnode = s.pop( ); p = Cnode.ptr; 3)while ( Cnode.tag = = 1) //从右子树回来 { cout << p->element; if ( !s.IsEmpty( )) { Cnode = s.pop( ); p = Cnode.ptr; } else return; } 4)Cnode.tag = 1; s.push(Cnode); p = p->Right; //从左子树回来 }//for } Level order: it is a non-recursive function and a queue is used. template<class T> void LevelOrder(BinaryNode<T>* t) { LinkedQueue<BinaryNode<T>*> Q; while(t) { visit(t); //visit t if(tàLeft) Q.Add(tàLeft); if(tàRight) Q.Add(tàRight); try { Q.Delete(t); }catch(OutOfBounds){return;} } } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。