tree.h

这是一个从音频信号里提取特征参量的程序

    //
    index++;
  }

  // add the nodes adjacent to the root to the list
  //
  this_node = this->getRoot();
  if (this_node == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"get", Error::ARG, __FILE__, __LINE__);
  }
    
  // get the degree of the root node
  //
  long degree = this_node->degree();
  
  if (degree > 0) {
    
    // set the length of the vector to the degree of the node
    //
    root_adj_a.setLength(degree);
    
    // add the position of the left child to the vector
    //
    long pos = 0;      
    TreeNode<TObject>* lnode = this_node->getLeftChild();
    
    if (lnode != (TreeNode<TObject>*)NULL) {

      hashkey.assign(lnode);
      root_adj_a(pos++) = *(khash.get(hashkey));
      
      // add the positions of the right siblings to the vector
      //	
      TreeNode<TObject>* rnode = lnode->getRightSibling();

      while (rnode != (TreeNode<TObject>*)NULL) {

	hashkey.assign(rnode);
	root_adj_a(pos++) = *(khash.get(hashkey));
	rnode = rnode->getRightSibling();
      }
    }     
  }
  
  // add the nodes adjacent to the nodes in the tree to the list
  //
  for (boolean more = this->gotoFirst(); more; more = this->gotoNext()) {

    // get the current tree node
    //
    this_node = this->getCurr();
    if (this_node == (TreeNode<TObject>*)NULL) {
      return Error::handle(name(), L"get", Error::ARG, __FILE__, __LINE__);
    }

    // clear the previous list of indices
    //
    indices.clear();
    
    // get the degree of the current tree node
    //
    long degree = this_node->degree();
    
    if (degree > 0) {

      // set the length of the vector to the degree of the node
      //
      indices.setLength(degree);

      // add the position of the left child to the vector
      //
      long pos = 0;      
      TreeNode<TObject>* lnode = this_node->getLeftChild();
      
      if (lnode != (TreeNode<TObject>*)NULL) {
	
	hashkey.assign(lnode);
	indices(pos++) = *(khash.get(hashkey));

	// add the positions of the right siblings to the vector
	//	
	TreeNode<TObject>* rnode = lnode->getRightSibling();
	
	while (rnode != (TreeNode<TObject>*)NULL) {
	  
	  hashkey.assign(rnode);
	  indices(pos++) = *(khash.get(hashkey));
	  rnode = rnode->getRightSibling();
	}
      }
    }

    // add the vector of indices to the list
    //
    node_adj_a.insert(&indices);          
  }
  
  // restore the original state of the list
  //
  this->gotoMark();

  // exit gracefully
  //
  return true;
}

//------------------------------------------------------------------------
//
// class-specific public methods:
//  tree traversal methods
//
//------------------------------------------------------------------------

// method: postorderTreeTraversal
//
// arguments:
//  SingleLinkedList<TreeNode<TObject> >& arg: (output) traversed nodes in the tree
//  
// return: a boolean value indicating status
//
// post-order traversal visits the left child first, then the right child,
// and finally visits the parent node
//
template <class TObject>
boolean Tree<TObject>::postorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg_a) {

  // declare local variables
  //
  Stack<TreeNode<TObject> > stack(DstrBase::USER);

  // get the root of the tree
  //
  TreeNode<TObject>* current = this->getRoot();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"postorderTreeTraversal", Error::ARG, __FILE__, __LINE__);
  }
  
  // push the root on the stack
  //
  stack.push(current);
  
  // recursively descend down the tree and visit the children in order
  //
  postorderTreeIterator(stack);

  // insert elements of the stack into the list
  //
  while(!stack.isEmpty()) {
    arg_a.insert(stack.pop());
  }
  
  // exit gracefully
  //
  return true;
}

