【数据结构】——树

速通回忆

下面是一个二叉树的演示：包括二叉树的类型构造，二叉树存放一个数值，二叉树的遍历（先序遍历、中序遍历、后序遍历）

你可以选择直接看这个演示代码回忆之前学过的内容，或者看下面的介绍进行二次学习

#include "stdio.h"
#include "stdlib.h"

/* 树的元素结构体，结点元素、左子树、右子树 */
typedef struct tree_n{
    int num;
    struct tree_n *left;
    struct tree_n *right;
} tree_node;

/* 树，根结点 */
typedef struct{
    tree_node *root;
}tree;

/* 树的末尾一个结点 */
void Tree_Insert(tree *t, int nums){
    /* 分配缓存空间 */
    tree_node *node_temp = (tree_node *)malloc(sizeof(tree_node));
    node_temp->num = nums;
    node_temp->left = NULL;
    node_temp->right = NULL;
    
    /* 当树为空的时候 */
    if(t->root == NULL){
        t->root = node_temp;
        return ;
    }
    /* 不为空的时候 */
    tree_node *tree_temp = t->root;
    while(tree_temp){
        /* 比结点小，存放在左子树 */
        if(nums < tree_temp->num){
            /* 当左字数为空的时候 */
            if(tree_temp->left == NULL){
                tree_temp->left = node_temp;
                return ;
            }else{
                tree_temp = tree_temp->left;
            } 
        }
        /*当数值大于等于结点的时候，存放左字数*/
        else{
            /* 当右字数为空的时候 */
            if(tree_temp->right == NULL){
                tree_temp->right = node_temp;
                return ;
            }else{
                tree_temp = tree_temp->right;
            } 
        }
    }
}

/* 中序遍历显示二叉树 */
void TreeShow_infix(tree_node* node){
    if(node){
        TreeShow_infix(node->left);
        printf("%d\t", node->num);
        TreeShow_infix(node->right);
    }
}

/* 先序遍历显示二叉树 */
void TreeShow_pre(tree_node* node){
    if(node){
        printf("%d\t", node->num);
        TreeShow_pre(node->left);
        TreeShow_pre(node->right);
    }
}

/* 后序遍历显示二叉树 */
void TreeShow_epilogue(tree_node* node){
    if(node){
        TreeShow_epilogue(node->left);
        TreeShow_epilogue(node->right);
        printf("%d\t", node->num);
    }
}

int main(){
    /* 创建一棵树 */
    tree tree_temp;
    tree_temp.root = NULL;

    /* 插入一些结点 */
    Tree_Insert(&tree_temp, 5);
    Tree_Insert(&tree_temp, 3);
    Tree_Insert(&tree_temp, 7);
    Tree_Insert(&tree_temp, 2);
    Tree_Insert(&tree_temp, 4);
    Tree_Insert(&tree_temp, 6);
    Tree_Insert(&tree_temp, 8);

    /* 显示树的结构 */
    printf("中序遍历的树的结构:\n");
    TreeShow_infix(tree_temp.root);
    printf("\n\n");

    printf("先序遍历的树的结构:\n");
    TreeShow_pre(tree_temp.root);
    printf("\n\n");

    printf("后序遍历的树的结构:\n");
    TreeShow_epilogue(tree_temp.root);
    printf("\n\n");

    return 0;
}

树的概念

树属于非线性数据结构结构的一种，树的概念是非常多的，下面一一举例。

没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构

树的定义：n个节点组成的有限集合。n=0，空树；n>0,1个根节点，m个互不相交的有限集，每个子集为根的子树。

基本术语

• 节点的度：树中某个节点的子树（子节点）的个数

• 树的度：树中各节点的度的最大值

• 分支节点：度不为0的节点

• 叶子节点：度为0的节点

• 路径：i->j

• 路径：路径经过的节点数-1

• 孩子节点：节点的后继节点

• 双亲（父母）节点；该节点为其孩子节点的双亲节点

• 兄弟节点：同双亲节点的节点

• 子孙节点：节点的子树的所有节点

• 祖先节点：从树的根节点到该节点路径上的点

• 节点层次：根节点为第一层，以此类推

• 树的高度：树中节点的最大层次

• 有序树：树中节点按照次序从左向右排序

• 森林：互不相交的树的集合

树的性值

• 树的节点树为所有节点的度+1（根节点）

• 度为m的树中第i层最多有m^(i-1)个节点

• 高度为h的m层树至多(m^h-1)/(m-1)个节点

• 具有n个节点的m层树的最小高度为logm( n(m-1) + 1 )  向上取整

