树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应
文件 main.cpp 代码如下：
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树：
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树：
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[cpp] view plaincopy
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储：
[csharp] view plaincopy
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;
二叉树三种递归的遍历方法：
先序遍历访问根节点→先序遍历左子树→先序遍历右子树
中序遍历中序遍历左子树→访问根节点→中序遍历右子树
后序遍历后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法：
[cpp] view plaincopy
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法：
有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历：
[cpp] view plaincopy
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历：
[cpp] view plaincopy
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历：
[cpp] view plaincopy
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法：（用队列的方法）
[cpp] view plaincopy
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}
已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）
[cpp] view plaincopy
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
c=pre[pre_s]; /* c储存根节点。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c); /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}
template<class T>
void BinTree<T>::view()
{
if (IsNull()) return;
deque<TreeNode<T>*> q;
TreeNode<T>* temp;
q.push_back(root);
while(!q.empty())
{
temp = q.front();
q.pop_front();
cout<<temp->data;
if (temp->Left!=NULL)
q.push_back(temp->Left);
if (temp->Right!=NULL)
q.push_back(temp->Right);
}
cout<<endl;
}
1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define maxsize 100
typedef enum tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
问题来自《数据结构》（严蔚敏、吴伟民著，C语言描述，清华大学出版社，1997年4月第1版），第6章树与二叉树，6.3遍历二叉树和线索二叉树。
遍历二叉树的非递归算法，教材的描述如下（见130页）：
仿照递归算法执行过程中递归工作栈的状态变化状况可直接写出相应的非递归算法。例如，从中序遍历递归算法执行过程中递归工作栈的状态可见：（1）工作记录中包含两项，其一是递归调用的语句编号，其二是指向根结点的指针，则当栈顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈；（2）若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶记录中指针所指的根结点；（3）若是从右子树返回，则表明当前曾的遍历结束，应继续退栈。从另一角度看，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。由此可得两个中序遍历二叉树的非递归算法如下：
=============================================================
算法一：
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
Push(S,T); //根指针进栈
while(!StackEmpty(s))
{
while(GetTop(S,p)&&p)
Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
if(!StackEmpty(S)) //访问结点，向右一步
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse 算法一
============================================================
============================================================
算法二：
Status InOrderTraverse(BiTree T, Status (*Visit)(TelemType e))
{
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
p=T;
while(p||!StackEmpty(S))
{
if(p)
{
Push(S,p);
p=p->lchild;
}//if 根指针进栈，遍历左子树
else
{
Pop(S,p);
if(!Visit(p->data))
return ERROR;
p=p->rchild;
}//else 根指针退栈，访问根结点，遍历右子树
}//while
}InOrderTraverse() 算法二
============================================================
我的问题是，文字描述中提到的“从中序遍历递归算法执行过程中递归工作栈的状态可见：……”的这一部分。我不明白什么是“栈顶记录中的指针”，什么是“工作记录”。不明白第（2）句话中，先说“栈顶记录中的指针值为空”的时候怎么怎么样，后面为什么又会有对“栈顶记录中指针所指的根结点”的访问？这不是前后矛盾的吗？在读完后面的代码并作了认真的分析之后，仍不明白这一段话到底描述了一个什么样的过程，不理解转化成非递归过程的具体实现。请达人指教。
问题补充：参考：
对代码中与栈有关的函数的说明：
InitStack(&S) 构造一个空栈S；
Push(&S,e) 栈已存在时，插入元素e为新的栈顶元素；
StackEmpty(S) 栈已存在时，若为空栈返回TRUE，否则返回FALSE；
GetTop(S,&e) 栈已存在且非空时，用e返回S的栈顶元素；
Pop(&S,&e) 栈S存在且非空时，删除栈顶元素，并用e返回其值；
——摘自该书45页。
中序遍历二叉树的操作递归定义：
若二叉树为空，则空操作；
否则
（1） 中序遍历左子树；
（2） 访问根结点；
（3） 中序遍历右叉树；
——摘自该书128页。
递归过程转为非递归过程的实质：
将原由系统管理的递归工作栈改为由程序员管理。在非递归过程中，递归工作栈同样起着两个作用：其一是将递归调用室的实在参数和返回地址传递给下一层递归；其二是保存本层参数和局部变量，以便从下一层返回本层时继续恢复使用。如果将栈的每一层视为一项待处理的事务，则栈顶记录则是当前急待处理的事务。
——摘自《数据结构》PASCAL语言描述，严蔚敏、吴伟民著，清华大学出版社。
//利用栈将二叉树递归算法转化为非递归算法
#define struct_sizes 20
#define adds 10
typedef struct bitnode//二叉树的定义
{
int data;//二叉树元素数据类型
struct bitnode *lchild,*rchild;//左右孩子
}*bitree;
typedef struct
//顺序栈的定义
{
bitree *base;//栈底指针
bitree *top;//栈顶指针
int stacksize;
}sqstack;
int initstack(sqstack &S)//新建一个空栈
{
S.base=(bitree *)malloc(struct_sizes*sizeof(bitree));
if(!S.base)return 0;
S.top = S.base;
S.stacksize = struct_sizes;
return 1;
}//initstack
int stackempty(sqstack S)
//判断栈是否为空
{
if(S.base==S.top)return 1;
else return 0;
}
int push(sqstack &S,bitree e)//进栈
{
if(S.top - S.base >= S.stacksize)//栈满重新分配空间
{
S.base = (bitree *)realloc(S.base,(S.stacksize + adds) * sizeof (bitree));
if(!S.base)return 0;
S.top = S.base + S.stacksize;
S.stacksize += adds;
}
*(S.top++)=e;
return 1;
}//push
int pop(sqstack &S,bitree &e)//出栈
{
if(S.top == S.base)return 0;
e = * --S.top;
return 1;
}//pop
int gettop(sqstack S,bitree &e)//取栈顶元素
{
if(S.top == S.base) return 0;
e = *(S.top - 1);
return 1;
}//gettop
int mid_travel(bitree T)//递归二叉树中序遍历
{
if(!T)return 0;
else
{
if(T->lchild)mid_travel(T->lchild);
printf(" %d",T->data);
if(T->rchild)mid_travel(T->rchild);
}
return 1;
}
int mid_norecursion(bitree T)
//中序遍历二叉树T的非递归算法，打印每个数据
{
sqstack S;
bitree p;
if(!T)return 0;
initstack(S);push(S,T);//根指针进栈
while(!stackempty(S))
{
while(gettop(S,p)&&p)push(S,p->lchild);//向左走到尽头
pop(S,p); //空指针退栈
if(!stackempty(S))//访问结点，向右一步
{
pop(S,p);printf(" %d",p->data);
push(S,p->rchild);
}
}
return 1;
}
参考资料：http://zhidao.baidu.com/question/16519850.html
帅哥，你是软院的吧
我也是软院的，我也在找这个答案呢
你哪个班的
数据结构的树和二叉树之间怎么转换?
① 加线：在兄弟之间加一连线 ② 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 ③ 旋转：以树的根结点为轴心，将整树顺时针转45° 将二叉树转换成树：① 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连起来...
小白科普丨何为树、二叉树和森林?
存储结构的艺术 二叉树和树的存储方式各具特色。顺序存储结构适用于完全二叉树和满二叉树，链式存储结构利用链表节点方便地表示每个节点。双亲表示法和孩子表示法是树的不同存储方式，而孩子兄弟表示法则进一步简化为二叉链表形式。相互转换的艺术 从树到二叉树的转换规则明确：每个节点左指针指向第一个孩子...
如何将二叉树转换为一棵树?
方法：二叉树转换为树和森林。若二叉树非空，则二叉树根及其左子树为第一棵二叉树形式，二叉树根的右子树又可以看做一个由森林转换后的二叉树，应用同样的方法，直到最后产生一棵没有右子树的二叉树为止，这样就得到一个森林。为了进一步得到树，可用树的二叉链表表示逆方法，即结点的右子树的根、右...
数据结构题目(森林与二叉树)
森林与二叉树转换图 如上图中，有A、E、H、G四个非终端节点，我们知道森林转换成二叉树的规则是：兄弟相连，长兄为父，孩子靠左。而每个非终端节点在转换前都有孩子，A有BCD，E有F，H有J，G有HI，按照规则兄弟相连，长兄为父，一个结点会成为前面兄弟的右节点，如：BCD本来是兄弟，转换成二叉树...
将二叉树转化为树(森林)?
假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林 转换方法：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连续删除。直到所有这些根结点与右孩子的连线都删除为止。分离后的二叉树 二叉树转树 （1）、加线。若某结点...
...转化的二叉树(孩子兄弟表示法)的关系,并说明转化后的二叉树的...
1、转换后的二叉树没有右子树 2、原树中叶子就变成了没有左子树的结点了 3、树的先根遍历就和这个二叉树的先序一样 4、树的后根遍历就和这个二叉树的中序一样 还有一些别的可以慢慢推导出来
二叉树与树(或森林)之间能不能转化?为什么
可以转换啊，使用左孩子右兄弟，将一棵棵的树先转换为二叉树后，再从第二棵树开始，依次将根连接在前一棵树根的右子树上就可以了
把一棵树转换为二叉树后,这棵树的形态是唯一的吗
一棵树转换为二叉树后，这棵二叉树的形态唯一
森林的先序遍历和中序遍历与所转换的二叉树的?
根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的...
请问二叉树和一般树是如何转换的?
将右兄弟节点，变为右子代节点，左子代不变
商葛盐酸：[答案] int IsSearchTree(const BTNode *t){ if(!t) //空二叉树情况 return 1;已经上机验证成功,的写的太随意了吧,各种情况都需要考虑地.
沂南县17545175888： 数据结构的树和二叉树之间怎么转换? - ？
商葛盐酸： 将树转换成二叉树:① 加线:在兄弟之间加一连线 ② 抹线:对每个结点,除了其左孩子外,去除其与其余孩子之间的关系 ③ 旋转:以树的根结点为轴心,将整树顺时针转45° 将二叉树转换成树:① 加线:若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子……沿分支找到的所有右孩子,都与p的双亲用线连起来 ② 抹线:抹掉原二叉树中双亲与右孩子之间的连线 ③ 调整:将结点按层次排列,形成树结构
沂南县17545175888： 树的应用 要求:实现树与二叉树的转换的实现.以及树的前序、后序的递归、非递归算法,层次序的非递归算法？
商葛盐酸： 初始条件:二叉树T存在,Visit是对结点操作的应用函数.修改算法6.1 // 实现树与二叉树的转换的实现.以及树的前序、后序的递归、非递归算法,层次
沂南县17545175888： 树与二叉树的转换的实现 - ？
商葛盐酸： int IsSearchTree(const BTNode *t){ if(!t) //空二叉树情况 return 1;已经上机验证成功,的写的太随意了吧,各种情况都需要考虑地.
沂南县17545175888： 森林与二叉树的转换 - ？
商葛盐酸： 树、森林与二叉树的转换1、 树、森林转换成二叉树将一棵树转换成二叉树的方法:将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可,此时,树中的每个结点最多有两个指针:一个指针指向第一个孩子,另一个指针指...
沂南县17545175888： 树怎样转成二叉树?关于二叉树的公式有哪些?如题.最好详细些.关于二叉树的公式最基本的就可以,不要推导过程也行. - ？
商葛盐酸：[答案] 树与二叉树 树是一种简单的非线性结构,所有元素之间具有明显的层次特性. 在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根.每一个结点可以有多个后件,称为该结点的子结点.没有后件...
沂南县17545175888： 数据结构的树和二叉树之间怎么转换?？
商葛盐酸： 由根结点往下,如果有多个孩子那么这一层的孩子都作为本层第一个结点的右孩子的右孩子的右孩子……而本层第一个结点则作为它们双亲结点的左孩子,比如一个只有两层四个结点的树,变换完了以后就变成:根结点-》往左有一个孩子-》往右一个孩子-》继续往右一个孩子 这样的折线型
沂南县17545175888： 树怎么转化为二叉树 - ？
商葛盐酸： 1、去除所有父结点也孩子结点连线; 2、把父结点与最左边的孩子相连,作为父结点的左孩子; 3、把同层结点的兄弟结点相连作为左边兄弟的右孩子; 以此类推所有结点即得到二叉树.
沂南县17545175888： C++实现树与二叉树的转换.树的前序, 后序的递归,非递归算法,层次序的非递归算法的实现,包含建树的实现. - ？
商葛盐酸： #include <stdio.h>#include <malloc.h> typedef struct node{int data;struct node *lchild,*rchild; }*treetp,tree; treetp create (treetp t,int c); void print1(treetp); void print2(treetp); void print3(treetp); int number=0; void main() { treetp t=0,r;r=create (t,0);...
沂南县17545175888： 树与二叉树的转换 - ？
商葛盐酸： 你的意思是说这个右孩子是某一节点的唯一孩子......把树转换成二叉树后..此＂右孩子＂将变成这个节点的左孩子 应该能满足你的要求!
