二叉树的遍历及其应用C/C++代码实现

超、凢脫俗 2023-02-16 05:46 9阅读 0赞

## 二叉树的存储结构： ##

**顺序存储**：只适合完全二叉树。  
**链式存储**：利用这种结点结构所得二叉树的存储结构分别称之为二叉链表和三叉链表。  
![在这里插入图片描述][20200608133349397.png]

## 二叉树的遍历： ##

规定先左后右，按照根结点的访问次序可分为先（根） 序遍历、中（根） 序遍历和后（根） 序遍历。  
![在这里插入图片描述][20200608142836262.png]  
先序遍历序列：ABCDEGF  
中序遍历序列：CBEGDFA  
后序遍历序列：CGEFDBA

注意：  
另外由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树。 但先序序列和后序序列不能唯一确定一棵二叉树。

## 遍历的应用： ##

1，建立二叉链表  
2，复制二叉树  
3，计算二叉树的深度  
4，统计二叉树的结点个数

## 代码如下： ##

#include<stdio.h>
    #include<iostream>
    
    typedef int TElemType;
    
    //二叉树的二叉链表存储结构
    typedef struct BiTNode
    {
        
    	TElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode,*BiTree;
    
    //先序遍历建立二叉树
    void CreateBiTree(BiTree &T)
    {
        
    	char ch;
    	scanf("%c", &ch);
    	if (ch == '#')
    	{
        
    		T = NULL;
    	}
    	else
    	{
        
    		T = new BiTNode;
    		T->data = ch;
    		CreateBiTree(T->lchild);
    		CreateBiTree(T->rchild);
    	}
    }
    
    //先序遍历复制二叉树
    void Copy(BiTree T, BiTree &NewT)
    {
        
    	if (T == NULL)			//空树 ，递归结束
    	{
        
    		NewT = NULL;
    		return;
    	}
    	else
    	{
        
    		NewT = new BiTNode;
    		NewT->data = T->data;			//复制
    		Copy(T->lchild, NewT->lchild);	//递归复制左子树
    		Copy(T->rchild, NewT->rchild);	//递归复制右子树
    	}
    }
    
    // 计算二叉树的深度
    // 二叉树的深度为左右子树深度的较大者加1。 
    int Depth(BiTree T)
    {
        
    	int m, n;
    	if (T == NULL)
    	{
        
    		return 0;
    	}
    	else
    	{
        
    		m = Depth(T->lchild);
    		n = Depth(T->rchild);
    		if (m > n) return (m + 1);		
    		else return (n + 1);
    	}
    }
    
    //计算二叉树结点的个数
    //二叉树的结点数为：左子树的结点数+右子树的结点数+1
    int NodeCount(BiTree T)
    {
        
    	if (T == NULL)
    	{
        
    		return 0;
    	}
    	else
    	{
        
    		return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    	}
    }
    
    
    //先序遍历输出
    void PreOrderTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		printf("%c", T->data);
    		PreOrderTraverse(T->lchild);
    		PreOrderTraverse(T->rchild);
    	}
    }
    //中序遍历输出
    void InOrderTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		InOrderTraverse(T->lchild);
    		printf("%c", T->data);
    		InOrderTraverse(T->rchild);
    	}
    }
    //后序遍历输出
    void PostOrderTraverse(BiTree T)
    {
        
    	if (T)
    	{
        
    		PostOrderTraverse(T->lchild);
    		PostOrderTraverse(T->rchild);
    		printf("%c", T->data);
    	}
    }
    
    
    int main()
    {
        
    	BiTree T;
    	int depth, node;
    	printf("请输入要建立的二叉树的先序序列，用#表示空树（单个字符表示结点）:");
    	CreateBiTree(T);
    	depth = Depth(T);
    	printf("树的深度为：%d\n", depth);
    	node = NodeCount(T);
    	printf("树的节点个数为：%d\n", node);
    
    	//遍历
    	printf("\n先序遍历：");
    	PreOrderTraverse(T);
    	printf("\n中序遍历：");
    	InOrderTraverse(T);
    	printf("\n后序遍历：");
    	PostOrderTraverse(T);
    	printf("\n");
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]

[20200608133349397.png]: https://img-blog.csdnimg.cn/20200608133349397.png
[20200608142836262.png]: https://img-blog.csdnimg.cn/20200608142836262.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200608144039978.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70