二叉树

二叉树是n个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成

每一个结点中最多拥有一个左结点和一个右结点，并没有多余的结点，这是很明显的二叉树的特征

二叉树特点

• 每个结点最多有两棵树

• 次序不能随意颠倒

• 要区分左结点和右结点

二叉树性质

• 二叉树第i层上的结点数目最多为 2的(i-1)次方个节点

• 深度为k的二叉树至多有2的k次方-1个结点

• 包含n个结点的二叉树的高度至少为log2 (n+1)、

• 在任意一颗二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

特殊的二叉树

• 斜树：所有结点都只有左结点或右结点，分别称为左斜树、右斜树

• 满二叉树：所有的结点都有左结点和右结点，且所有的叶子都在同一层

  • 非叶子结点的度一定为2

  • 叶子结点只能出现在最下面

  • 同一深度，满二叉树是二叉树类中结点树最多，叶子数最多的

• 完全二叉树：对具有n个结点的二叉树按层编号，如果i结点与同样深度的满二叉树的i结点编号完全相同

二叉树结点设计

二叉树其实就一个每个结点都只允许有左右两个孩子的树

一颗完全二叉树，需要设计：

• 结点元素

• 左孩子结点指针

• 右孩子结点指针

• 父结点

//树的结点
typedef struct node{
    int data;
    struct node* left;
    struct node* right;
} Node;
  
//树根
typedef struct {
    Node* root;
} Tree;

二叉树的创建

• 我们创建一个空的结点再进行连接，首先将这个空的结点中的date域赋予数据；

• 再判断tree中是否是一个空树，如果为空，只需要将整个根指向这一个结点即可；

• 如果不为空，再进行判断：

  • 输入的数据是否大于或者小于当前比对的结点数据，根据其大小进行相应的排列

//创建树--插入数据
void insert(Tree* tree, int value){
    //创建一个节点，让左右指针全部指向空，数据为value
    Node* node=(Node*)malloc(sizeof(Node));
    node->data = value;
    node->left = NULL;
    node->right = NULL;
  
    //判断树是不是空树，如果是，直接让树根指向这一个结点即可
    if (tree->root == NULL){
        tree->root = node;
    } else {//不是空树
        Node* temp = tree->root;//从树根开始
        while (temp != NULL){
            if (value < temp->data){ //小于就进左儿子
                if (temp->left == NULL){
                    temp->left = node;
                    return;
                } else {//继续往下搜寻
                    temp = temp->left;
                }
            } else { //否则进右儿子
                if (temp->right == NULL){
                    temp->right = node;
                    return;
                }
                else {//继续往下搜寻
                    temp = temp->right;
                }
            }
        }
    }
    return;
}

遍历，显示树

遍历分为三种方式：中序遍历、先序遍历、后序遍历，这个前后顺序指的是结点相比其左右子结点排序中的顺序

先序遍历：根左右
中序遍历：左根右
后序遍历：左右根

用C实现三种遍历的代码虽然只有几行，但是一定要搞清楚其中函数回调的意义!!!

先序遍历二叉树

//树的先序遍历 Preorder traversal
void preorder(Node* node){
    if (node != NULL)
    {
        printf("%d ",node->data);
        inorder(node->left);
        inorder(node->right);
    }
}

中序遍历二叉树

//树的中序遍历 In-order traversal
void inorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
    }
}

后序遍历二叉树

//树的后序遍历 Post-order traversal
void postorder(Node* node){
    if (node != NULL)
    {
        inorder(node->left);
        inorder(node->right);
        printf("%d ",node->data);
    }
}

二叉树森林互相转换

树转换成二叉树

分为3步：

• 加线：在兄弟（即同一层之间的孩子）之间加一连线

• 抹线：对每个结点，除了其第一个孩子外，除去其与其余孩子之间的连线

• 旋转：以树的根结点为轴心，将整树顺时针转45°

旋转之后，结点的左子树还是左子树，最近的兄弟结点变为右子树
注意：树转换成二叉树其右子树一定为空

二叉树转换成树

同样分为3步：

• 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来

• 抹线：抹掉原二叉树中双亲与右孩子之间的连线

• 调整：将结点按层次排列，形成树结构

森林转换成二叉树

• 将各棵树分别转换成二叉树

• 将每棵树的根结点用线相连,以第一棵树根结点为二叉树的根

• 再以根结点为轴心，顺时针旋转，构成二叉树型结构

二叉树转换成森林

• 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

• 还原：将孤立的二叉树还原成树（二叉树→树）