完全二杈树的层次序遍历 树的遍历通常是从父结点到子结点或子结点到父结点的顺序（前序，后序，中序），如果要实现同一层的所有元素用一般的方法要用堆栈来做，而且实现非常复杂。这里提供一种特别的遍历方法。 我们先按从上到下从左到右的顺序给二杈树的元素编号：第一层的一个元素编1号，第二层左边第一个编2号，第二个编3号，第三层左边第一个编1号，第二个编2号，第三个编3号第四个编4号……大致情况如下： 1 2,3 4,5,6,7 8,9,10,11,12,13,14,15 16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31 …… 从后的情形很清楚了，只要能知道第几个元素在哪很容易就能实现层次序的遍历。我们现在关注的是如何能知道24号在哪很快就能找到它？ 我才用了如下方法，将编号除以2的余数是1还是0来确定它在父结点的左边还是右边，余数是1在右点是0在左边，再将商除以2看余数。如此循环直到结果等于1为止。我用vector将每次的结果保存起来，以make_path函数来实现。 int make_path(int index) {
serial.clear(); int t = index; while ( t != 1) { if( t % 2 == 0) { serial.push_back(t % 2); } else { serial.push_back(t % 2); t--; } t/=2; }
return 0;
} 思路很简单，就是把编号除以二把余数存入serial中 它的定义如下： vector<int> serial; 再跟据生成的路径寻找到指定原素： int go_to(int index) { pcurrent= root; if(index == 1) return 0; make_path(index); for( vector<int>::reverse_iterator iter = serial.rbegin(); iter != serial.rend(); iter ++) { if(*iter) { pcurrent = pcurrent->right; } else { pcurrent = pcurrent->left; } } return 0; } 如果serial中是0就访问他的左结点，否则就是右结点。Pccurrent是访问的当前节点的指针。 下面是插入算法，值得它是个和go_to想似的算法，不同就是如果即将访问的子节点的指针是NULL的话即认为找到，插入。还有就是当树为空时的插入。 int insert(T data) { pcurrent = root; if(root) { make_path(m_count+1); for( vector<int>::reverse_iterator iter = serial.rbegin(); iter != serial.rend(); iter ++) { if(!*iter) { if(pcurrent->left) pcurrent = pcurrent->left; else { pcurrent->left = new Node<T>(data,pcurrent); break; } } else { if(pcurrent->right) pcurrent = pcurrent->right; else { pcurrent->right = new Node<T>(data,pcurrent); break; } } } } else { root = new Node<T>(data); } m_count ++; return m_count ;
} T是用模版定义的一个类型参数，用它来实现算法的数据无关性。 下面遍厉就很简单了： for( int i = 1; i <= tree.m_count ; i++) { cout << tree[i] ; if( i+1 == pow(2,c)) { cout << endl; c++; } else cout << ","; } if是为了考虑换行，因为每一行的第一个是2的c次方所以如果打印的是2的c次方减1的话换行。 下面是完整的原代码: // bintree.cpp : 定义控制台应用程序的入口点。 //
#include "stdafx.h" #include "iostream" #include "vector" #include "conio.h" #include "cmath"
using namespace std; template<class T> class Node { private: Node(); public: T data; Node *left; Node *right; Node *parent; Node(int n):left(NULL),right(NULL),parent(NULL),data(n) { } Node(int n,Node *p):left(NULL),right(NULL),parent(p),data(n) { } operator=(const int &n) { data = n; } Node &operator=(const Node &n) { data = n.data; return *this; } bool operator>(const Node &n) { return data > n.data; } };
template<class T> class Tree { public: Node<T> *root; Node<T> *pcurrent; vector<int> serial; int m_count;
Tree():root(NULL),pcurrent(NULL),m_count(0) { } ~Tree() { remove(); } int go_to(int index) { pcurrent= root; if(index == 1) return 0; make_path(index); for( vector<int>::reverse_iterator iter = serial.rbegin(); iter != serial.rend(); iter ++) { if(*iter) { pcurrent = pcurrent->right; } else { pcurrent = pcurrent->left; } } return 0; } T operator[](int index) { go_to(index); return pcurrent->data;
} int insert(T data) { pcurrent = root; if(root) { make_path(m_count+1); for( vector<int>::reverse_iterator iter = serial.rbegin(); iter != serial.rend(); iter ++) { if(!*iter) { if(pcurrent->left) pcurrent = pcurrent->left; else { pcurrent->left = new Node<T>(data,pcurrent); break; } } else { if(pcurrent->right) pcurrent = pcurrent->right; else { pcurrent->right = new Node<T>(data,pcurrent); break; } } } } else { root = new Node<T>(data); } m_count ++; return m_count ;
} int remove() { rec_del(root); m_count=0; return 0;
} int rec_del( Node<T>* &p) { if(!p) return 1; if(p->left) rec_del(p->left); if(p->right) rec_del(p->right); delete p; p = NULL; return 0;
} int sort( Node<T> *p) { Node<T> t(p->data); if(p->parent) { if(*p > *p->parent) { *p = *p->parent; *p->parent = t; } } return 0; } int sort(int index) { go_to(index); sort(pcurrent); return 0;
} int make_path(int index) {
serial.clear(); int t = index; while ( t != 1) { if( t % 2 == 0) { serial.push_back(t % 2); } else { serial.push_back(t % 2); t--; } t/=2; }
return 0;
}
}; int _tmain(int argc, _TCHAR* argv[]) { int n; int in; Tree<int> tree; cin >> n; tree.remove(); for( int i = 1; i <= n ; i ++) { cin >> in; tree.insert(in); } int layer = 1; for( int i = n; i > 0; i--) { tree.sort(i); } int c= 1; for( int i = 1; i <= tree.m_count ; i++) { cout << tree[i] ; if( i+1 == pow(2,c)) { cout << endl; c++; } else cout << ","; }
getch();
return 0; }
编译平台: windows xp sp2,VC++2003
|
