首先定义二叉树的节点

 

struct BTNode{	int data;	BTNode *left;	BTNode *right;};

然后先序建立二叉树

 

思路：以数组中的元素先序构建二叉树，过程就是不断插入，直至数组中没有元素

 

//先序建立二叉树void insert_node(BTNode **root, int *data, int i){	if(i<=data[0])	{		*root = new BTNode();		(*root)->data = data[i];		(*root)->left=NULL;		(*root)->right=NULL;		insert_node(&((*root)->left), data, 2*i);		insert_node(&((*root)->right), data, 2*i+1);	}}

再进行遍历二叉树的操作，先序，中序，后续，以及层序遍历

 

 

//递归实现二叉树的遍历void pre_order(BTNode *root){	if(root!=NULL)	{		cout << root->data << " ";		pre_order(root->left);		pre_order(root->right);	}}void in_order(BTNode *root){	if(root!=NULL)	{		in_order(root->left);		cout << root->data << " ";		in_order(root->right);	}}void post_order(BTNode *root){	if(root!=NULL)	{		post_order(root->left);		post_order(root->right);		cout << root->data << " ";	}}//// 非递归实现二叉树的遍历// 先将根节点值输出，再压入栈，接着访问根节点的左孩子// 若左孩子非空，则输出值，压栈，若空则弹栈，访问右孩子// 重复上述步骤，直至树所有节点访问为止/void non_pre_order(BTNode *root){	stack
    
     s;	while(s.size() || root!=NULL)	{		if(root!=NULL)		{			cout << root->data << " ";			s.push(root);			root = root->left;		}		else		{				root = s.top();			s.pop();			root = root->right;		} 	}}//// 非递归实现中序二叉树// 先访问二叉树的根节点，并且压栈，接着访问树的左孩子，若左孩子非空// 则继续访问该孩子的左孩子，若空，则弹出节点，并输出该节点的值，// 并继续该孩子的右孩子，直到访问完二叉树的全部节点/ void non_in_order(BTNode *root){	stack
     
       s;	while(s.size() || root!=NULL)	{		if(root!=NULL)		{			s.push(root);			root = root->left;		}		else		{			root = s.top();			s.pop();			cout << root->data << " ";			root = root->right;		}	}}/// 非递归实现后序遍历二叉树// 先将根节点入栈，再判断栈顶元素是否被访问过// 若未被访问，则依次将栈顶元素的右孩子，左孩子入栈// 重复上述步骤，知道栈空为止void non_post_order(BTNode *root){	stack
      
        s;	BTNode *cur=NULL;		//当前访问的结点	BTNode  *pre=NULL;	//前一个访问的结点	s.push(root);	while(s.size() && root!=NULL)	{		cur = s.top();		if((cur->left==NULL&&cur->right==NULL)		|| (pre!=NULL&&(pre==cur->left||pre==cur->right)))		{			cout << cur->data << " ";			s.pop();			pre = cur;		}		else		{			if(cur->right!=NULL)				s.push(cur->right);			if(cur->left!=NULL)				s.push(cur->left);		}	}}///// 层序遍历二叉树//void floor_order(BTNode *root){	queue
       
         q;	BTNode *cur;	q.push(root);	while(root!=NULL && q.size())	{		cur = q.front();		cout << cur->data << " ";			q.pop();		if(cur->left!=NULL)			q.push(cur->left);		if(cur->right!=NULL)			q.push(cur->right);	}}
       
      
     
    

下面是测试代码：

 

 

int main(void){	int i=0, input;	int data[]={5, 1, 2, 3, 4, 5};	BTNode *root = NULL;	insert_node(&root, data, 1);	//先序遍历二叉树	cout << "递归先序遍历二叉树" << endl;	pre_order(root);	cout << "\n非递归先序遍历二叉树\n";	non_pre_order(root);	cout << "\n递归中序遍历二叉树\n";	//中序遍历二叉树	in_order(root);	cout << "\n非递归中序遍历二叉树\n";	non_in_order(root);	cout << "\n递归后序遍历二叉树\n";	//后序遍历二叉树	post_order(root);	cout << "\n非递归后序遍历二叉树\n";	non_post_order(root);	cout << endl;	//层序遍历二叉树	cout << "层序遍历二叉树\n";	floor_order(root);		cout << endl;	return 0;}

有什么不对，可以指出，共同学习，共同进步！