树的存储结构：
孩子链表：在一颗度为K的树中，若一个结点x已有k个孩子，再插入一个结点作为x的孩子，由于孩子链已满，需要扩充，对于只支持静态数组的程序设计语言，则不能实现此种情况下的插入操作。C++语言提供动态数组，若将孩子的结点域children设计为一个可变长顺序表，则可实现插入操作的扩充功能。
有时占用较多存储空间。若树有n个结点，度为k，总链数为n*k，其中n-1个非空链指向除根以外的n-1个结点。空链与总链之比如下，若k=10，则空链占90%。
孩子兄弟链表：在树的孩子兄弟链表中，孩子域和兄弟域必须区分的，且不可呼唤。这种存储结构实际上将一颗树转换为一颗二叉树存储。按照孩子兄弟表示法，一颗树能够转换成唯一的一颗二叉树；反之，一颗二叉树也能够还原成唯一的一棵树。由于树的根结点没有兄弟，所以对应二叉树根结点的右子树为空。
树的兄弟孩子链表实现：
树的孩子兄弟链表
#include <iostream.h>
#include "DoubleNode.h" //双链表结点类
template <class T>
class Tree // 树的孩子链表实现
{
public:
DoubleNode<T> *root;
Tree ();
~Tree ();
bool IsEmpty; //判断是否为空
void DestroyTree (DoubleNode <T> *p);//撤销以结点P为根的子树
DoubleNode<T> *InsertElem (DoubleNode <T>*p,T x);//插入以x作为结点p的孩子
friend ostream &operator << (ostream & out ,Tree <T>&List);
//先根次序遍历树并以书的横向凹入表示法输出树的所有元素
void preRoot (DoubleNode<T> *p,int n);//先根次序遍历以结点P为根的子树
};
template <class T>
Tree <T>::Tree()
{
this->root = NULL；
}
template <class T>
Tree<T>::~Tree()
{
DestroyTree (this ->root);
}
template <class T>
bool Tree <T>::IsEmpty ()
{
return root->prior == NULL;
}
template <class T>
void Tree <T>::DestroyTree(DoubleNode<T> *p)
{
if(p != NULL)
{
DestroyTree(p->prior);
DestroyTree(p->next);
delete p;
}
}
插入孩子结点
template<class T>
DoubleNode<T> * Tree<T>::InsertElem(DoubleNode<T> *p, T x) // 插入x作为结点p的孩子
{
DoubleNode<T> *q = NULL;
if(p!=NULL)
{
q = new DoubleNode<T>(x); // 初始化新结点q
if(p->prior == NULL)
{
p->prior =q;
}
else
{
p= p->prior;
while(p->next!=NULL)
p=p->next;
p->next =q;
}
}
return q;
}
树的遍历：
树的先根遍历：（1）访问根结点（2）按照从左到右的次序先根遍历根的每一棵子树
树的后根遍历：（1）按照从左到右的次序后根遍历根的每一棵子树（2）访问根结点
template <class T>
ostream& operator<< (ostream& out,Tree<T>&List) //先根遍历树并以树的横向凹入表示法输出树的所有元素
{
List.preRoot(List.root,0);
return out;
}
template <class T>
void Tree<T>::preRoot(DoubleNode<T> *p, int n) //先根遍历以结点P为根的子树，参数i指定结点的层次
{
if(p!=NULL)
{
for(int j=0;j<n;j++)
cout<<" \t";
cout<<p->data<<endl;
preRoot(p->prior,n+1);
preRoot(p->next,n);
}
}
打印云南城市树
#define _CRT_SECURE_NO_WARNINGS
#include "Tree.h"
void Creat(Tree<char*> &tree) //构造一棵树
{
tree.root =new DoubleNode<char *>("云南");
DoubleNode<char *> *km =tree.InsertElem(tree.root,"昆明市");
tree.InsertElem (km,"安宁市");
DoubleNode<char *> *qj = tree.InsertElem(tree.root,"曲靖市");
tree.InsertElem (qj,"宜威市");
tree.InsertElem(tree.root,"大理市");
tree.InsertElem(tree.root,"丽江市");
}
int main()
{
Tree<char*>tree;
Creat(tree);
cout<<tree;
return 0;
}