Tree | 一般树 —— 概念、建立与凹进输出

最新推荐文章于 2023-02-19 19:19:16 发布

贝贝今天AC了吗

最新推荐文章于 2023-02-19 19:19:16 发布

阅读量1.7k

点赞数 4

分类专栏： ★ 数据结构文章标签：树数据结构 c语言建立树输出树

本文链接： https://blog.csdn.net/weixin_43787043/article/details/103955229

版权

★ 数据结构专栏收录该内容

20 篇文章 10 订阅

订阅专栏

一、树的基本概念

1、树的结构：

2、树一些名词解释：

二、一般树的实现

1、树的结构

2、树的建立

3、树的输出

打印某个节点的函数如下：

整个树的打印递归实现：

End

一、树的基本概念

树是一种数据结构，由n(n>=0)个有限结点组成一个有层次关系的集合。

由于形状像一颗倒立的树而得名。

当n=0时称为空树，非空树的特征如下：

（1）有且仅有一个根结点R（root）

（2）n > 1时，其余结点可分为m( m > 0 )个互不相交的有限集合，其中每个集合本身又是一棵树，称为原树的子树（Subtree）。

1、树的结构：

可以递归地理解一棵树：

树由一个根节点生成，其下均为它的子树。子树也是其本身为加上其子树生成...

从上往下看，一条边上连接了两个节点，上面的为前驱节点，下面的为后继节点。我们称前驱节点为后继节点的父亲节点，后继节点为前驱节点的孩子节点。

2、树一些名词解释：

术语	解释
根节点（Root）	一棵树最顶端的节点
叶子节点（leaf）	没有孩子节点
边（Edge）	两个节点之间的连接
路径（Path）	连接某一节点到另一节点边的序列
节点高度（Height）	从该节点到叶子节点的最长路径的边数
节点层级（Level）	从该一结点到根节点路径的边数+1
节点深度（Depth）	从根节点到该节点路径的边数
节点的度（Degree）	该节点孩子节点的个数

图解：

Edge、Root、Leaf

Path

Height

需要注意的是叶子节点的高度为0，树的高度就是根节点的高度。

Depth

需要注意的是根节点的深度为0。

Level

二、一般树的实现

1、树的结构

树的种类有很多，对于一般的树是通过儿子兄弟法构造的。

那么这种表示方法下，树节点的结构应该是这样的：

每个节点有三个域 —— 数据域，左儿子指针域，右兄弟指针域

树的整体结构图如下图所示：

左边为树的宏观结构，右边是具体的数据储存方式。

对应的代码实现：

树的节点定义 ——

typedef struct TreeNode {
    int data;
    struct TreeNode * FirstChild;
    struct TreeNode * NextSibling;
} *TREE, tree;

2、树的建立

输入一棵树的层序结构，如：

可以想象，我们的树应该是长这样：

可以通过利用栈和队列实现对一般树的建立。

我们同时需要在树节点的结构中添加一个新的域：记录节点深度depth。

话不多说，直接上代码。配合注释+自己画画图理解一下，应该很好看懂：

/* 传入参数为：
 * 层序输入的字符串
 * 根节点T(实际上没有存数据，深度已设为零) */
TREE BuildTree (char s[], TREE root) {
    queue <TREE> Q;
    stack <TREE> S;

    S.push(root);
    int depth = 0;  //用于更新当前遍历到的深度

    /* 将字母改成树的节点
     * 并依次将每个节点入队 */
    for(int i = 0; s[i] != '\0'; i++) {
        switch (s[i]) {
            case ',':
                break;
            case '(':
                depth++;
                break;
            case ')':
                depth--;
                break;
            default:   //只有可能为节点字母了
                TREE temp = (TREE)malloc(sizeof(tree));  //申请一个节点
                temp->c = s[i];
                temp->depth = depth;  //记录节点的深度
                temp->FirstChild = temp->NextSibling =NULL;
                Q.push(temp);  //节点入队
        }
    }
    /* 利用栈建树 
     * 注意：最开始栈内已经加入一个元素root,其深度为0
     * 其他节点已经在队列中，深度 >= 1 */
    while(!Q.empty()) {
        //依次将队头节点与栈顶结点比较：
        if(Q.front()->depth > S.top()->depth) {
            S.top()->FirstChild = Q.front();  //队头挂在栈顶的左儿子
            S.push(Q.front());  //队头入栈
            Q.pop();  //出队
        }
        else if(Q.front()->depth == S.top()->depth) {
            S.top()->NextSibling = Q.front();  //队头挂在栈顶的右兄弟
            S.push(Q.front());  //队头入栈
            Q.pop();  //出队
        }
        else {
            //出栈，一直到栈顶节点深度不小于队头节点
            while (Q.front()->depth < S.top()->depth) {
                S.pop();
            }
        }
    }
    return root;  
    /* root是传入的参数
     * 通过此函数 已经将待建立的树
     * 完整地挂在了root的左儿子上 */
}

