本文共 3956 字，大约阅读时间需要 13 分钟。

存储与遍历树的实现

项目背景

本题旨在实现树的存储与遍历，通过C++编程对树结构进行操作。树是常见的数据结构之一，具有穷尽搜索等特性。在实际应用中，树的存储与遍历是解决许多问题的关键步骤。本文将详细介绍树的存储方法以及常用遍历算法的实现。

树的存储方法

在本项目中，我们采用了孩子存储法来存储树。这种方法的核心思想是将每个节点的子节点存储在一个数组中，通过指针链接每个节点的孩子。具体来说，每个节点包含以下信息：

• 值：节点的数据内容
• 级别：节点所在的层数
• 下一个孩子：指向下一个子节点的指针

我们使用一个向量tree来存储所有节点，其中每个节点对应一个ptree对象。ptree结构体包含父节点信息和第一个孩子节点的指针。

typedef struct node {
    int value;
    int level;
    struct node *nextChild;
} *Node;
struct ptree {
    int parent;
    struct node *firstChild;
} tree[100];

层次遍历（BFS）的实现

层次遍历（BFS）是常用的树遍历算法，其核心思想是按层次从根节点开始，逐层访问子节点。我们使用一个队列来实现BFS，队列中的每个节点代表当前访问的节点。具体实现步骤如下：

void levelOrder() {
    int leaf = 0;
    struct node *parent;
    struct node *tempNode;
    queue
   
     myQueue;
    // 初始化根节点
    struct node *rootNode = (struct node*)malloc(sizeof(struct node));
    int currentStep = 0;
    rootNode->value = tree[1].parent;
    rootNode->nextChild = tree[1].firstChild;
    rootNode->level = 0;
    myQueue.push(rootNode);
    while (!myQueue.empty()) {
        tempNode = myQueue.front();
        myQueue.pop();
        int myParent = tempNode->value;
        int level = tempNode->level;
        // 检查是否为当前层的最后一个节点
        if (level > currentStep) {
            currentStep = level;
            leaf = 0;
        }
        // 检查是否为叶子节点
        if (tree[myParent].firstChild == NULL) {
            leaf++;
        }
        // 将子节点加入队列
        struct node *firstChild = tree[myParent].firstChild;
        while (firstChild != NULL) {
            firstChild->level = level + 1;
            myQueue.push(firstChild);
            firstChild = firstChild->nextChild;
        }
    }
    nonLeafs.push_back(leaf);
}
   

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
         
           using namespace std; #define INF 0x7FFFFFFF typedef struct node { int value; int level; struct node *nextChild; } *Node; struct ptree { int parent; struct node *firstChild; } tree[100]; vector
          
            nonLeafs; queue
           
             myQueue; void levelOrder() { int leaf = 0; Node tempNode; int currentStep = 0; // 初始化根节点 Node rootNode = (Node)malloc(sizeof(Node)); rootNode->value = tree[1].parent; rootNode->nextChild = tree[1].firstChild; rootNode->level = 0; myQueue.push(rootNode); while (!myQueue.empty()) { tempNode = myQueue.front(); myQueue.pop(); int myParent = tempNode->value; int level = tempNode->level; // 检查是否为当前层的最后一个节点 if (level > currentStep) { currentStep = level; leaf = 0; } // 检查是否为叶子节点 if (tree[myParent].firstChild == NULL) { leaf++; } // 将子节点加入队列 Node firstChild = tree[myParent].firstChild; while (firstChild != NULL) { firstChild->level = level + 1; myQueue.push(firstChild); firstChild = firstChild->nextChild; } } nonLeafs.push_back(leaf); } int main() { int nodes, nonLeafNodes; while (scanf("%d %d", &nodes, &nonLeafNodes) != EOF) { tree.resize(nodes + 1); for (int i = 1; i <= nonLeafNodes; ++i) { int parentNode, nodesSize; scanf("%d %d", &parentNode, &nodesSize); Node tempNode = (Node)malloc(sizeof(Node)); tree[parentNode].firstChild = NULL; for (int j = 0; j < nodesSize; ++j) { int tempChild; scanf("%d", &tempChild); if (j == 0) { tempNode->value = tempChild; tree[parentNode].firstChild = tempNode; if (j == nodesSize - 1) { tempNode->nextChild = NULL; } continue; } Node temp2Node = (Node)malloc(sizeof(Node)); temp2Node->value = tempChild; tempNode->nextChild = temp2Node; tempNode = temp2Node; if (j == nodesSize - 1) { tempNode->nextChild = NULL; } } } levelOrder(); for (int i = 0; i < nonLeafs.size(); ++i) { if (i == nonLeafs.size() - 1) { printf("%d", nonLeafs[i]); } else { printf("%d ", nonLeafs[i]); } } } return 0; }
           
          
         
        
       
      
     
    
   

优化建议

• 结构体指针管理：确保结构体指针通过malloc分配，并在适当时释放内存，避免内存泄漏。
• 循环终止条件：在链表遍历时，确保最后一个节点的nextChild指针置为空，防止死循环。
• 层次遍历优化：通过记录层数，避免重复处理同一层的节点，提升效率。

项目总结

本项目通过C++实现了树的存储与层次遍历，采用了孩子存储法和队列数据结构，确保了树的高效存储与遍历。代码结构清晰，易于扩展和维护，适用于处理大规模树结构问题。

转载地址：http://blqfk.baihongyu.com/