🪴qql1's digital garden

树

4分钟阅读

梗概1:

树的相关概念:

空树:

  1. 定义: 0个结点

子树

  1. 定义: 子树的根只有一个直接前驱

森林

child::森林

结点的度

  1. 定义: 结点的分叉数量

结点的分类:

根结点:

  1. 定义: 树最底层的结点

双亲结点:

  1. 该结点所连接的上一层结点

叶结点/终结结点:

  1. 定义: 度为0的结点

分支结点:

  1. 定义: 度不为0的结点

结点的层次

  1. 从根结点开始数1, 每个结点步进1

结点的层序编号:

  1. 编号顺序:
    1. 从左到右, 再到下一层

树的度

  1. 用树中最大的结点度作为树的度

树的高度(深度)

  1. 树中最大层次

特殊的树:

树,森林,二叉树的相互转换

child::树,森林,二叉树的相互转换

操作:

child::

树的操作

基础

遍历:

删除节点

child::

删除树节点

方法之一

  • 遍历树的时候，缓存其当前节点的父节点
  • 从父节点中移除当前节点

方法之一

  • 遍历树的同时复制一棵树，对于需要删除的节点，则不复制
  • 缺点：需要两倍的空间
  • 优点：方便快捷
指向原始笔记的链接

克隆

child::

克隆树

  • child::

    广度优先克隆树

    在 JavaScript 中，可以使用广度优先搜索（BFS）来实现树的深拷贝。下面是一个实现的示例：

    class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    
    addChild(child) {
        this.children.push(child);
    }
}
function deepCopyTree(root) {
    if (!root) {
        return null; // 如果根节点为空，返回 null
    }
    // 创建一个队列用于广度优先遍历
    const queue = [];
    const clonedRoot = new TreeNode(root.value); // 复制根节点
    queue.push({ original: root, clone: clonedRoot }); // 将原始节点和克隆节点放入队列
    while (queue.length > 0) {
        const { original, clone } = queue.shift(); // 弹出队列中的第一个元素
        // 遍历当前节点的子节点
        for (const child of original.children) {
            const clonedChild = new TreeNode(child.value); // 复制子节点
            clone.children.push(clonedChild); // 将复制的子节点添加到克隆节点的子节点中
            queue.push({ original: child, clone: clonedChild }); // 将子节点的原始和克隆放入队列
        }
    }
    return clonedRoot; // 返回深拷贝的树的根节点
}
// 示例用法
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const child3 = new TreeNode(4);
root.addChild(child1);
root.addChild(child2);
child1.addChild(child3);
const clonedTree = deepCopyTree(root);
// 打印结果以验证深拷贝
console.log(clonedTree); // 输出克隆的树结构
    指向原始笔记的链接
  • child::

    深度优先克隆树

    伪代码

    function cloneTree(tree){
    function dfs(node){
        let cloneNode = clone(node)
        cloneNode.children= tree.children.map(v=>dfs(v))
        return cloneNode
    }
    return dfs(tree)
}
    指向原始笔记的链接
指向原始笔记的链接

指向原始笔记的链接

树的存储结构

数据维度

  • 至少需要二维: id和子结点

主要有三种:

  1. 双亲表示法
  2. 孩子表示法
  3. 孩子兄弟表示法

普通树在c语言中的实现

双亲表示法

梗概:

  1. 用线性表存储树的结点
  2. 每个结点存储三部分信息
    1. 该结点在线性表中的位置(下标)
      1. 表示某一个结点
    2. 数据域 2. 存储该结点的数据
    3. 双亲域 3. 存储双亲结点的位置(下标)

实现:

#define TNode_MAXNUM 128
typedef struct{
	TdataType data;
	int parent;
}TNode;
typedef struct{
	TNode tree[TNode_MAXNUM];
	int nodenum;
}ParentTree;

孩子表示法

梗概:

  1. 用一个线性表存储每个结点
  2. 每个结点存储三个信息
    1. 当前结点在线性表中的位置
      1. 表示对应结点
    2. 数据域
      1. 存储当前结点的数据
    3. 孩子链表头指针域
      1. 存储一个单链表的头指针
        1. 该单链表每个链表结点存储两个信息
          1. 树结点在线性表中的位置
            1. 表示对应树结点
          2. 下一个链表结点指针域

实现:

typedef struct ChildNode{
	int Child;
	struct ChildNode *next;
}ChildNode;
typedef struct{
	TdataType data;
	ChildNode *FirstChild;
}TNode;
typedef struct{
	TNode nodes[TNode_MAXNUM];
	int root;
	int num;
}ChildTree;

孩子兄弟表示法

梗概:

  1. 用二叉链表存储每个树结点
  2. 每个链结点存储三部分信息
    1. 首孩子域(名为FirstChild)
      1. 存储首孩子(从左往右)树结点在二叉链表中的位置
    2. 数据域
    3. 兄弟域(名为NextSibling)
      1. 存储右兄弟树结点在二叉链表中的位置

实现:

typedef struct CSNode{
	TDataType data;
	struct CSNode* FirstChild;
	struct CSNode* NextSibling;	
}CSNode, *CSTree;

关系图谱

反向链接