3、树的输出

通过以上输入建立好树后，要求输出树的凹进结构，如图，左边绿色部分为输入，黑色部分为输出：

可以看到，这样打印一棵树是可以递归地完成的：

对于一棵树，先打印根节点，再依次打印各个儿子（子树），子树也是这样操作。

比如说这棵树，先打印根节点A，再完成了儿子B的打印，再完成了儿子C的打印，最后完成了儿子D的打印。

那么输出时，每个节点占一行，且要根据其深度加上凹进。

打印某个节点的函数如下：

/* 传入树的某个节点 */
void printLine(TREE T) {
    for (int i = 0; i < T->depth - 1; i++) {
        printf("    ");  //多一层则多四个空格凹进
    }
    printf("%c\n", T->c);
}

整个树的打印递归实现：

/* 传入树的根节点 */
void printTree(TREE root) {
    
    //递归的终点，空树不打印
    if (!root) {
        return;
    }
    
    //打印根节点
    printLine(root);
    
    /* 依次打印每个子树 */
    TREE p = root->FirstChild;
    while(p) {
        printTree(p);
        p = p->NextSibling;
    }
}

完整代码如下：

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>

#define MAX 200

using namespace std;

typedef struct TreeNode {
    char c;
    int depth;
    struct TreeNode * FirstChild;
    struct TreeNode * NextSibling;
} *TREE, tree;


/* 传入参数为：
 * 层序输入的字符串
 * 根节点T(实际上没有存数据，深度已设为零) */
TREE BuildTree (char s[], TREE root) {
    queue <TREE> Q;
    stack <TREE> S;

    S.push(root);
    int depth = 0;  //用于更新当前遍历到的深度

    /* 将字母改成树的节点
     * 并依次将每个节点入队 */
    for(int i = 0; s[i] != '\0'; i++) {
        switch (s[i]) {
            case ',':
                break;
            case '(':
                depth++;
                break;
            case ')':
                depth--;
                break;
            default:   //只有可能为节点字母了
                TREE temp = (TREE)malloc(sizeof(tree));  //申请一个节点
                temp->c = s[i];
                temp->depth = depth;  //记录节点的深度
                temp->FirstChild = temp->NextSibling =NULL;
                Q.push(temp);  //节点入队
        }
    }
    /* 利用栈建树
     * 注意：最开始栈内已经加入一个元素root,其深度为0
     * 其他节点已经在队列中，深度 >= 1 */
    while(!Q.empty()) {
        //依次将队头节点与栈顶结点比较：
        if(Q.front()->depth > S.top()->depth) {
            S.top()->FirstChild = Q.front();  //队头挂在栈顶的左儿子
            S.push(Q.front());  //队头入栈
            Q.pop();  //出队
        }
        else if(Q.front()->depth == S.top()->depth) {
            S.top()->NextSibling = Q.front();  //队头挂在栈顶的右兄弟
            S.push(Q.front());  //队头入栈
            Q.pop();  //出队
        }
        else {
            //出栈，一直到栈顶节点深度不小于队头节点
            while (Q.front()->depth < S.top()->depth) {
                S.pop();
            }
        }
    }
    return root;
    /* root是传入的参数
     * 通过此函数 已经将待建立的树
     * 完整地挂在了root的左儿子上 */
}

/* 传入树的某个节点 */
void printLine(TREE T) {
    for (int i = 0; i < T->depth - 1; i++) {
        printf("    ");  //多一层则多四个空格凹进
    }
    printf("%c\n", T->c);
}

/* 传入树的根节点 */
void printTree(TREE root) {

    //递归的终点，空树不打印
    if (!root) {
        return;
    }

    //打印根节点
    printLine(root);

    /* 依次打印每个子树 */
    TREE p = root->FirstChild;
    while(p) {
        printTree(p);
        p = p->NextSibling;
    }
}

int main () {
    char s[MAX];
    gets(s);

    TREE T = (TREE) malloc(sizeof(tree));
    T->depth = 0;
    T->FirstChild = T->NextSibling = NULL;

    //建树
    TREE root = BuildTree(s, T)->FirstChild;
    //输出树
    printTree(root);
    return 0;
}