| 【数据结构】树与二叉树（二）：树的表示C语言：树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法 | 您所在的位置：网站首页 › c语言二叉树图形输出 › 【数据结构】树与二叉树（二）：树的表示C语言：树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法 |
【数据结构】树与二叉树（二）：树的表示C语言：树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法
文章目录
5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语5.1.4 树的表示1．树形表示法2．嵌套集合表示法结构体创建树主函数
3．嵌套括号表示法结构体创建树嵌套括号表示法主函数
4．凹入表示法结构体创建树凹入表示法主函数
5.1 树的基本概念
5.1.1 树的定义
一棵树是结点的有限集合T：
若T非空，则：
有一个特别标出的结点，称作该树的根，记为root(T)；其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0)，其中T1, T2, …, Tm又都是树，称作root(T)的子树。
 T 空时为空树，记作root(T)=NULL。
5.1.2 森林的定义
一个森林是0棵或多棵不相交（非空）树的集合，通常是一个有序的集合。换句话说，森林由多个树组成，这些树之间没有交集，且可以按照一定的次序排列。在森林中，每棵树都是独立的，具有根节点和子树，树与树之间没有直接的连接关系。 森林是树的扩展概念，它是由多个树组成的集合。在计算机科学中，森林也被广泛应用于数据结构和算法设计中，特别是在图论和网络分析等领域。 参照前文：【数据结构】树与二叉树（一）：树（森林）的基本概念：父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度 5.1.4 树的表示 1．树形表示法树形表示法是一种图形化的表示方法，使用节点和边来表示树的结构。每个节点代表树中的一个元素，而边表示节点之间的关系。这种表示方法可以直观地展示树的层次结构和节点之间的连接关系。
嵌套集合表示法使用集合的嵌套结构来表示树：每个集合代表一个节点，而集合中的元素表示该节点的子节点。通过嵌套的方式，可以表示出树的层次结构。 tree = { 'value': 'A', 'children': [ { 'value': 'B', 'children': [] }, { 'value': 'C', 'children': [ { 'value': 'D', 'children': [] } ] } ] } 结构体 #include #include struct TreeNode { int value; struct TreeNode** children; int numChildren; }; 创建树 struct TreeNode* createTreeNode(int value, int numChildren) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->value = value; node->numChildren = numChildren; node->children = (struct TreeNode**)malloc(numChildren * sizeof(struct TreeNode*)); for (int i = 0; i struct TreeNode* root = createTreeNode(1, 2); struct TreeNode* node1 = createTreeNode(2, 0); struct TreeNode* node2 = createTreeNode(3, 1); struct TreeNode* node3 = createTreeNode(4, 0); root->children[0] = node1; root->children[1] = node2; node2->children[0] = node3; // 其他操作... return 0; } 3．嵌套括号表示法嵌套括号表示法使用括号来表示树的结构：每对括号代表一个节点，而括号内的内容表示该节点的子节点。通过嵌套括号的方式，可以清晰地表示树的层次结构和节点之间的关系。 tree_str = '((A (B C)) D)' 结构体 #include #include struct TreeNode { int value; struct TreeNode* left; struct TreeNode* right; }; 创建树 struct TreeNode* createTreeNode(int value) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->value = value; node->left = NULL; node->right = NULL; return node; } 嵌套括号表示法 // 根据嵌套括号表示法构建树 struct TreeNode* buildTreeFromParenthesis(char* treeStr, int* index) { struct TreeNode* node = NULL; int value = 0; int sign = 1; while (treeStr[*index] != '\0') { char c = treeStr[*index]; (*index)++; if (c == '(') { if (node == NULL) { node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->left = NULL; node->right = NULL; } node->left = buildTreeFromParenthesis(treeStr, index); } else if (c == ')') { return node; } else if (c == '-') { sign = -1; } else if (c >= '0' && c value *= sign; node->value = value; value = 0; sign = 1; } } return node; } 主函数 int main() { char* treeStr = "(1 (2 (4) (5)) (3 (6)))"; int index = 0; struct TreeNode* root = buildTreeFromParenthesis(treeStr, &index); // 其他操作... return 0; } 4．凹入表示法凹入表示法使用缩进来表示树的结构：每个节点都在上一级节点的下方，并且比上一级节点缩进一定的距离。通过缩进的方式，可以清晰地展示树的层次结构和节点之间的嵌套关系。 结构体 #include #include struct TreeNode { int value; struct TreeNode* firstChild; struct TreeNode* nextSibling; }; 创建树 struct TreeNode* createTreeNode(int value) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->value = value; node->firstChild = NULL; node->nextSibling = NULL; return node; } 凹入表示法 struct TreeNode* buildTreeFromIndented(char* treeStr, int* index, int level) { struct TreeNode* node = NULL; while (treeStr[*index] != '\0') { char c = treeStr[*index]; (*index)++; if (c == '\n') { continue; } if (c == ' ') { continue; } if (c == '-') { level++; continue; } int value = c - '0'; if (node == NULL) { node = createTreeNode(value); } else { struct TreeNode* child = createTreeNode(value); if (node->firstChild == NULL) { node->firstChild = child; } else { struct TreeNode* sibling = node->firstChild; while (sibling->nextSibling != NULL) { sibling = sibling->nextSibling; } sibling->nextSibling = child; } } int nextChar = treeStr[*index]; if (nextChar == '\n') { level--; } else if (nextChar == '-') { continue; } else { break; } } return node; } 主函数 int main() { char* treeStr = "1\n-2\n--4\n--5\n-3\n--6\n"; int index = 0; struct TreeNode* root = buildTreeFromIndented(treeStr, &index, 0); // 其他操作... return 0; } |
【本文地址】
公司简介
联系我们