// method: postorderTreeIterator
//
// arguments:
//  Stack<TreeNode<TObject> >& stack: (input) input stack
//  
// return: a boolean value indicating status
//
// post-order traversal iterator method
//
template <class TObject>
boolean Tree<TObject>::postorderTreeIterator(Stack<TreeNode<TObject> >& stack_a) {

  // verify inputs
  //
  if (stack_a.isEmpty()) {
    return Error::handle(name(), L"postorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }

  // get the item on the top of the stack
  //
  TreeNode<TObject>* current = stack_a.peek();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"postorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }

  // get the children associated with the current tree node
  //
  DoubleLinkedList<TreeNode<TObject> > list(DstrBase::USER);
  TreeNode<TObject>* child = current->getLeftChild();
  
  if (child != (TreeNode<TObject>*)NULL) {

    list.insert(child);
    child = child->getRightSibling();
    
    while(child != (TreeNode<TObject>*)NULL) {
      list.insert(child);
      child = child->getRightSibling();
    }
  }

  // recursively descend down the tree and visit the children in order
  //
  for (boolean more = list.gotoLast(); more; more = list.gotoPrev()) {
    stack_a.push(list.getCurr());
    postorderTreeIterator(stack_a);
  }

  // exit gracefully
  //
  return true;
}

// method: preorderTreeTraversal
//
// arguments:
//  SingleLinkedList<TreeNode<TObject> >& arg: (output) traversed nodes in the tree
//  
// return: a boolean value indicating status
//
// pre-order traversal visits parent node first, then the left child,
// and finally visits the right child  
//
template <class TObject>
boolean Tree<TObject>::preorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg_a) {

  // declare local variables
  //
  Stack<TreeNode<TObject> > stack(DstrBase::USER);

  // get the root of the tree
  //
  TreeNode<TObject>* current = this->getRoot();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"postorderTreeTraversal", Error::ARG, __FILE__, __LINE__);
  }
  
  // push the root on the stack
  //
  stack.push(current);
  
  // recursively descend down the tree and visit the children in order
  //
  preorderTreeIterator(stack);

  // insert elements of the stack into the list
  //
  while(!stack.isEmpty()) {
    arg_a.insert(stack.pop());
  }
  arg_a.reverse();
  
  // exit gracefully
  //
  return true;
}

// method: preorderTreeIterator
//
// arguments:
//  Stack<TreeNode<TObject> >& stack: (input) input stack
//  
// return: a boolean value indicating status
//
// post-order traversal iterator method
//
template <class TObject>
boolean Tree<TObject>::preorderTreeIterator(Stack<TreeNode<TObject> >& stack_a) {

  // verify inputs
  //
  if (stack_a.isEmpty()) {
    return Error::handle(name(), L"preorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }

  // get the item at the fornt of the stack
  //
  TreeNode<TObject>* current = stack_a.peek();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"preorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }

  // get the children associated with the current tree node
  //
  DoubleLinkedList<TreeNode<TObject> > list(DstrBase::USER);
  TreeNode<TObject>* child = current->getLeftChild();
  
  if (child != (TreeNode<TObject>*)NULL) {

    list.insert(child);
    child = child->getRightSibling();
    
    while(child != (TreeNode<TObject>*)NULL) {
      list.insert(child);
      child = child->getRightSibling();
    }
  }

  // recursively descend down the tree and visit the children in order
  //
  for (boolean more = list.gotoFirst(); more; more = list.gotoNext()) {
    stack_a.push(list.getCurr());
    preorderTreeIterator(stack_a);
  }
  
  // exit gracefully
  //
  return true;
}

// method: inorderTreeIterator
//
// arguments:
//  TreeNode<TObject>* parent: (input) parent tree node
//  Queue<TreeNode<TObject> >& queue: (input) input queue
//  
// return: a boolean value indicating status
//
// post-order traversal iterator method
//
template <class TObject>
boolean Tree<TObject>::inorderTreeIterator(TreeNode<TObject>* parent_a, Queue<TreeNode<TObject> >& queue_a) {

  // verify the inputs
  //
  if (parent_a == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"inorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }
  
  // visit the left child
  //
  TreeNode<TObject>* child = parent_a->getLeftChild();
  
  if (child != (TreeNode<TObject>*)NULL) {
    inorderTreeIterator(child, queue_a);
  }
  
  // add the parent to the queue
  //
  queue_a.add(parent_a);
  
  // visit the right children
  //
  if (child != (TreeNode<TObject>*)NULL) {
    child = child->getRightSibling();
    while (child != (TreeNode<TObject>*)NULL) {
      inorderTreeIterator(child, queue_a);
      child = child->getRightSibling();      
    }
  }
  
  // exit gracefully
  //
  return true;
}

// method: inorderTreeTraversal
//
// arguments:
//  SingleLinkedList<TreeNode<TObject> >& arg: (output) traversed nodes in the tree
//  
// return: a boolean value indicating status
//
// in-order traversal visits left child first, then the parent node,
// and finally visits the right child
//
template <class TObject>
boolean Tree<TObject>::inorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg_a) {

  // declare local variables
  //
  Queue<TreeNode<TObject> > queue(DstrBase::USER);

  // get the root of the tree
  //
  TreeNode<TObject>* current = this->getRoot();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"postorderTreeTraversal", Error::ARG, __FILE__, __LINE__);
  }
  
  // recursively descend down the tree and visit the children in order
  //
  inorderTreeIterator(current, queue);

  // insert elements of the queue into the list
  //
  while(!queue.isEmpty()) {
    arg_a.insert(queue.remove());
  }

  // exit gracefully
  //
  return true;
}

