【数据结构与算法】第23篇：树、森林与二叉树的转换

一、树的存储结构1.1 双亲表示法每个节点存储数据和父节点下标适合找父节点的场景。c#define MAX_SIZE 100 typedef struct { int data; int parent; // 父节点下标 } PNode; typedef struct { PNode nodes[MAX_SIZE]; int root; // 根节点下标 int size; } PTree;缺点找孩子需要遍历整个数组。1.2 孩子表示法每个节点用链表存储所有孩子适合找孩子的场景。ctypedef struct ChildNode { int childIndex; struct ChildNode *next; } ChildNode; typedef struct { int data; ChildNode *firstChild; } CNode;缺点找父节点不方便。1.3 孩子兄弟表示法重点每个节点存储第一个孩子、右兄弟。ctypedef struct CSNode { int data; struct CSNode *firstChild; // 第一个孩子 struct CSNode *nextSibling; // 右兄弟 } CSNode, *CSTree;这种表示法把树变成了二叉树——左指针指向孩子右指针指向兄弟。画个图text原树 孩子兄弟表示法 A A / | \ / B C D B | \ E C \ D / E二、树与二叉树的转换2.1 转换规则左孩子右兄弟原树关系转换后二叉树关系第一个孩子左孩子下一个兄弟右孩子口诀左孩子右兄弟。2.2 手动转换示例原树textA / | \ B C D / \ E F转换步骤A的第一个孩子是B → A的左孩子是BB的兄弟是C → B的右孩子是CC的兄弟是D → C的右孩子是DC的第一个孩子是E → C的左孩子是EE的兄弟是F → E的右孩子是F转换后的二叉树textA / B \ C / \ E D \ F2.3 转换后的特点根节点没有右孩子因为根没有兄弟左孩子是原树的第一个孩子右孩子是原树的下一个兄弟2.4 代码实现c#include stdio.h #include stdlib.h // 树节点孩子兄弟表示法 typedef struct CSNode { char data; struct CSNode *firstChild; struct CSNode *nextSibling; } CSNode, *CSTree; // 创建节点 CSNode* createNode(char data) { CSNode *node (CSNode*)malloc(sizeof(CSNode)); node-data data; node-firstChild NULL; node-nextSibling NULL; return node; } // 手动构建一棵树 // A // / | \ // B C D // / \ // E F CSTree buildTree() { CSNode *A createNode(A); CSNode *B createNode(B); CSNode *C createNode(C); CSNode *D createNode(D); CSNode *E createNode(E); CSNode *F createNode(F); A-firstChild B; B-nextSibling C; C-nextSibling D; C-firstChild E; E-nextSibling F; return A; } // 二叉树的前序遍历验证转换结果 void preorder(CSNode *root) { if (root NULL) return; printf(%c , root-data); preorder(root-firstChild); preorder(root-nextSibling); } // 二叉树的中序遍历 void inorder(CSNode *root) { if (root NULL) return; inorder(root-firstChild); printf(%c , root-data); inorder(root-nextSibling); } int main() { CSTree tree buildTree(); printf(转换后的二叉树前序: ); preorder(tree); printf(\n); printf(转换后的二叉树中序: ); inorder(tree); printf(\n); return 0; }运行结果text转换后的二叉树前序: A B C E F D 转换后的二叉树中序: B E F C D A三、森林与二叉树的转换3.1 森林的定义森林是 mm ≥ 0棵互不相交的树的集合。3.2 森林转二叉树规则将森林中的每棵树分别转换成二叉树左孩子右兄弟将每棵树的根节点视为兄弟关系用右指针连接步骤第一棵树的根作为转换后二叉树的根第二棵树的根作为第一棵树根的右孩子第三棵树的根作为第二棵树根的右孩子以此类推...text森林 转换后的二叉树 Tree1 Tree2 Tree1根 ↓ ↓ \ Tree1根 Tree2根 Tree2根 \ Tree3根3.3 二叉树转森林判断条件如果二叉树的根节点有右孩子说明它是由森林转换来的。规则将根节点和左子树作为第一棵树将右子树作为剩下的森林递归处理3.4 代码实现c#include stdio.h #include stdlib.h typedef struct CSNode { char data; struct CSNode *firstChild; struct CSNode *nextSibling; } CSNode, *CSTree; CSNode* createNode(char data) { CSNode *node (CSNode*)malloc(sizeof(CSNode)); node-data data; node-firstChild NULL; node-nextSibling NULL; return node; } // 构建森林三棵树 // 树1: A 树2: D 树3: G // / \ | | // B C E H // | | // F I CSTree buildForest() { // 树1 CSNode *A createNode(A); CSNode *B createNode(B); CSNode *C createNode(C); A-firstChild B; B-nextSibling C; // 树2 CSNode *D createNode(D); CSNode *E createNode(E); CSNode *F createNode(F); D-firstChild E; E-firstChild F; // 树3 CSNode *G createNode(G); CSNode *H createNode(H); CSNode *I createNode(I); G-firstChild H; H-firstChild I; // 连接成森林根节点用右兄弟连接 A-nextSibling D; D-nextSibling G; return A; } // 森林转二叉树其实构建森林时已经按规则连接好了 // 这里只是验证 // 二叉树转森林按右兄弟断开 void forestToTree(CSTree root) { if (root NULL) return; printf(树根: %c\n, root-data); // 递归处理左子树孩子 if (root-firstChild) { printf( %c 的孩子: , root-data); CSNode *child root-firstChild; while (child) { printf(%c , child-data); child child-nextSibling; } printf(\n); forestToTree(root-firstChild); } // 递归处理右子树下一棵树 if (root-nextSibling) { forestToTree(root-nextSibling); } } void preorder(CSTree root) { if (root NULL) return; printf(%c , root-data); preorder(root-firstChild); preorder(root-nextSibling); } int main() { CSTree forest buildForest(); printf(森林转换后的二叉树前序: ); preorder(forest); printf(\n\n); printf(从二叉树还原森林:\n); forestToTree(forest); return 0; }运行结果text森林转换后的二叉树前序: A B C D E F G H I 从二叉树还原森林: 树根: A A 的孩子: B C 树根: B 树根: C 树根: D D 的孩子: E 树根: E E 的孩子: F 树根: F 树根: G G 的孩子: H 树根: H H 的孩子: I 树根: I四、树与二叉树的遍历对应关系树的遍历对应二叉树的遍历先根遍历前序遍历后根遍历中序遍历验证以前面的树为例原树先根遍历A B C E F D对应二叉树前序A B C E F D✓原树后根遍历B E F C D A对应二叉树中序B E F C D A✓五、三种存储方式对比存储方式找孩子找父节点空间开销适用场景双亲表示法慢快小并查集孩子表示法快慢中树形结构遍历孩子兄弟表示法快慢中树转二叉树六、小结这一篇我们学习了树、森林与二叉树的转换要点说明孩子兄弟表示法firstChild nextSibling树→二叉树左孩子右兄弟森林→二叉树先每棵树转二叉树再根节点用右兄弟连接遍历对应树先根二叉树前序树后根二叉树中序核心口诀左孩子第一个孩子右兄弟下一个兄弟森林转根连根下一篇我们讲哈夫曼树与哈夫曼编码。七、思考题一棵树转换成的二叉树它的右子树可能为空吗什么情况下为空森林转换成的二叉树根节点的右子树可能为空吗什么情况下为空如果已知一棵二叉树的先序和中序遍历序列如何判断它是由树还是由森林转换来的尝试用孩子兄弟表示法实现树的先根遍历和后根遍历。欢迎在评论区讨论你的答案。