【数据结构实验作业】——以链式存储结构的二叉树的递归遍历输出它的先序,中序,后序遍历序列以及高度

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define NULL 0
typedef char TElemType; 
typedef int Status;//用作函数值类型,表示函数结构状态 
typedef struct BiTNode { // 结点结构
TElemType	data;
struct BiTNode	*lchild, *rchild;	// 左右孩子指针 (成员变量也可以是指向结构体自身的指针) 
} BiTNode, *BiTree;//*Bitree是指向结点结构体的指针类型 
//以下是建立二叉树存储结构 
Status CreateBiTree(BiTree &T) {
char ch; 
scanf("%c",&ch);
if (ch=='#') 	T = NULL;
else {
 	T = (BiTree)malloc(sizeof(BiTNode));
 	if(!T){
 		exit(OVERFLOW);
	}
	T->data = ch;
	
	CreateBiTree(T->lchild);//遍历访问根结点的左子树 
	CreateBiTree(T->rchild);//遍历访问根结点的右子树 
}
return OK;
} // CreateBiTree
void PreOrder (BiTree T)
{ // 先序遍历二叉树
if (T) {
printf("%4c",T->data);	// 访问结点
PreOrder(T->lchild);//遍历访问根结点的左子树 
PreOrder(T->rchild); //遍历访问根结点的右子树 
}}


void InOrder (BiTree T)
{ // 中序遍历二叉树
	if (T) {
		InOrder(T->lchild);//遍历访问根结点的左子树 
          printf("%4c",T->data);
          InOrder(T->rchild);//遍历访问根结点的右子树 
          
    }
}
void PostOrder (BiTree T)
{      // 后序遍历二叉树
	if(T){
	PostOrder(T->lchild);// 遍历访问根结点的左子树 
    PostOrder(T->rchild);//遍历访问根结点的右子树 
    printf("%4c",T->data);
		
	}

}

int BiTreeDeep(BiTree T) {

 if(T == NULL)
		return 0;
	else {
		int LTreedeep = BiTreeDeep(T->lchild);
		int RTreedeep = BiTreeDeep(T->rchild);
		
		return (LTreedeep > RTreedeep ? LTreedeep : RTreedeep)+1;
	} 
	if(T->lchild ==NULL&& T->rchild == NULL){
		return 1;
	}
}

int main()
{ 
BiTree T;
T=NULL;//建立空二叉树 
printf("\n 请按先序次序输入各结点的值,以#表示空树:\n");
 CreateBiTree(T);
printf("二叉树已建立完毕!\n");
printf("\n 先序遍历:");
 PreOrder(T);
printf("\n 中序遍历:");
 InOrder(T);
 printf("\n 后序遍历:");
 PostOrder(T); 
 int i = BiTreeDeep(T);
	printf("\n二叉树深度:%d",i);
    return 0;
}

实验结果输出
【数据结构实验作业】——以链式存储结构的二叉树的递归遍历输出它的先序,中序,后序遍历序列以及高度

上一篇:数据结构(4)—— 树与二叉树


下一篇:数据结构-二叉树编程