// method: levelorderTreeTraversal
//
// arguments:
//  SingleLinkedList<TreeNode<TObject> >& arg: (output) traversed nodes in the tree
//  
// return: a boolean value indicating status
//
// level-order traversal visits all nodes at level one (namely the root)
// before visiting all nodes at level two and so on...
//
template <class TObject>
boolean Tree<TObject>::levelorderTreeTraversal(SingleLinkedList<TreeNode<TObject> >& arg_a) {

  // declare local variables
  //
  Queue<TreeNode<TObject> > queue(DstrBase::USER);

  // get the root of the tree
  //
  TreeNode<TObject>* current = this->getRoot();

  if (current == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"postorderTreeTraversal", Error::ARG, __FILE__, __LINE__);
  }
  
  // insert the root node in the queue
  //
  queue.add(current);

  // call the iterator as long as the queue is not empty
  //
  while (!queue.isEmpty()) {
    levelorderTreeIterator(arg_a, queue);
  }
  
  // exit gracefully
  //
  return true;
}

// method: levelorderTreeIterator
//
// arguments:
//  SingleLinkedList<TreeNode<TObject> >& arg: (output) traversed nodes in the tree
//  Queue<TreeNode<TObject> >& queue: (input) input queue
//  
// return: a boolean value indicating status
//
// post-order traversal iterator method
//
template <class TObject>
boolean Tree<TObject>::levelorderTreeIterator(SingleLinkedList<TreeNode<TObject> >& arg_a, Queue<TreeNode<TObject> >& queue_a) {

  // verify inputs
  //
  if (queue_a.isEmpty()) {
    return Error::handle(name(), L"levelorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }

  // get the parent
  //
  TreeNode<TObject>* parent = queue_a.remove();

  if (parent == (TreeNode<TObject>*)NULL) {
    return Error::handle(name(), L"levelorderTreeIterator", Error::ARG, __FILE__, __LINE__);
  }
  
  // visit the children
  //
  TreeNode<TObject>* child = parent->getLeftChild();
  
  if (child != (TreeNode<TObject>*)NULL) {
    queue_a.add(child);
  }

  if (child != (TreeNode<TObject>*)NULL) {
    child = child->getRightSibling();
    while (child != (TreeNode<TObject>*)NULL) {
      queue_a.add(child);
      child = child->getRightSibling();      
    }
  }
  
  // insert the parent in the list
  //
  arg_a.insert(parent);
  
  // exit gracefully
  //
  return true;
}

// end of include file
//
#endif