C语言写二叉树

叁歲伎倆 2024-03-31 12:38 61阅读 0赞

## C语言写二叉树 ##

简介：本文是博主当初学习阶段，用C语言实现的二叉树代码。

### 结点类（TNode.h） ###

#ifndef _TNode_h_
    #define _TNode_h_
    
    // 定义二叉树结点类型
    typedef struct _TNODE_
    {
        
        // 数据域
        char data;
        // 指针域(左、右孩子指针)
        struct _TNODE_ *lch, *rch;
    } TNODE;
    
    #endif

### 二叉树类（BinTree.h） ###

#ifndef _BinTree_h_
    #define _BinTree_h_
    
    #include "TNode.h"
    // 创建二叉树
    void BinTreeCreate(TNODE **root); 
    
    // 创建二叉树
    void BinTreeClear(TNODE **root);
    
    // 销毁二叉树
    void BinTreeDestroy(TNODE **root);
    
    // 输入二叉树
    void BinTreeInput(TNODE **root);
    
    // 先序遍历
    void BinTreePreorder(const TNODE *root);
    
    // 后序遍历
    void BinTreePostorder(const TNODE *root);
    
    // 中序遍历
    void BinTreeInorder(const TNODE *root);
    
    // 输出二叉树
    void BinTreeOutput(const TNODE *root);
    
    // 求结点数
    int BinTreeNumNode(const TNODE *root);
    
    // 叶子结点数
    int BinTreeNumLeaf(const TNODE *root);
    
    // 分枝结点数
    int BinTreeNumBranch(const TNODE *root);
    
    // 二叉树的深度
    int BinTreeDepth(const TNODE *root);
    
    #endif

### BinTree.c ###

#### 创建二叉树 ####

// 创建二叉树 
    void BinTreeCreate(TNODE **root) // 之所以要用二级指针 是因为会有更改一级指针的操作 
    {
        
    	*root = NULL; 
    }

#### 清空二叉树 ####

// 清空二叉树
    void BinTreeClear(TNODE **root)
    {
        
    	if (*root) 
    	{
        
    		BinTreeClear(&(*root)->lch); // 这里要注意的是传入的是(*root)->lch的地址，这样才是一个二级地址 
    		BinTreeClear(&(*root)->rch); // 这个是先释放左孩子，在释放右孩子 
    		free(*root);
    		*root = NULL;
    	}
    }

#### 销毁二叉树 ####

// 销毁二叉树
    void BinTreeDestroy(TNODE **root)
    {
        
    	BinTreeClear(root); 		// 注意传的是二级指针 
    }

#### 输入二叉树 ####

void BinTreeInput(TNODE **root)
    {
        
    //     if (*root != NULL && tag == 0)
    //     {
        
    //         BinTreeClear(root);
    //     }
    
        tag = 1;
        char element;
    
        scanf (" %c", &element);
        if (element == '#')
        {
        
            *root = NULL; 
        }
        else
        {
        
            *root = (TNODE *)malloc(sizeof(TNODE));
            (*root)->data = element;
            BinTreeInput(&(*root)->lch);
            BinTreeInput(&(*root)->rch);
        }    
    }

#### 先序遍历 ####

// 先序遍历
    void BinTreePreorder(const TNODE *root)
    {
        
    	if (root)
    	{
        
    		printf("%c", root->data);
    		BinTreePreorder(root->lch);
    		BinTreePreorder(root->rch);
    	}
    }

#### 后序遍历 ####

// 后序遍历
    void BinTreePostorder(const TNODE *root)
    {
        
    	if (root)
    	{
        		
    		BinTreePostorder(root->lch);
    		BinTreePostorder(root->rch);
    		printf("%c", root->data);
    	}
    }

#### 中序遍历 ####

// 中序遍历
    void BinTreeInorder(const TNODE *root)
    {
        
    	if (root)
    	{
        		
    		BinTreeInorder(root->lch);
    		printf("%c", root->data);
    		BinTreeInorder(root->rch);		
    	}
    }

#### 输出二叉树 ####

static void BinTreeOutput1(const TNODE *root, int layer)
    {
        
        if (root)
        {
        
            BinTreeOutput1(root->rch, layer + 1);
            for (int k = 1; k < layer; ++k)
            {
        
                printf("  ");
            }
            printf("%c\n", root->data);
            BinTreeOutput1(root->lch, layer + 1);
        }
    }
    
    void BinTreeOutput(const TNODE *root)
    {
        
        BinTreeOutput1(root, 1);
    }

#### 求结点数 ####

// 结点数
    int BinTreeNumNode(const TNODE *root)
    {
        
    	int num;
    	if (root)
    	{
        
    		num = 1 + BinTreeNumNode(root->lch) + BinTreeNumNode(root->rch);
    	}
    	else
    	{
        
    		num = 0;
    	}
    	return num;
    }

#### 叶子结点数 ####

