devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C语言写二叉树_创建一颗二叉树的代码

作者：不正经 | 2024-05-03 20:22:37

赞

踩

创建一颗二叉树的代码

C语言写二叉树

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

结点类（TNode.h）

#ifndef _TNode_h_
#define _TNode_h_

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

#endif

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

二叉树类（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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

BinTree.c

创建二叉树

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

  • 1
  • 2
  • 3
  • 4
  • 5

清空二叉树

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

销毁二叉树

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

  • 1
  • 2
  • 3
  • 4
  • 5

输入二叉树


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);
    }    
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

先序遍历

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

后序遍历

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

中序遍历

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

输出二叉树

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);
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

求结点数

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

叶子结点数

// 叶子结点数
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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

分枝结点数

// 分枝结点数
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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

二叉树的深度

// 深度
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;
	}		
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

测试程序

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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86

运行效果

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/531361
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号