数据结构-树的相关问题

问：子树是否可以有交集

==注意：树形结构中，子树之间不能有交集，否则就不是树形结构==

• 子树不相交
• 除了根结点，每个结点有且仅有一个父节点
• 一个N个结点的树有N-1条边

树的表示方法：

假设说明树的度为N->最大的节点的度为N

struct TreeNode
{
    int data;
    struct TreeNode* subs[N];
};
//subs是指针数组，是数组
存在的问题：
    1.可能会存在不少空间浪费 ->如果最大的度为N 其它都为0，1，2.. N 会存在不少空间的浪费
    2.万一没有限定树的度为多少呢？

未知树的度->使用顺序表

typedef struct TreeNode* SLDataTye;//存放的数据是二叉树结构体
struct TreeNode
{
    int data;
    SeqList s; //s是顺序表结构体里面含一个指针,SLDataType* a ->a是一个数组，SLDataType展开后，a是二级指针,a指向的是存放一级指针SLDataType的数组
};
 使用顺序表，如果空间不够就可以扩容

双亲表示法

struct TreeNode
{
    int parent;//存父亲结点的下标
    int data;//存该结点的数据
};
struct TreeNode arr[10]；//arr是结构体数组
    
用数组存放父亲结点的下标

三叉链

// 三叉链
typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}；

最优表示方法：左孩子右兄弟表示法

typedef int DataType;
struct Node
{
    struct Node* firstChil; // 永远指向它的第一个孩子结点
    struct Node* NextBrother; // 指向孩子右边的兄弟
    DataType data; // 结点中的数据域
};

如何通过这个方法找到结点的孩子：

通过fristchirld找到第一个孩子，通过第一个孩子的Nextbrother，不断找下一个NextBrother，当Nextbrother为NULL时结束

经典的树形结构：文件系统

前序后序中序配合构成树 ：结论

前序+中序 可以重建树

后序+中序 可以重建树

前序+后序 不可以重建树