完全二杈树的层次序遍历
树的遍历通常是从父结点到子结点或子结点到父结点的顺序（前序，后序，中序），如果要实现同一层的所有元素用一般的方法要用堆栈来做，而且实现非常复杂。这里提供一种特别的遍历方法。
我们先按从上到下从左到右的顺序给二杈树的元素编号：第一层的一个元素编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
