3--数据结构－二叉树的遍历.cpp

来自「数据结构中某几个算法.以及利用数据结构算法实现简单 停车场管理程序.」· C++ 代码 · 共 93 行

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>

typedef struct bitnode{
//----------二叉树的二叉线索储存表示-----------------------------------
	char date;
	struct bitnode *lchild, * rchild;    //-----左右孩子指针-----------
}bitnode, *bitree;

int btree(bitree &t){
//-----------按先序输入2叉树中结点的值，用 ^ 字符表示空树--------------
//-----------           构造二叉链表表示二叉树t          --------------
	char x;
	cin>>x;
	if (x=='^') t=NULL;
	else{
		if(!(t=(bitnode *)malloc(sizeof (bitnode))))
		{
			exit (-2);
		}
		t->date = x;          //-----生成根结点-----
		btree (t->lchild);    //-----构造左子树-----
        btree (t->rchild);    //-----构造右子树-----
	}
	return 1;
}

printtree(bitree t)
{
//------------按照创建的树打印出来-------------
	if(!t) return 0;
	else
	{
		cout<<t->date<<"  ";
	} 
	printtree(t->lchild);
	printtree(t->rchild);
}

void preorder(bitree t)
{
//-------------先序遍历二叉树的函数-------------
	cout<<t->date<<"  ";
	if(t->lchild!=NULL)
		preorder(t->lchild);
	if (t->rchild!=NULL)
		preorder(t->rchild);
}

void midorder(bitree t)
{
//-------------中序遍历二叉树的函数-------------
	if (t->lchild!=NULL)
		midorder(t->lchild);
	cout<<t->date<<"  ";
	if (t->rchild!=NULL)
		midorder(t->rchild);
}

void postorder(bitree t)
{
//-------------后序遍历二叉树的函数------------
	if (t->lchild!=NULL)
		postorder(t->lchild);
	if (t->rchild!=NULL)
		postorder(t->rchild);
	cout<<t->date<<"  ";
}

main()
{
//-------------程序主题-------------
	char ch;
	bitree t;
	do{
	cout<<"输入树，用 ^ 字符代表空子树：";
	btree(t);
	cout<<"创建树如下：";
    printtree(t);
	cout<<"\n\n"<<"--------------------下面开始操作--------------------"<<endl;
    cout<<endl<<"先序遍历树：";
	preorder(t);                   //----先序输出二叉树----
	cout<<endl<<"中序遍历树：";
	midorder(t);                   //----中序输出二叉树----
	cout<<endl<<"后序遍历树：";
	postorder(t);                  //----后序输出二叉树----
	cout<<endl<<"继续?(y/n)?";
	cin>>ch;
	}
	while (ch=='y');
}