?? tree.h
字號:
/*
$Id: tree_msvc.hh,v 1.3 2002/05/28 11:53:25 t16 Exp $
STL-like templated tree class.
Copyright (C) 2001 Kasper Peeters <k.peeters@damtp.cam.ac.uk>
Microsoft VC version by Jason Avinger, see
http://www.damtp.cam.ac.uk/user/kp229/tree/
for the original.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
// it++ 沒有定義。只定義了 ++it
#ifndef tree_hh_
#define tree_hh_
#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>
#ifdef _MSC_VER // MSVC does not have HP style construct/destroy
//p指向的T1型變量的值賦為val
template <class T1, class T2>
inline void constructor(T1* p, T2& val)
{
new ((void *) p) T1(val);
/*
* new 作用
* if(p) *p = T1(val);
*/
}
template <class T1>
inline void constructor(T1* p)
{
new ((void *) p) T1;
}
template <class T1>
inline void destructor(T1* p)
{
p->~T1();
}
#else
#define constructor std::construct
#define destructor std::destroy
#endif
//節點
template<class T>
struct tree_node_ {
tree_node_<T> *parent;//父節點
tree_node_<T> *first_child, *last_child;//子節點
tree_node_<T> *prev_sibling, *next_sibling;//兄弟節點
T data;//數據
};
template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree
{
protected:
typedef tree_node_<T> tree_node;
public:
typedef T value_type;
class iterator;
class sibling_iterator;//兩種iterator
//******************* 構造和析構函數 ***********************
//structor & destructor
tree(){
head_initialise_();
}
~tree(){
clear();
alloc_.deallocate(head,1);
}
tree(const tree<T, tree_node_allocator>& other){
head_initialise_();
copy_(other);
}
//
void operator=(const tree<T, tree_node_allocator>& other){
copy_(other);
}
//*********************************************************
//--------------------------class iterator------------------------
class iterator
{
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
//*********** 構造函數和析構函數 *************************************
//不指向任何節點
iterator(): node(0), skip_current_children_(false){
}
//node指向tn
iterator(tree_node *tn): node(tn), skip_current_children_(false){
}
//指向other.node
//如果node==0，則...
iterator(const sibling_iterator& other):
node(other.node), skip_current_children_(false){
if(node==0) {//這種情況的發生是由于
node=other.range_last();
skip_children();
increment_();
}
}
//********** 位移操作 ************************************************
//只要存在樹，就不會出錯，也就是說 this->node != 0
//因此不要企圖使用 it!=0 來作為遍歷結束條件，一定要用 it!=end()
iterator& operator++(void){
if(!increment_()) {//如果失敗，node一定會是0的，不用再賦值了
node=0;
}
return *this;
}
//向前
iterator& operator--(void){
if(!decrement_()) {
node=0;
}
return *this;
}
iterator& operator+=(unsigned int num){
while(num>0) {
++(*this);
--num;
}
return (*this);
}
iterator& operator-=(unsigned int num){
while(num>0) {
--(*this);
--num;
}
return (*this);
}
iterator operator+(int num) const{
iterator ret(*this);
while(num>0) {
++ret;
--num;
}
return ret;
}
//********************* 獲取數據 ***********************************
//獲取的是引用
T& operator*(void) const{
return node->data;
}
//獲取的是指針
T* operator->(void) const{
return &(node->data);
}
//********************* 兩個iterator關系 ***********************
// 兩個iterator是否指向相同的節點?
bool operator==(const iterator& other) const{
if(other.node==node) return true;
else return false;
}
// 兩個iterator是否指向不同的節點？
bool operator!=(const iterator& other) const{
if(other.node!=node) return true;
else return false;
}
//返回子節點。如果不存在子節點，則ret.node == 0
sibling_iterator begin() const{
sibling_iterator ret(node->first_child);
ret.parent_=node;
return ret;
}
//構造一個不指向節點的iterator
sibling_iterator end() const{
sibling_iterator ret(0);
ret.parent_=node;
return ret;
}
//******************** 其他 ********************************
// do not iterate over children of this node
void skip_children(){
skip_current_children_=true;
}
//iterator是否指向樹節點？
bool is_valid() const{
if(node==0) return false;
else return true;
}
//直接子節點的個數
unsigned int number_of_children() const{
tree_node *pos=node->first_child;
if(pos==0) return 0;
unsigned int ret=1;
while(pos!=node->last_child) {
++ret;
pos=pos->next_sibling;
}
return ret;
}
//********************** 封裝的數據 ********************
tree_node *node;//指向樹節點
private:
//如果有下一個節點，則返回true，并且node指向它
//何時才返回false?只有當head==0
//skip_current_children_作用：
// 為false時，如果有子節點，則指向子節點;如果有兄弟節點，則為兄弟節點;否則回溯
// 為true時，肯定不訪問子節點
// 有一個問題：
// 設skip_current_children == false
// head<---->root1<---->root2<---->head
// /\
// / \
// a b
// node當前值指向b，則執行后node指向root2
// 再執行一次將指向head!!!!
//
bool increment_(){//這個函數執行后,skip_current_children==false
assert(node!=0);
//如果不跳過子節點并且存在子節點，則指向第一個子節點
if(!skip_current_children_ && node->first_child) {
node=node->first_child;
return true;
}
else{
skip_current_children_=false;
while(!node->next_sibling){//沒有兄弟節點，回溯
node=node->parent;
if(node==0)
return false;
}
node=node->next_sibling;//由于是pre-order，優先訪問本節點，再訪問子節點
return true;
}
}
bool decrement_(){
assert(node!=0);
//若是樹根
if(node->parent==0) {
if(node->last_child==0)
node=node->prev_sibling;
while(node->last_child)
node=node->last_child;
if(!node) return false;
}
//不是樹根
else {
//如果存在前趨
if(node->prev_sibling) {
if(node->prev_sibling->last_child) {
node=node->prev_sibling->last_child;
}
else {
node=node->prev_sibling;
}
}
//不存在前趨
else {
node=node->parent;
if(node==0)
return false;
}
}
return true;
}
bool skip_current_children_;
};
//---------------------end of class iterator------------------
//--------------------sibling_iterator------------------------
/******************
*對于 sibling_iterator，node==0是正常的
*
******************/
class sibling_iterator
{
friend class tree<T, tree_node_allocator>;
// friend class tree<T, tree_node_allocator>::iterator;
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
//************** 構造和析構函數 ******************************
//不指向任何節點
sibling_iterator(): node(0), parent_(0){
}
//指向 tn，并且設置parent_指向tn的父節點
sibling_iterator(tree_node *tn): node(tn){
set_parent_();
}
//將other的值拷貝過來
sibling_iterator(const sibling_iterator& other):
node(other.node), parent_(other.parent_){
}
sibling_iterator(const iterator& other): node(other.node){
set_parent_();
}
//************** 位移操作 ************************************
//如果已到最后一個兄弟節點的后面，這移不了
sibling_iterator& operator++(void){
if(node)
node=node->next_sibling;
return *this;
}
//如果已到最前一個兄弟節點的前面，移不了
sibling_iterator& operator--(void){
if(node)
node=node->prev_sibling;
/* comment by zychen
else{
assert(parent_);//也就是說head的兄弟節點...
node=parent_->last_child;
}
*/
return *this;
}
sibling_iterator& operator+=(unsigned int num){
while(num>0) {
++(*this);
--num;
}
return (*this);
}
sibling_iterator& operator-=(unsigned int num){
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -