C语言-数据结构-二叉树-遍历

心已赠人 2022-12-24 10:59 143阅读 0赞

### C语言-数据结构-二叉树-遍历 ###

*  一些基本操作
 *   *  定义二叉树结构体
     *  访问根节点
 *  二叉树的遍历
 *   *  前序遍历二叉树
     *  中序遍历二叉树
     *  后序遍历二叉树
 *  二叉树遍历的部分应用
 *   *  基于二叉树遍历输出叶子结点
     *  基于遍历序列建立二叉树
     *  基于遍历求二叉树深度
     *  基于遍历统计叶子结点数目
 *  结语

# 一些基本操作 #

## 定义二叉树结构体 ##

typedef struct Node
    {
        
    	char data;
    	struct Node* LChild;
    	struct Node* RChild;
    }BiTNode, * BiTree;

## 访问根节点 ##

void Visit(char data)  //读取数据并输出
    {
        
    	printf("%c", data);
    }

# 二叉树的遍历 #

## 前序遍历二叉树 ##

void PreOrder(BiTree root)   //前序遍历
    {
        
    	if (root != NULL)
    	{
        
    		Visit(root->data);
    		PreOrder(root->LChild);
    		PreOrder(root->RChild);
    	}
    }

## 中序遍历二叉树 ##

void InOrder(BiTree root)   //中序遍历
    {
        
    	if (root != NULL)
    	{
        
    		InOrder(root->LChild);
    		Visit(root->data);
    		InOrder(root->RChild);
    	}
    }

## 后序遍历二叉树 ##

void PostOrder(BiTree root)   //后序遍历
    {
        
    	if (root != NULL)
    	{
        
    		PostOrder(root->LChild);
    		PostOrder(root->RChild);
    		Visit(root->data);
    	}
    }

# 二叉树遍历的部分应用 #

## 基于二叉树遍历输出叶子结点 ##

void PreOrder2(BiTree root)   //前序遍历输出叶子节点
    {
        
    	if (root != NULL)
    	{
        
    		if (root->LChild == NULL && root->RChild == NULL)
    			Visit(root->data);
    		PreOrder2(root->LChild);
    		PreOrder2(root->RChild);
    	}
    }

该实例为利用前序遍历输出叶子节点 其他遍历方法以此类推

## 基于遍历序列建立二叉树 ##

int exitdata=0;//用于记录二叉树是否建立完 1是0否
    
    void CreatBitree(BiTree* bt)      //基于遍历序列建立二叉链表
    {
        
    	char ch;
    
    	if (exitdata == 1)
    		return;
    	ch = getchar();
    
    	if (ch == '.')              //表示二叉树子树为空
    		*bt = NULL;
    	else if (ch == '\n')
    	{
        
    		*bt = NULL;
    		exitdata = 1;
    	}
    	else
    	{
        
    		*bt = (BiTree)malloc(sizeof(BiTNode));
    		(*bt)->data = ch;
    		(*bt)->LChild = NULL;
    		(*bt)->RChild = NULL;
    
    		CreatBitree(&((*bt)->LChild));
    		CreatBitree(&((*bt)->RChild));
    	}
    }

## 基于遍历求二叉树深度 ##

int PostTreeDepth(BiTree root)  //后续遍历求二叉树高度
    {
        
    	int hl, hr, max;
    	if (root != NULL)
    	{
        
    		hl = PostTreeDepth(root->LChild)+1;
    		hr = PostTreeDepth(root->RChild)+1;
    		max = hl > hr ? hl : hr;
    		return max;
    	}
    	else
    		return (0);
    }

## 基于遍历统计叶子结点数目 ##

int leaf(BiTree root)      //统计叶子结点数目
    {
        
    	int LeafCount;
    
    	if (root == NULL)
    		LeafCount = 0;
    	else if (root->LChild == NULL && root->RChild == NULL)
    		LeafCount = 1;
    	else
    		LeafCount = leaf(root->LChild) + leaf(root->RChild);
    
    	return LeafCount;
    }

# 结语 #

好好学习,天天向上  
代码是书上抄的 完全不知道该投啥 你们知道的话请告诉我 我去改下  
![在这里插入图片描述][2020112721422158.jpg_pic_center]

[2020112721422158.jpg_pic_center]: /images/20221120/83949321814044308b6dd3a6962e2de7.png