星海's Blog

老头初学编程
算法导论习题 12-2
算法导论 红黑树的实现代码(C++)

二叉树的C++模板,摘自Mark Alen Weiss,中序用栈遍历摘自microgoogle

星海 posted @ 2012年11月16日 16:10 in 数据结构与算法分析 , 2652 阅读

Mark Alen Weiss:
http://users.cis.fiu.edu/~weiss/#dsaac++3
《数据结构与算法分析 C++语言描述》

提供了较好的C++样式和代码风格,用到了模板,重载和指针引用,值得学习。。

但在效率上稍差一点,另外没有parent节点。

 

MicroGoogle:

http://www.cnblogs.com/shuaiwhu/archive/2011/04/20/2065055.html

非递归遍历用栈版本和不用栈版本。

我这里只参照micogoogle的实现了栈版本中序递归(基本全是照抄),非递归版本暂不考虑。

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

// #include "dsexceptions.h"
#include <iostream>    // For NULL
#include <vector>
using namespace std;

// BinarySearchTree class
//
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as warranted

template <typename Comparable>
class BinarySearchTree
{
public:
  BinarySearchTree( ) : root( NULL ) {
  }

  BinarySearchTree( const BinarySearchTree & rhs ) : root( NULL ) {
    *this = rhs;
  }

  /**
   * Destructor for the tree
   */
  ~BinarySearchTree( ) {
    makeEmpty( );
  }

  /**
   * Find the smallest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMin( ) const {
    if ( isEmpty( ) ) {
      //      throw UnderflowException( );
      ;
    }
    return findMin( root )->element;
  }

  /**
   * Find the largest item in the tree.
   * Throw UnderflowException if empty.
   */
  const Comparable & findMax( ) const {
    if ( isEmpty( ) ) {
      //      throw UnderflowException( );
      ;
    }
    return findMax( root )->element;
  }

  /**
   * Returns true if x is found in the tree.
   */
  bool contains( const Comparable & x ) const {
    return contains( x, root );
  }

  /**
   * Test if the tree is logically empty.
   * Return true if empty, false otherwise.
   */
  bool isEmpty( ) const {
    return root == NULL;
  }

  /**
   * Print the tree contents in sorted order.
   */
  void printTree( ostream & out = cout ) const {
    if ( isEmpty( ) ) {
      out << "Empty tree" << endl;
    } else {
      printTree( root, out );
    }
  }

  /**
   * Make the tree logically empty.
   */
  void makeEmpty( ) {
    makeEmpty( root );
  }

  /**
   * Insert x into the tree; duplicates are ignored.
   */
  void insert( const Comparable & x ) {
    insert( x, root );
  }

  /**
   * Remove x from the tree. Nothing is done if x is not found.
   */
  void remove( const Comparable & x ) {
    remove( x, root );
  }

  /**
   * Deep copy.
   */
  const BinarySearchTree & operator=( const BinarySearchTree & rhs ) {
    if ( this != &rhs ) {
      makeEmpty( );
      root = clone( rhs.root );
    }
    return *this;
  }

private:
  struct BinaryNode {
    Comparable element;
    BinaryNode *left;
    BinaryNode *right;

    BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt )
      : element( theElement ), left( lt ), right( rt ) { }
  };

  BinaryNode *root;


  /**
   * Internal method to insert into a subtree.
   * x is the item to insert.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void insert( const Comparable & x, BinaryNode * & t ) {
    if ( t == NULL ) {
      t = new BinaryNode( x, NULL, NULL );
    } else if ( x < t->element ) {
      insert( x, t->left );
    } else if ( t->element < x ) {
      insert( x, t->right );
    } else {
//      ;  // Duplicate; do nothing
    }
  }

  /**
   * Internal method to remove from a subtree.
   * x is the item to remove.
   * t is the node that roots the subtree.
   * Set the new root of the subtree.
   */
  void remove( const Comparable & x, BinaryNode * & t ) {
    if ( t == NULL ) {
      return;  // Item not found; do nothing
    }
    if ( x < t->element ) {
      remove( x, t->left );
    } else if ( t->element < x ) {
      remove( x, t->right );
    } else if ( t->left != NULL && t->right != NULL ) { // Two children
      t->element = findMin( t->right )->element;
      remove( t->element, t->right );
    } else {
      BinaryNode *oldNode = t;
      t = ( t->left != NULL ) ? t->left : t->right;
      delete oldNode;
    }
  }

  /**
   * Internal method to find the smallest item in a subtree t.
   * Return node containing the smallest item.
   */
  BinaryNode * findMin( BinaryNode *t ) const {
    if ( t == NULL ) {
      return NULL;
    }
    if ( t->left == NULL ) {
      return t;
    }
    return findMin( t->left );
  }

  /**
   * Internal method to find the largest item in a subtree t.
   * Return node containing the largest item.
   */
  BinaryNode * findMax( BinaryNode *t ) const {

    if ( t != NULL )
      while ( t->right != NULL ) {
        t = t->right;
      }
    return t;
  }


  /**
   * Internal method to test if an item is in a subtree.
   * x is item to search for.
   * t is the node that roots the subtree.
   */
  bool contains( const Comparable & x, BinaryNode *t ) const {
    if ( t == NULL ) {
      return false;
    } else if ( x < t->element ) {
      return contains( x, t->left );
    } else if ( t->element < x ) {
      return contains( x, t->right );
    } else {
      return true;  // Match
    }
  }
  /****** NONRECURSIVE VERSION*************************
    bool contains( const Comparable & x, BinaryNode *t ) const
    {
    while( t != NULL )
    if( x < t->element )
    t = t->left;
    else if( t->element < x )
    t = t->right;
    else
    return true;    // Match

    return false;   // No match
    }
   *****************************************************/

  /**
   * Internal method to make subtree empty.
   */
  void makeEmpty( BinaryNode * & t ) {
    if ( t != NULL ) {
      makeEmpty( t->left );
      makeEmpty( t->right );
      delete t;
    }
    t = NULL;
  }

  //
  //  void printTree( BinaryNode *t, ostream & out ) const {
  //    if ( t != NULL ) {
  //      printTree( t->left, out );
  //      out << t->element << endl;
  //      printTree( t->right, out );
  //    }
  //  }

  void printTree( BinaryNode *t, ostream &out) const {
//  将vector当作栈来实现,push_back,pop_back,back
    vector<BinaryNode *> stackList;
    while (t != NULL || !stackList.empty()) {
      while (t != NULL) {
        stackList.push_back(t);
        t = t->left;
      }
      t = stackList.back();
      stackList.pop_back();
      out << t->element << "\t";
      t = t->right;
    }
  }

    /**
     * Internal method to clone subtree.
     */
    BinaryNode * clone( BinaryNode *t ) const {
      if ( t == NUL
          return NULL;
          } else {
          return new BinaryNode( t->element, clone( t->left ), clone( t->right ) );
          }
          }
          };

