网站建设如何选择良好的服务器,定制网站+域名+企业邮箱,个人网站建设方案,傻瓜式网站文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语 5.2 二叉树5.3 树5.3.1 树的存储结构1. 理论基础2. 典型实例 5.3.2 Father链接结构a. 定义树节点结构b. 创建新节点c. 主函数d. 代码整合 5.3.3 儿子链表链接结构a. 定义树节点结构b. 创建新节点c. 添加… 文章目录 5.1 树的基本概念5.1.1 树的定义5.1.2 森林的定义5.1.3 树的术语 5.2 二叉树5.3 树5.3.1 树的存储结构1. 理论基础2. 典型实例 5.3.2 Father链接结构a. 定义树节点结构b. 创建新节点c. 主函数d. 代码整合 5.3.3 儿子链表链接结构a. 定义树节点结构b. 创建新节点c. 添加子节点作为第一个子节点d. 遍历树打印节点数据e. 主函数f. 代码整合 5.1 树的基本概念
5.1.1 树的定义
一棵树是结点的有限集合T 若T非空则 有一个特别标出的结点称作该树的根记为root(T)其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m0)其中T1, T2, …, Tm又都是树称作root(T)的子树。 T 空时为空树记作root(T)NULL。
5.1.2 森林的定义 一个森林是0棵或多棵不相交非空树的集合通常是一个有序的集合。换句话说森林由多个树组成这些树之间没有交集且可以按照一定的次序排列。在森林中每棵树都是独立的具有根节点和子树树与树之间没有直接的连接关系。 森林是树的扩展概念它是由多个树组成的集合。在计算机科学中森林也被广泛应用于数据结构和算法设计中特别是在图论和网络分析等领域。
5.1.3 树的术语
父亲parent、儿子child、兄弟sibling、后裔descendant、祖先ancestor度degree、叶子节点leaf node、分支节点internal node结点的层数路径、路径长度、结点的深度、树的深度
参照前文【数据结构】树与二叉树一树森林的基本概念父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度
5.2 二叉树
5.3 树
5.3.1 树的存储结构
1. 理论基础 Father链接结构: 在这种结构中每个节点除了存储数据外还包含一个指向其父节点的指针。这种结构使得查找父节点很容易但对于查找子节点则较为困难因为需要遍历整个树。在二叉树中每个节点最多有一个父节点但在一般的树中节点可以有多个父节点。 儿子链表链接结构: 在这种结构中每个节点包含一个指向其第一个子节点的指针以及一个指向其下一个兄弟节点的指针。这种结构使得查找子节点很容易但查找父节点较为困难可能需要遍历兄弟节点链表直到找到相应的父节点。 左儿子右兄弟链接结构: 也称为孩子兄弟表示法每个节点包含一个指向其第一个子节点的指针以及一个指向其下一个兄弟节点的指针。在这种结构中树的每一层被表示为一个单链表子节点通过左链连接兄弟节点通过右链连接。这种结构既方便查找父节点又方便查找子节点和兄弟节点被广泛用于一般的树的表示。 选择合适的树的存储结构通常取决于具体应用的需求。 Father链接结构适合于查找父节点的操作频繁而儿子链表链接结构和左儿子右兄弟链接结构适用于频繁查找子节点的情况。
2. 典型实例 Father链接结构: A节点父指针为nullA为根节点B节点父指针指向AC节点父指针指向AD节点父指针指向AE节点父指针指向CF节点父指针指向C 儿子链表链接结构: A节点子节点链表为B、C、DB节点子节点链表为nullC节点子节点链表为E、FD节点子节点链表为nullE节点子节点链表为nullF节点子节点链表为null 左儿子右兄弟链接结构: A节点左儿子为B右兄弟为nullB节点左儿子为null右兄弟为CC节点左儿子为E右兄弟为DD节点左儿子为null右兄弟为nullE节点左儿子为null右兄弟为FF节点左儿子为null右兄弟为null
5.3.2 Father链接结构
a. 定义树节点结构
typedef struct TreeNode {char data; // 节点数据struct TreeNode* parent; // 指向父节点的指针
} TreeNode;b. 创建新节点
TreeNode* createNode(char data) {TreeNode* newNode (TreeNode*)malloc(sizeof(TreeNode));if (newNode NULL) {fprintf(stderr, Memory allocation failed\n);exit(EXIT_FAILURE);}newNode-data data;newNode-parent NULL;return newNode;
}
c. 主函数
int main() {// 创建节点TreeNode* nodeA createNode(A);TreeNode* nodeB createNode(B);TreeNode* nodeC createNode(C);TreeNode* nodeD createNode(D);TreeNode* nodeE createNode(E);TreeNode* nodeF createNode(F);// 构建树结构设置父指针nodeB-parent nodeA;nodeC-parent nodeA;nodeD-parent nodeA;nodeE-parent nodeC;nodeF-parent nodeC;// 打印每个节点及其父节点printf(Node %c, Parent: %c\n, nodeA-data, (nodeA-parent ? nodeA-parent-data : N));printf(Node %c, Parent: %c\n, nodeB-data, (nodeB-parent ? nodeB-parent-data : N));printf(Node %c, Parent: %c\n, nodeC-data, (nodeC-parent ? nodeC-parent-data : N));printf(Node %c, Parent: %c\n, nodeD-data, (nodeD-parent ? nodeD-parent-data : N));printf(Node %c, Parent: %c\n, nodeE-data, (nodeE-parent ? nodeE-parent-data : N));printf(Node %c, Parent: %c\n, nodeF-data, (nodeF-parent ? nodeF-parent-data : N));// 释放内存free(nodeA);free(nodeB);free(nodeC);free(nodeD);free(nodeE);free(nodeF);return 0;
}d. 代码整合
#include stdio.h
#include stdlib.h// 定义树节点结构
typedef struct TreeNode {char data; // 节点数据struct TreeNode* parent; // 指向父节点的指针
} TreeNode;// 创建新节点的函数
TreeNode* createNode(char data) {TreeNode* newNode (TreeNode*)malloc(sizeof(TreeNode));if (newNode NULL) {fprintf(stderr, Memory allocation failed\n);exit(EXIT_FAILURE);}newNode-data data;newNode-parent NULL;return newNode;
}int main() {// 创建节点TreeNode* nodeA createNode(A);TreeNode* nodeB createNode(B);TreeNode* nodeC createNode(C);TreeNode* nodeD createNode(D);TreeNode* nodeE createNode(E);TreeNode* nodeF createNode(F);// 构建树结构设置父指针nodeB-parent nodeA;nodeC-parent nodeA;nodeD-parent nodeA;nodeE-parent nodeC;nodeF-parent nodeC;// 打印每个节点及其父节点printf(Node %c, Parent: %c\n, nodeA-data, (nodeA-parent ? nodeA-parent-data : N));printf(Node %c, Parent: %c\n, nodeB-data, (nodeB-parent ? nodeB-parent-data : N));printf(Node %c, Parent: %c\n, nodeC-data, (nodeC-parent ? nodeC-parent-data : N));printf(Node %c, Parent: %c\n, nodeD-data, (nodeD-parent ? nodeD-parent-data : N));printf(Node %c, Parent: %c\n, nodeE-data, (nodeE-parent ? nodeE-parent-data : N));printf(Node %c, Parent: %c\n, nodeF-data, (nodeF-parent ? nodeF-parent-data : N));// 释放内存free(nodeA);free(nodeB);free(nodeC);free(nodeD);free(nodeE);free(nodeF);return 0;
}注其他操作……有缘再见
5.3.3 儿子链表链接结构
a. 定义树节点结构
struct TreeNode {char data;struct TreeNode* child;struct TreeNode* sibling;
};b. 创建新节点
struct TreeNode* createNode(char data) {struct TreeNode* newNode (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode-data data;newNode-child NULL;newNode-sibling NULL;return newNode;
}
c. 添加子节点作为第一个子节点
void addChild(struct TreeNode* parent, struct TreeNode* child) {child-sibling parent-child;parent-child child;
}
d. 遍历树打印节点数据 void traverseTree(struct TreeNode* root) {if (root ! NULL) {printf(%c\n, root-data);struct TreeNode* child root-child;while (child ! NULL) {printf( %c (Child)\n, child-data);child child-sibling;}// 递归遍历每个子节点child root-child;while (child ! NULL) {traverseTree(child);child child-sibling;}}
}e. 主函数
int main() {// 创建树节点struct TreeNode* A createNode(A);struct TreeNode* B createNode(B);struct TreeNode* C createNode(C);struct TreeNode* D createNode(D);struct TreeNode* E createNode(E);struct TreeNode* F createNode(F);// 构建树结构addChild(A, B);addChild(A, C);addChild(A, D);addChild(C, E);addChild(C, F);// 遍历并打印树节点traverseTree(A);// 释放内存free(A);free(B);free(C);free(D);free(E);free(F);return 0;
} f. 代码整合
#include stdio.h
#include stdlib.h// 定义树节点结构
struct TreeNode {char data;struct TreeNode* child;struct TreeNode* sibling;
};// 创建新节点
struct TreeNode* createNode(char data) {struct TreeNode* newNode (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode-data data;newNode-child NULL;newNode-sibling NULL;return newNode;
}// 添加子节点作为第一个子节点
void addChild(struct TreeNode* parent, struct TreeNode* child) {child-sibling parent-child;parent-child child;
}// 遍历树并打印节点
void traverseTree(struct TreeNode* root) {if (root ! NULL) {printf(%c\n, root-data);struct TreeNode* child root-child;while (child ! NULL) {printf( %c (Child)\n, child-data);child child-sibling;}// 递归遍历每个子节点child root-child;while (child ! NULL) {traverseTree(child);child child-sibling;}}
}int main() {// 创建树节点struct TreeNode* A createNode(A);struct TreeNode* B createNode(B);struct TreeNode* C createNode(C);struct TreeNode* D createNode(D);struct TreeNode* E createNode(E);struct TreeNode* F createNode(F);// 构建树结构addChild(A, B);addChild(A, C);addChild(A, D);addChild(C, E);addChild(C, F);// 遍历并打印树节点traverseTree(A);// 释放内存free(A);free(B);free(C);free(D);free(E);free(F);return 0;
}
