数据结构之二叉树创建及其遍历

时间:2022-09-30 10:43:55

        还记得N年想在全盘电脑寻找一个文件,当时看那代码晦涩难懂,后来不了了之,最近复习了下二叉树,现在感觉全盘寻找文件不是想象的那么复杂。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef char TElemType;
typedef struct SBiTNode
{
	TElemType data;
	struct SBiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//采用左序遍历创建二叉树,用到的是递归算法,参数指针T有点晦涩难懂。
void CreateBiTree(BiTree *T)
{
	TElemType ch;
	scanf("%c",&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 PreOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	printf("%c",T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}
//中序遍历
void InOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	InOrderTraverse(T->lchild);
	printf("%c",T->data);
	InOrderTraverse(T->rchild);
}
//后序遍历
void PostOrderTraverse(BiTree T)
{
	if(T==NULL)
		return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c",T->data);
}
//主函数
int main()
{
	BiTree T;
	CreateBiTree(&T);		//创建二叉树
	PreOrderTraverse(T);	//左序遍历
	printf("\n");
	InOrderTraverse(T);		//中序遍历
	printf("\n");
	PostOrderTraverse(T);	//后序遍历
	printf("\n");
	return 0;
} 

        本段代码CreateBiTree函数的形参为BiTree *T,为何是这样的,值得去思考下。目的是主函数创建了结构体指针T,如果形参为BiTree T,调用CreateBinary后,它传递的是值传递,最后的结构就是二叉树创建后,你无法拥有二叉树的根节点指针,相当于创建的二叉树内存创建了,可是你却找不到它。

        程序运行效果图如下:

数据结构之二叉树创建及其遍历数据结构之二叉树创建及其遍历