#endif
Avatar_small
전설 서구 说:
2021年3月04日 21:44

I am very happy to discover your post as it will become on top in my collection of favorite blogs to visit. free movie download sites

Avatar_small
Smithseo 说:
2021年3月20日 04:59

This is very educational content and written well for a change. It's nice to see that some people still understand how to write a quality post! outlook login

Avatar_small
biaakhan 说:
2021年3月30日 20:07

Superbly written article, if only all bloggers offered the same content as you, the internet would be a far better place.. Health

Avatar_small
John 111 说:
2021年4月06日 01:36

This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good work 토토갤러리

Avatar_small
John 111 说:
2021年4月11日 14:00

You have done a amazing job with you website 메이저사이트

Avatar_small
Top SEO 说:
2021年4月24日 13:15

Hello I am so delighted I located your blog, I really located you by mistake, while I was watching on google for something else, Anyways I am here now and could just like to say thank for a tremendous post and a all round entertaining website. Please do keep up the great work. kuliah karyawan

Avatar_small
Top SEO 说:
2021年4月25日 21:01 Two full thumbs up for this magneficent article of yours. I've really enjoyed reading this article today and I think this might be one of the best article that I've read yet. Please, keep this work going on in the same quality. shopping
Avatar_small
Top SEO 说:
2021年4月25日 21:06

I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you! 巨乳肥満ラブドール

Avatar_small
John 111 说:
2021年5月02日 13:19

Wow, What a Excellent post. I really found this to much informatics. It is what i was searching for.I would like to suggest you that please keep sharing such type of info.Thanks Non Woven Fabric Factory

Avatar_small
John 111 说:
2021年5月21日 19:15

Thank you very much for this useful article. I like it. 먹튀검증

Avatar_small
John 111 说:
2021年5月31日 23:33

Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. 꽁머니사이트

Avatar_small
먹튀검증 说:
2021年5月31日 23:52

It is truly a well-researched content and excellent wording. I got so engaged in this material that I couldn’t wait reading. I am impressed with your work and skill. Thanks.

Avatar_small
마추자먹튀 说:
2021年6月10日 15:06

Pretty nice post. I just stumbled upon your weblog and wanted to say that I have really enjoyed browsing your blog posts. After all I’ll be subscribing to your feed and I hope you write again soon!

Avatar_small
Top SEO 说:
2021年6月18日 08:34

check this link. its full of sex education. and also useful in your life. and help in your sex life better xxx paraguay 2021

Avatar_small
John 111 说:
2021年6月30日 23:27

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. 안전놀이터

Avatar_small
Top SEO 说:
2021年10月16日 15:46

I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work. fifa world cup 2022 tickets

Avatar_small
Top SEO 说:
2021年10月26日 15:55

Great survey, I'm sure you're getting a great response. SBOBET88

Avatar_small
Top SEO 说:
2021年11月02日 14:14

Very efficiently written information. It will be beneficial to anybody who utilizes it, including me. Keep up the good work. For sure i will check out more posts. This site seems to get a good amount of visitors. Buy real canadian drivers licence online

Avatar_small
Top SEO 说:
2021年11月03日 15:03

We have sell some products of different custom boxes.it is very useful and very low price please visits this site thanks and please share this post with your friends. HR System in Cambodia

Avatar_small
jackseo 说:
2021年12月04日 23:09

Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. 北美代写

Avatar_small
John 说:
2021年12月09日 15:57

I wanted to thank you for this excellent read!! I definitely loved every little bit of it. I have you bookmarked your site to check out the new stuff you post. 모모벳

Avatar_small
Top SEO 说:
2022年3月04日 14:44

I found Hubwit as a transparent s ite, a social hub which is a conglomerate of Buyers and Sellers who are ready to offer online digital consultancy at decent cost. we will all laugh at gilded butterflies


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter