数据结构二叉树的构造与遍历-创新互联

本文主要是给c语言初学者或数据结构初学者展示二叉树的构造与遍历，可以作为简单的参考。除了代码外，本文有部分博主自己对代码的简单分析，可以通过下面的链接免费下载。

#include "stdafx.h"

// 各种引用
#include#include#include#include#define NULL 0 

int m_nNumOfLeaf=0;   // 叶子结点数量

typedef char ElemType;   //定义二叉树结点中保存的数据的数据类型

typedef struct BinaryNode  //定义二叉树结点的数据类型
{ElemType data;  //存放二叉树结点数据
    struct BinaryNode *lchild, *rchild;  //存放二叉树结点左右子树的指针（指向的数据类型是本身）
} BTNode; 


BTNode * m_root= NULL; // 二叉树指针（指向二叉树的根结点）

BTNode * CreatebBinaryTree()  
{BTNode *T; 
    ElemType x; 
    scanf("%c",&x);  // 获取结点数据
    if(x=='#') // 空结点
        T=NULL; 
    else  // 非空结点
    {T=(BTNode*)malloc(sizeof(BTNode));  // 申请空间存储结点
        T->data=x;  // 存储数据
        T->lchild=CreatebBinaryTree();    // 建立以本结点为根的左子树
        T->rchild=CreatebBinaryTree(); 	  // 建立以本结点为根的右子树
    } 

    return(T); // 返回根结点
} 

void PreOrderPrint(BTNode *t) 
{if(t!=NULL)   // 根结点不为空
    {printf("%c\t",t->data);    // 输出根结点
        PreOrderPrint(t->lchild);  // 前序遍历以本结点为根的左子树
        PreOrderPrint(t->rchild);  // 前序遍历以本结点为根的右子树
    } 
} 

void InOrderPrint(BTNode *t) 
{if(t!=NULL) // 根结点不为空
    {InOrderPrint(t->lchild);  // 中序遍历以本结点为根的左子树
        printf("%c\t",t->data);   // 输出根结点      
        InOrderPrint(t->rchild);  // 中序遍历以本结点为根的右子树
    } 
}

void PostOrderPrint(BTNode *t) 
{if(t!=NULL) // 根结点不为空
    { 
        PostOrderPrint(t->lchild); // 后序遍历以本结点为根的左子树
        PostOrderPrint(t->rchild); // 后序遍历以本结点为根的右子树
		printf("%c\t",t->data);    // 输出根结点
    } 
}

void CalNumOfLeaf(BTNode *t)
{if(t!=NULL)  // 根结点不为空
	{if((t->lchild!=NULL)||(t->rchild!=NULL))  // 判断该结点是否有左右子树		
		{	CalNumOfLeaf(t->lchild);     // 计算该结点左子树的叶子结点数     
		    CalNumOfLeaf(t->rchild);     // 计算该结点右子树的叶子结点数   
		}
        else m_nNumOfLeaf++;  // 是叶子结点,则叶子结点数加1
	}
}

int main(int argc, char* argv[]) // 主函数
{printf("              ***************************************\n");
	printf("                            二叉树操作\n");
	printf("              ***************************************\n");
	

	int flag = 1;
	while(flag)
	{printf("\n\n\t\t 1--建立\n");
		printf("\t\t 2--前序遍历\n");
		printf("\t\t 3--中序遍历\n");
		printf("\t\t 4--后序遍历\n");
		printf("\t\t 5--叶子的数量\n");
		printf("\t\t 0--退出程序\n");

		printf("\t\t 程序编写人<姓名:%s ; 学号:%s>\n","张三","123456789"); // 显示 姓名和学号

		scanf("%d",&flag);
		switch(flag)
		{	case 1:  // 建立二叉树
			{	getchar(); // 获取输入的回车
				printf("请输入二叉树各结点(前序顺序,#代表空结点),形式如(AB###,ABC#####)：\n"); // 输出字符串
				m_root = CreatebBinaryTree();  // 构建二叉树(前序)
				printf("建立二叉树完毕：\n");  // 输出字符串
			}				
				break;				
			case 2:  // 前序遍历
			{		if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树前序遍历的顺序为：\n"); // 输出字符串

					PreOrderPrint(m_root); // 前序遍历输出

					printf("\n二叉树前序遍历结束：\n"); // 输出字符串
				}

			}
				break;
			case 3:  // 中序遍历
			{	
				if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树中序遍历的顺序为：\n"); // 输出字符串

					InOrderPrint(m_root); // 中序遍历输出

					printf("\n二叉树中序遍历结束：\n"); // 输出字符串
				}
			}
				break;

			case 4:  // 后序遍历
			{	
				if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{printf("\n二叉树后序遍历的顺序为：\n"); // 输出字符串

					PostOrderPrint(m_root); // 后序遍历输出

					printf("\n二叉树后序遍历结束：\n"); // 输出字符串
				}

			}
				break;
			case 5:  // 计算叶子结点的数目
			{		if(m_root == NULL)  // 出错判断
				{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
				}
				else
				{m_nNumOfLeaf=0;   // 叶子结点数量初始化
					CalNumOfLeaf(m_root);   // 计算叶子结点数量

					printf("\n当前二叉树中叶子数量为:%d\n",m_nNumOfLeaf); // 输出字符串
				}
			}
				break;
			case 0:  // 退出程序
				break;

			default: // 输入错误
				printf("请输入正确的数字!!!\n");
				break;
		}

	}
	return 0;

}

下载

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