【学习笔记】二叉树（c语言）

显示全部楼层

1.树

1.1树的性质

树是一种非线性的数据结构，他是由n（n >= 0）个有限结点组成一个具有层次关系的集合。把他叫做树是因为他看起来向一颗倒挂的树，也就是说他是根在上，叶在下的。
1.2树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点
非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；
1.3树的性质

树有一个特殊的结点叫做根结点，根节点没有前驱结点

除根结点外，其余结点被分成M（M>0）个互不相交的集合T1\T2.....\Tm,其中每个集合Ti（1val = x; newnode->left = NULL; newnode->right = NULL;}[/code] 3.2.2前序遍历

typedef char BTDataType;
typedef struct BTNode {
        BTDataType val;
        struct BTNode* left;
        struct BTNode* right;
}BTNode;
复制代码

3.2.3中序遍历

BTNode* CreatTreeNode(BTDataType x)                                        //创建二叉树结点
{
        BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
        assert(newnode);
        newnode->val = x;
        newnode->left = NULL;
        newnode->right = NULL;
}
复制代码

3.2.4后序遍历

void PrevOrder(BTNode* root)                                                //前序遍历
{
        if (root == NULL)                                //遇到结点为NULL返回
        {
                printf("NULL ");
                return;
        }
        printf("%c ", root->val);                //打印根数据
        PrevOrder(root->left);                        //令左孩子为根进行前序遍历
        PrevOrder(root->right);                        //令右孩子为根进行前序遍历
}
复制代码

3.2.5二叉树结点个数

void InOrder(BTNode* root)                                                        //中序遍历
{
        if (root == NULL)                                //遇到结点为NULL返回
        {
                printf("NULL ");
                return;
        }
        InOrder(root->left);                        //打印根数据
        printf("%c ", root->val);                //令左孩子为根进行中序遍历
        InOrder(root->right);                        //令右孩子为根进行中序遍历
}
复制代码

3.2.6二叉树叶结点个数

void PostOrder(BTNode* root)                                                //后序遍历
{
        if (root == NULL)                                //遇到结点为NULL返回
        {
                printf("NULL ");
                return;
        }
        PostOrder(root->left);                        //令左孩子为根进行后序遍历        
        PostOrder(root->right);                        //令右孩子为根进行后序遍历
        printf("%c ", root->val);                //打印根数据
}
复制代码

3.2.7第k层结点个数

int TreeSize(BTNode* root)                                                        //结点个数
{
        if (root == NULL)
        {
                return 0;
        }
        return TreeSize(root->left) + TreeSize(root->right) + 1;
        //优化
        //return root == NULL ? 0 : TreeSize(root->left)+TreeSize(root->right)+1;
}
复制代码

3.2.8二叉树最大深度

int BinaryTreeLeafSize(BTNode* root)                                //叶结点个数
{
        if (root == NULL)
        {
                return 0;
        }
        if (root->left == NULL && root->right == NULL)
        {
                return 1;
        }
        
        return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
复制代码

3.2.9二叉树查找

int BinaryTreeLevelKSize(BTNode* root, int k)                //第k层结点个数
{
        if (root == NULL)
        {
                return 0;
        }
        if (k == 1)
        {
                return 1;
        }
        return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
复制代码

3.3二叉树头文件

文件：“Binary_Tree.h”

int MaxDepth(BTNode* root)                                //二叉树最大深度
{
        if (root == NULL)
        {
                return 0;
        }
        int leftdepth = MaxDepth(root->left);
        int rightdepth = MaxDepth(root->right);
        return leftdepth > rightdepth ? leftdepth+1 : rightdepth+1;
}
复制代码

3.4二叉树功能测试

文件：“test.c”

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)        //二叉树查找
{
        if (root == NULL)
        {
                return NULL;
        }
        if (root->val == x)
        {
                return root;
        }
        BTNode* left = BinaryTreeFind(root->left, x);
        if (left)
        {
                return left;
        }
        BTNode* right = BinaryTreeFind(root->right, x);
        if (right)
        {
                return right;
        }
        return NULL;
}
复制代码

✨写在最后
⏱笔记时间：2022_01_11

来源：https://blog.caogenba.net/Zero__two_/article/details/122432444
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

工作时间

工作时间

【学习笔记】二叉树（c语言）

火星云矿 | 预约S19Pro，享500抵1000！