当前位置:C++技术网 > 资讯 > 数据结构笔记分享:14 二叉树的遍历(利用函数指针)

数据结构笔记分享:14 二叉树的遍历(利用函数指针)

更新时间:2015-11-25 20:56:43浏览次数:1+次

算法描述:


设计了一个面向用户的公有成员函数和一个具体实现遍历操作的递归私有成员函数,两者共同完成遍历运算的功能。

公有成员函数:非递归函数,作为与用户的接口。它调用私有的递归函数。

私有成员函数:递归函数,具体实现遍历操作。被公有成员函数调用。

两个函数的共同参数是一个Visit函数指针,用户通过指定访问的元素的函数Visit,遍历每个节点

指向函数的指针一般定义格式:

函数返回类型 (*函数指针名)(参数1,参数2…)

// 访问元素函数
template<class T>
void Visit(T& x) {
    cout << x << "\t";
}
//先序遍历
template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)(T& x)) { 
     PreOrder(Visit,root);
}
template<class T>
void BinaryTree<T>::PreOrder(void(*Visit)(T& x), BTNode<T>* t) { 
    if(t) {
         Visit(t->element);
         PreOrder(Visit, t->lChild);
         PreOrder(Visit, t->rChild);
  }
}   



//中序遍历
template<class T>
void BinaryTree<T>::InOrder(void(*Visit)(T& x)) {
      InOrder(Visit,root);
}

template<class T>
void BinaryTree<T>::InOrder(void(*Visit)(T& x), BTNode<T>* t) {
     if(t) {
           InOrder(Visit, t->lChild);
           Visit(t->element);
           InOrder(Visit, t->rChild);
     }
}
//后序遍历
template<class T>
void BinaryTree<T>::PostOrder(void(*Visit)(T& x)) {
      PostOrder(Visit,root);
}

template<class T>
void BinaryTree<T>::PostOrder(void(*Visit)(T& x), BTNode<T>* t) {
      if(t) {
             PostOrder(Visit, t->lChild);
             PostOrder(Visit, t->rChild);
             Visit(t->element);
      }
}