二叉树的静态实现可以满足完全不使用指针，而简单使用数组来完成二叉树的所有操作。

在定义二叉树时，采用的是二叉链表的结构，如下所示：

struct node{
	typename data;//数据域
	node *lchild;//指向左子树的根结点的指针
	node *rchild;//指向右子树的根结点的指针 
};

在这个定义中，为了能够实时控制新生成的结点的个数，结构体node中的左右指针域都采用了指针。静态的二叉链表不需要使用指针即可实现。

 

静态的二叉链表的定义：

 

结点的左右指针域均采用int型来代替，用来表示左右子树的根节点在数组中的下标。为此需要建立一个大小为结点上限个数的node型数组，所有动态生成的结点都直接使用数组中的结点，所有对指针的操作均改为对数组下标的访问。于是，结点node的定义更改如下：

struct node{
	typedefname data;//数据域
	int lchild;//指向左子树的指针域
	int rchild;//指向右子树的指针域 
}Node[maxn];//结点数组，maxn为结点上限个数 

在这样的定义下，结点的动态生成就可以转变为如下的静态的指定：

int newNode(int v){
	//分配一个Node型数组中的结点给新结点，index为其下标
	Node[index].data=v;
	Node[index].lchild=-1;//以-1或maxn表示空，因为数组范围是0-maxn-1 
	Node[index].rchild=-1;
	return index++; 
}

 下面给出二叉树的查找、插入、建立的代码，与使用指针的代码有所区别。

//查找，root为根节点在数组中的下标
void search(int root,int x,int newdata){
	if(root==-1){
		//用-1来代替null
		return;//递归的边界 
	}
	if(Node[root]==x){
		//找到数据域为x的结点，更改新的数据域
		Node[root]=newdata; 
	}
	search(Node[root].lchild,x,newdata);//在左子树中搜索x（递归式）
	search(Node[root].rchild,x,newdata);
} 
//插入，root为根节点在数组中的下标，记得加引用
void insert(int &root,int x){
	if(root==-1){
		//查找失败，边界
		root=newNode(x);//给root以新的结点
		return; 
	}
	if(由二叉树的性质x应该插入左子树){
		insert(Node[root].lchild,x);
	}else{
		insert(Node[root].rchild,x);
	}
} 

//二叉树的建立，函数返回根节点root的下标
int Create(int data[],int n){
	int root=-1;//建立根节点
	for(int i=0;i<n;i++){
		insert(root,data[i]);
	} 
	return root;//返回二叉树的根节点在数组中的下标 
} 

关于二叉树的先序遍历、中序遍历、后序遍历、层次遍历也应该做相应的转换。

//先序遍历
void preorder(int root){
	if(root==-1){
		return;//到达空树，递归边界 
	}
	//访问根节点root，例如将其数据输出
	printf("%d\n",Node[root].data);
	//访问左子树
	preorder(Node[root].lchild);
	//访问右子树
	preorder(Node[root].rchild); 
} 

//中序遍历
void inorder(int root){
	if(root==-1){
		return;//到达空树，递归边界 
	}
	//访问左子树
	preorder(Node[root].lchild);
	//访问根节点root，例如将其数据输出
	printf("%d\n",Node[root].data);
	//访问右子树
	preorder(Node[root].rchild); 
} 

//后序遍历
void postorder(int root){
	if(root==-1){
		return;//到达空树，递归边界 
	}
	//访问左子树
	preorder(Node[root].lchild);
	//访问右子树
	preorder(Node[root].rchild); 
	//访问根节点root，例如将其数据输出
	printf("%d\n",Node[root].data);
} 

//层序遍历
void LayerOrder(int root){
	queue<int>q;//此处队列里存放结点的下标
	q.push(root);//将根节点地址入队
	while(!q.empty()){
		int now=q.front();//取出队首元素
		q.pop();
		printf("%d",Node[now].data);
		if(Node[now].lchild!=-1) q.push(Node[now].lchild);
		if(Node[now].rchild!=-1) q.push(Node[now].rchild);//右子树非空 
		
	} 
} 

 二叉树实现了完全的静态转换