留学生虚心求指点，高分，在线等，二叉树C++代码的实现的基本解释，也请看看我的代码,提出指正。周围实在是找不
留学生虚心求指点，高分，在线等，二叉树C++代码的实现的基本解释，也请看看我的代码,提出指正。
周围实在是找不到说汉语的人帮我解释。网上有很多的例子，也有讲解，但是新手，有部分地方还是看不太懂。学校的课程讲的很泛泛，教授又是个怪老头儿，需要自己再自学很多东西，二叉树的基本实现是我们的一个作业，很基础。麻烦大家了，谢谢。
1.中序遍历，老师的要求是函数输出结点值，并且每个值之前用“—”分开，输出的样式：2-3-8-10；
而输出中序函数只实现一个输出功能。我自己在想：可能需要两个函数，一个实现中序遍历，一个是实现输出中序，但是这个分隔符不知道怎么处理了，估计是不能用递归实现中序。这个是实现中序的一段代码
void inorder_nonrecursive(tree root)
{
tree stack[100];
int top = 0;
tree p = root;
while (NULL != p || top > 0)
{
while (NULL != p) //左边
{
stack[top++] = p; // 进
p = p->left_child;
}
p = stack[--top]; //出
cout<< p->data; //输出根
p = p->right_child;//右边
}
}
这个循环有点没看太懂，遍历右子叔开始后，回到第一个循环开始，进行右边遍历，是怎么运行的？因为回到第一个循环开始，进入第二个循环，又会遍历一遍左子树（p=p->left_child)....
cout<< p->data 是输出根结点还是输出子树的值？如果是根结点的话，不是已经进栈了吗，在p = stack[--top]不就能输出根了吗？
谢谢
[解决办法]
其实也可以不用那么复杂，中序遍历的顺序是：左根右。如果递归去访问的话，在访问到根节点的时候输出就可以了。
[解决办法]
- C/C++ code
/* 程序名：二叉树功能实现 程序功能：二叉树功能 程序的菜单功能项如下： 1------建立一棵二叉树 2------前序遍历递归算法 3------前序遍历非递归算法 4------中序遍历递归算法 5------中序遍历非递归算法 6------后序遍历递归算法 7------后序遍历非递归算法 8------求树高 9------求叶子总数 10-----输出二叉树 11-----退出 */ #include <iostream> #include<iomanip> #include<queue> using namespace std; template<class T> struct Node { T data; Node<T> *lchild,*rchild; }; template<class T> class BTree { private: int height;//结点书 int dep;//树高 Node<T> *input1();//前序输入 Node<T> *input2();//中序输入 Node<T> *input3();//后序输入 Node<T> *input4();//层次输入 Node<T> *root; public: BTree(){}; ~BTree(){}; void CreateBTree(); void preorder(); //前序递归遍历 void preorder(Node<T> *p);//以树的结点展开对所有结点前序递归遍历 void preorder1();//前序非递归遍历 void inorder();//中序递归遍历 void inorder(Node<T> *p);//以树的结点展开对所有结点遍历 void inorder1();//中序非递归遍历 void postorder();//后序递归遍历 void postorder(Node<T> *p);//以树的结点展开对所有结点遍历 void postorder1();//后序非递归遍历 void print();//输出二叉树 void num();//无参数的函数，求树的结点数 int num(Node<T> *P);//求二叉树的所有结点 void depth();//二叉树的高度 int depth(Node<T> *p);//二叉树的高度 }; //前序输入 template<class T> Node<T> *BTree<T>::input1() { Node<T> *p; T ch; cin>>ch; if(ch=='#') return(NULL); p=new Node<T>; p->data=ch; p->lchild=input1(); p->rchild=input1(); return p; } //中序输入 template<class T> Node<T> *BTree<T>::input2() { Node<T> *p,*q; T ch; cin>>ch; if(ch=='#') return 0; else q=input2(); p=new Node<T>; p->data=ch; p->lchild=q; p->rchild=input2(); return p; } //后序输入 template<class T> Node<T> *BTree<T>::input3() { Node<T> *q1,*q2,*p; T ch; cin>>ch; if(ch=='#') return 0; else q1=input3(); q2=input3(); p=new Node<T>; p->data=ch; p->lchild=q1; p->rchild=q2; return p; } //层次输入 template<class T> Node<T> *BTree<T>::input4() { T m; int i; Node<T> *p,*q; queue<Node<T> *> st; cin>>m; root->data=m; st.push(root); while(!st.empty()&&p!=NULL) { p=st.front(); for(i=0;i<2;i++) { cin>>m; if(m=='@') return root; if(m=='#') q=NULL; else { q=new Node<T>; q->data=m; q->lchild=q->rchild=NULL; } if(i==0) p->lchild=q; else { p->rchild=q; } st.push(q); } st.pop(); } return root; } template<class T> void BTree<T>::CreateBTree() { int m; cout<<"输入说明：当结点为空时，用#代表，当层次输入时，以@为结束符!!!"<<endl; cout<<"请选择输入的方法：1--前序;2--中序;3--后序;4--层次。"<<endl; cout<<"请选择建立二叉树的方法序号1~4:"; cin>>m; if(m>4 || m<1) { cout<<"输入错误，请重新输入："; } else cout<<"请输入二叉树："; switch(m) { case 1:root=input1();break; case 2:root=input2();break; case 3:root=input3();break; case 4:root=input4();break; } } template<class T> void BTree<T>::preorder(Node<T> *p) { if(p!=NULL) { cout<<p->data<<setw(3); preorder(p->lchild); preorder(p->rchild); } } template<class T> void BTree<T>::preorder() { cout<<"前序递归遍历:"; preorder(root); cout<<endl; } template<class T> void BTree<T>::inorder(Node<T> *p) { if(p!=NULL) { inorder(p->lchild); cout<<p->data<<setw(3); inorder(p->rchild); } } template<class T> void BTree<T>::inorder() { cout<<"中序递归遍历:"; inorder(root); cout<<endl; } template<class T> void BTree<T>::postorder(Node<T> *p) { if(p!=NULL) { postorder(p->lchild); postorder(p->rchild); cout<<p->data<<setw(3); } } template<class T> void BTree<T>::postorder() { cout<<"后序递归遍历:"; postorder(root); cout<<endl; } template<class T> int BTree<T>::num(Node<T> *p) { if(p==NULL) return 0; else return(num(p->lchild)+num(p->rchild)+1); } template<class T> void BTree<T>::num() { height=num(root); cout<<"此二叉树的所有结点数为:"<<height<<endl; } template<class T> int BTree<T>::depth(Node<T> *p) { int max; if(p==NULL) return 0; else { max=depth(p->lchild); if(depth(p->rchild)>max) { max=depth(p->rchild); } return(max+1); } } template<class T> void BTree<T>::depth() { dep=depth(root); cout<<"二叉树的深度为:"<<dep<<endl; } int main() { int choice,i=1; BTree<char> bt; cout<<"欢迎来到二叉树的小小系统!\n"; bt.CreateBTree(); while(i!=0) { cout<<"请你选择想要遍历二叉树的方式:\n"; cout<<"1-前序递归遍历\n"; cout<<"2-中序递归遍历\n"; cout<<"3-后序递归遍历\n"; cout<<"4-二叉树的结点数\n"; cout<<"5-二叉树的深度\n"; cout<<"请你选择序号1~5:"; cin>>choice; switch(choice) { case 1:bt.preorder();break; case 2:bt.inorder();break; case 3:bt.postorder();break; case 4:bt.num();break; case 5:bt.depth();break; } cout<<endl; } return 0; }
[解决办法]
这是个非递归的二叉树中序遍历算法，不过其中的输出语句似乎没有输出间隔符号。
- C/C++ code
void inorder_nonrecursive(tree root){ tree stack[100]; int top = 0; tree p = root; while (NULL != p || top > 0) /*若当前子树树非空，或是暂存栈尚未空，则进入循环*/ { while (NULL != p) //左边 /*当前子树非空，则循环推进到左子树为空*/ { stack[top++] = p; // 进 p = p->left_child; } p = stack[--top]; //出 /*左子树已空，弹出当前节点以便处理*/ cout<< p->data; //输出根 p = p->right_child;//右边 /*沿右子树推进指针，循环继续处理*/ }}
[解决办法]