// 叶子结点数
    int BinTreeNumLeaf(const TNODE *root)
    {
        
    	int num;
    	if (root)
    	{
        
    		if (root->lch == NULL && root->rch == NULL)
    		{
        
    			num = 1;
    		}
    		else
    		{
        
    			num = BinTreeNumLeaf(root->lch) + BinTreeNumLeaf(root->rch);
    		}
    	}
    	else
    	{
        
    		num = 0;		
    	}
    	return num;
    }

#### 分枝结点数 ####

// 分枝结点数
    int BinTreeNumBranch(const TNODE *root)
    {
        
    	int num = 0;
    	if (root)
    	{
        
    		if (root->lch != NULL || root->rch != NULL)
    		{
        
    			num = 1;
    		}		
    				
    		num += BinTreeNumBranch(root->lch) + BinTreeNumBranch(root->rch);		
    	}
    	else
    	{
        
    		num = 0;		
    	}
    	return num;
    }

#### 二叉树的深度 ####

// 深度
    int BinTreeDepth(const TNODE *root)
    {
        
    	int l, r;
    	if (root == NULL)
    	{
        
    		return 0;
    	}
    	else
    	{
        
    		l = BinTreeDepth(root->lch);
    		r = BinTreeDepth(root->rch);
    		return l > r ? l + 1 : r + 1;
    	}		
    }

### 测试程序 ###

int main(void)
    {
        
        int loop = 1, num;
        char ch;
        TNODE *root;
        BinTreeCreate(&root);
        while (loop)
        {
        
            printf("I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > ");
            scanf(" %ch", &ch);
            ch = toupper(ch);
            switch (ch)
            {
        
                case 'I':
                    printf("输入: ");
                    BinTreeInput(&root);
                    break;
                case 'O':
                    printf("输出:\n");
                    BinTreeOutput(root);
                    break;
                case 'C':
                    BinTreeClear(&root);
                    printf("清空\n");
                    break;
                case 'T':
                    printf("遍历\n1-先序 2-中序 3-后序 0-返回 > ");
                    scanf("%d", &num);
                    if (num == 1)
                    {
        
                        printf("先序遍历: ");
                        BinTreePreorder(root);
                        putchar('\n');
                    }
                    else if (num == 2)
                    {
        
                        printf("中序遍历: ");
                        BinTreeInorder(root);
                        putchar('\n');
                    }
                    else if (num == 3)
                    {
        
                        printf("后序遍历: ");
                        BinTreePostorder(root);
                        putchar('\n');
                    }
                    else if (num != 0)
                    {
        
                        printf("不正确的遍历选项!\n");
                    }
                    break;
                case 'D':
                    printf("数据\n1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > ");
                    scanf("%d", &num);
                    if (num == 1)
                    {
        
                        printf("结点数: %d\n", BinTreeNumNode(root));
                    }
                    else if (num == 2)
                    {
        
                        printf("叶子结点数: %d\n", BinTreeNumLeaf(root));
                    }
                    else if (num == 3)
                    {
        
                        printf("分枝结点数: %d\n", BinTreeNumBranch(root));
                    }
                    else if (num == 4)
                    {
        
                        printf("深度: %d\n", BinTreeDepth(root));
                    }
                    else if (num != 0)
                    {
        
                        printf("不正确的数据选项!\n");
                    }
                    break;
                case 'Q':
                    loop = 0;
                    break;
                default:
                    printf("不正确的操作选项!\n");
                    break;
            }
        }
        BinTreeDestroy(&root);
        return 0;
    }

**运行效果**

I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > x
    不正确的操作选项!
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > I
    输入: EIBJ##H###DF#A##G#C##
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o
    输出:
          C
        G
      D
          A
        F
    E
      I
          H
        B
          J
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
    遍历
    1-先序 2-中序 3-后序 0-返回 > 9
    不正确的遍历选项!
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T
    遍历
    1-先序 2-中序 3-后序 0-返回 > 0
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
    遍历
    1-先序 2-中序 3-后序 0-返回 > 1
    先序遍历: EIBJHDFAGC
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > T
    遍历
    1-先序 2-中序 3-后序 0-返回 > 2
    中序遍历: JBHIEFADGC
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > t
    遍历
    1-先序 2-中序 3-后序 0-返回 > 3
    后序遍历: JHBIAFCGDE
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 9
    不正确的数据选项!
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 0
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
    结点数: 10
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > D
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 2
    叶子结点数: 4
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 3
    分枝结点数: 6
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 4
    深度: 4
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > c
    清空
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > O
    输出:
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
    结点数: 0
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > i
    输入: ABD##E##CF##G##
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > o
    输出:
        G
      C
        F
    A
        E
      B
        D
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > d
    数据
    1-结点数 2-叶子结点数 3-分枝结点数 4-深度 0-返回 > 1
    结点数: 7
    I-输入 O-输出 C-清空 T-遍历 D-数据 Q-退出 > Q