求解C++实现数组存储完全二叉树，要求实现非递归中序遍历

求解用C++实现用数组存储一个完全二叉树，要求实现非递归中序遍历。

你看下这篇博客吧, 应该有用👉 ：用C++实现非递归二叉树的中序遍历
除此之外, 这篇博客: 用C++实现非递归二叉树的中序遍历中的 直接上代码： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

大体思路：借助栈来实现要中序遍历的元素

#include <bits/stdc++.h>

using namespace std;

typedef struct BiTNode{
	char data;//数据域 
	struct BiTNode *lchild,*rchild;//左右孩子指针 
}BiTNode,*BiTree;

stack<BiTree> s;//创建栈用于中序遍历 


/*
初始化树，给树分配内存空间 
*/ 
void InitBiTree(BiTree *T){
	*T = NULL;
}

/*
创建树，以先序方式插入树节点 
*/
void createBiTree(BiTree *T){
	char ch;
	cin>>ch;
	if(ch =='#') *T=NULL;
	else{
		*T = (BiTree)malloc(sizeof(BiTNode));
		if(!(*T)) exit(-1);
		//按照先序的方式插入生成树 
		(*T)->data = ch;
		createBiTree(&((*T)->lchild));
		createBiTree(&((*T)->rchild));
	}
}

/*
利用栈，对二叉树进行非递归中序遍历 
*/
void InOrder(BiTree T){
	BiTree p = T;//p是遍历指针 
	while(p||!s.empty()){//当栈不空或p不空时进入下面循环 
		if(p){ 			//如果p不为空就一路向左并将所有左孩子入栈 
			s.push(p);
			p = p->lchild;
		}else{			//当碰到最后一个左孩子的左节点为空时，进入该循环，进行出栈 
			p=s.top();
			cout<<p->data<<" ";
			s.pop();
			p = p->rchild;//出完栈后，转到右孩子 
		}
	}
	cout<<endl;
}


int main(){
	BiTree T;
	InitBiTree(&T);
	cout<<"请按照先序地方式输入二叉树(输入#代表空)：如ABC##D##EF##G##"<<endl;
	createBiTree(&T);
	cout<<"该二叉树的中序遍历是："; 
	InOrder(T);
	
	return 0;
}

参考一下

非递归实现二叉树先序、中序、后序和层序遍历_MengYiKeNan的博客-CSDN博客_非递归实现中序文章目录用非递归的方式实现二叉树的先序遍历用非递归的方式实现二叉树的中序遍历：用非递归的方式实现二叉树的后序遍历：用非递归的方式实现二叉树的层次遍历：用递归方式实现二叉树先序、中序和后序遍历很简单。用递归方法解决的问题都能用非递归的方法实现。递归就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。用非递归的方式实现二叉树的先序遍历1、申请一个栈stack，然后将头节点压入stack中。2、从stack中弹出栈顶节点，打印，再将其右孩子节点（不为空的话）先压入s

https://blog.csdn.net/MengYiKeNan/article/details/111427190


#include <bits/stdc++.h>

using namespace std;

typedef struct BiTNode{
    char data;//数据域 
    struct BiTNode *lchild,*rchild;//左右孩子指针 
}BiTNode,*BiTree;

stack<BiTree> s;//创建栈用于中序遍历 


/*
初始化树，给树分配内存空间 
*/ 
void InitBiTree(BiTree *T){
    *T = NULL;
}

/*
创建树，以先序方式插入树节点 
*/
void createBiTree(BiTree *T){
    char ch;
    cin>>ch;
    if(ch =='#') *T=NULL;
    else{
        *T = (BiTree)malloc(sizeof(BiTNode));
        if(!(*T)) exit(-1);
        //按照先序的方式插入生成树 
        (*T)->data = ch;
        createBiTree(&((*T)->lchild));
        createBiTree(&((*T)->rchild));
    }
}

/*
利用栈，对二叉树进行非递归中序遍历 
*/
void InOrder(BiTree T){
    BiTree p = T;//p是遍历指针 
    while(p||!s.empty()){//当栈不空或p不空时进入下面循环 
        if(p){             //如果p不为空就一路向左并将所有左孩子入栈 
            s.push(p);
            p = p->lchild;
        }else{            //当碰到最后一个左孩子的左节点为空时，进入该循环，进行出栈 
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p = p->rchild;//出完栈后，转到右孩子 
        }
    }
    cout<<endl;
}


int main(){
    BiTree T;
    InitBiTree(&T);
    cout<<"请按照先序地方式输入二叉树(输入#代表空)：如ABC##D##EF##G##"<<endl;
    createBiTree(&T);
    cout<<"该二叉树的中序遍历是："; 
    InOrder(T);
    
    return 0;
}