【数据结构】二叉树的操作2

川长思鸟来 2022-08-25 13:55 106阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    typedef struct BiTree
    {
        ElemType elem;
    	BiTree * LChild;
    	BiTree * RChild;
    }BiTree,* PBiTree;
    
    /*先序顺序创建二叉树*/
    PBiTree CreateBiTree();
    /*先序顺序遍历二叉树*/
    void PreOrderTraverse(PBiTree T);
    /*中序顺序遍历二叉树*/
    void InOrderTraverse(PBiTree T);
    /*后序顺序遍历二叉树*/
    void PostOrderTraverse(PBiTree T);
    /*遍历查找叶子节点*/
    void TravelLeadNode(PBiTree T);
    /*计算树的高度*/
    int CountTreeHeight(PBiTree T);
    
    int main()
    {
    	PBiTree Tree;
    	int TreeHeight = 0;
    
    	printf("按照先序顺序创建二叉树：\n");
    	Tree = CreateBiTree();
    	
    	printf("\n按照先序顺序输出\n");	
    	PreOrderTraverse(Tree);
    	
    	printf("\n按照中序顺序输出\n");	
    	InOrderTraverse(Tree);
    	
    	printf("\n按照后序顺序输出\n");	
    	PostOrderTraverse(Tree);
    	
    	printf("\n叶子结点为：\n");
    	TravelLeadNode(Tree);
    
    	TreeHeight = CountTreeHeight(Tree);
    	printf("\n树的深度为：%d\n",TreeHeight);
    	
    	return 0;
    }
    
    PBiTree CreateBiTree()
    {
    	PBiTree Tree = NULL;
    	ElemType elem = '\0';
    	scanf("%c",&elem);
    	
    	if (elem == '#')
    	{
    		Tree = NULL;
    	}
    	else
    	{
    		Tree = (PBiTree)malloc(sizeof(BiTree));
    		Tree->elem = elem;
    		Tree->LChild = CreateBiTree();
    		Tree->RChild = CreateBiTree();
    	}
    	
    	return Tree;
    }
    
    
    void PreOrderTraverse(PBiTree T)
    {
    	if (T != NULL)
    	{
    		printf("%c ",T->elem);
    		
    		PreOrderTraverse(T->LChild);
    		PreOrderTraverse(T->RChild);
    	}
    	else 
    		return;
    }
    
    
    void InOrderTraverse(PBiTree T)
    {
    	if (T != NULL)
    	{
    		if (T->LChild != NULL)
    		{
    			InOrderTraverse(T->LChild);
    		}
    		
    		printf("%c ",T->elem);	
    		InOrderTraverse(T->RChild);	
    	}
    }
    
    
    void PostOrderTraverse(PBiTree T)
    {
    	if (T != NULL)
    	{
    		if (T->LChild != NULL)
    		{
    			PostOrderTraverse(T->LChild);
    		}
    		
    		PostOrderTraverse(T->RChild);	
    		printf("%c ",T->elem);
    	}
    }
    
    
    void TravelLeadNode(PBiTree T)
    {
    	if (T != NULL)
    	{
    		if (T->LChild == NULL && T->RChild == NULL)
    		{
    			printf("%c ",T->elem);
    		}
    		
    		TravelLeadNode(T->LChild);
    		TravelLeadNode(T->RChild);
    	}
    }
    
    
    int CountTreeHeight(PBiTree T)
    {
    	if (T != NULL)
    	{
    		return	CountTreeHeight(T->LChild) > CountTreeHeight(T->RChild) 
    			? CountTreeHeight(T->LChild)+1 : CountTreeHeight(T->RChild)+1;
    	}
    	else
    	{
    		return 0;
    	}
    }