数据结构03二叉树

二叉树

树的基本术语:

1**.** 结点： 树中的元素 及其子树

​ 2. 孩子**/**双亲： 一个结点的后继结点叫该结点的孩子，

​ 该结点叫 孩子的双亲结点。

​ 3. 结点的度：该结点分支的数量

​ 4. 叶子： 度为0的结点，

​ 5**.** 结点的层次： 从根到该结点的层数**(根的层次为1)****；**

​ 6. 树的高度**(深度)****：树中结点层次的最大值**

![在这里插入图片描述](https://i-blog.csdnimg.cn/di
ect/950a3d99e4bf44dbb5e9975d94e21205.png)

/*************************************************************************
  > File Name:    tree.c
  > Author:       SunTeng
  > Description:  
  > Created Time: 2025年08月04日 星期一 10时59分01秒
 ************************************************************************/

#include "head.h"

typedef struct  node
{  
    int data;
    struct node *left;
    struct node *right;
}TREE;

// 创建二叉树的独立节点
TREE* createNode(int num)
{
    TREE* pNew = (TREE*)malloc(sizeof(TREE));
    if (NULL == pNew)
    {
        perror("createNode malloc fail");
        return NULL;
    }

    pNew->data = num;
    pNew->left = NULL;
    pNew->right = NULL;

    return pNew;
}

TREE* insertNode(TREE* root, int num)
{
    // 1、创建一个新节点
    TREE* pNew = createNode(num);
    if (NULL == pNew)
    {
        return root;
    }

    // 2、如果原树无任何节点
    if (NULL == root)
    {
        return pNew;
    }

    // 3、如果存在节点，则执行编译，选择插入位置
    // ①  若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
    // ②  它的右子树非空，则右子树上所有结点的值均大于根结点的值；
    // ③  左、右子树本身又各是一棵二叉排序树。
    TREE* pCur = root;
    while(pCur != NULL)
    {

        //当前值小于根，则数据插入在左子树中
        if (pNew->data < pCur->data)
        {
            // 如果左节点为空，也就是没有子节点了，
            // 那么新节点就插入在这个位置
            if (NULL == pCur->left)
            {
                pCur->left = pNew;
                return root;
            }

            pCur = pCur->left;
        }
        //当前值大于根，则数据插入在右子树中
        else if (pNew->data > pCur->data)
        {
            if (NULL == pCur->right)
            {
                // 当前节点无右叶节点，直接插入
                pCur->right = pNew;
                return root;
            }

            pCur = pCur->right;
        }
        // 如果待查入数据与当前节点数据相等，不进行插入操作
        else // pNew->data == pCur->data
        {
            return root;
        }
    }

    return root;
}

// 前续遍历输出二叉树 --> 根左右
void before_order(TREE* root)
{
    if (root == NULL)
    {
        return;
    }

    // 将所有节点都当成其对应子树的根节点来看待
    printf("%d ", root->data);
    before_order(root->left);
    before_order(root->right);
}

// 中续遍历输出二叉树 --> 左根右
void middle_order(TREE* root)
{
    if (root == NULL)
    {
        return;
    }

    middle_order(root->left);
    printf("%d ", root->data);
    middle_order(root->right);
}

// 后续遍历输出二叉树 --> 左右根
void after_order(TREE* root)
{
    if (root == NULL)
    {
        return;
    }

    after_order(root->left);
    after_order(root->right);
    printf("%d ", root->data);
}

// 根据值来查找节点，并且将找到的节点指针返回
TREE* findNode(TREE* root, int num)
{
    if (NULL == root)
    {
        return NULL;
    }

    TREE* pCur = root;
    while(pCur != NULL)
    {
        // 查找左子树
        if (num < pCur->data)
        {
            pCur = pCur->left;
        }
        // 查找右子树
        else if (num > pCur->data)
        {
            pCur = pCur->right;
        }
        else // num == pCur->data
        {
            return pCur;
        }
    }

    return NULL;
}

int main(int argc,char *argv[])
{
    TREE* root = NULL;

    int arr[] = {44, 17, 66, 49, 35, 22, 111, 33};

    for (int i = 0; i < 8; i++)
    {
        root = insertNode(root, arr[i]);
    }


    printf("前序遍历：");
    before_order(root);
    printf("\n");

    printf("中序遍历：");
    middle_order(root);
    printf("\n");

    printf("后序遍历：");
    after_order(root);
    printf("\n");


    TREE* ptr = findNode(root, 8);
    if (ptr == NULL)
    {
        printf("未找到!\n");
    }
    else
    {
        printf("%p\n", ptr);
    }

    return 0;
}