C语言写二叉树

GeekLiHua

发布于 2025-01-21 15:11:36

4610

文章被收录于专栏：JavaJava

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-09-14，如有侵权请联系 cloudcommunity@tencent.com 删除

数据