当前位置: 首页 > news >正文

数据结构实验报告-树与二叉树

     

一、实验名称:

实验6 树和二叉树

二、实验内容:

1.编写二叉树的递归遍历算法,实现:给定一棵二叉树的“扩展先序遍历序列”,创建这棵二叉树。

(1)输出二叉树的先序遍历的结点序列。

(2)输出二叉树的后序遍历的结点序列。

(3)输出二叉树的中序遍历的结点序列。

(4)输出二叉树的叶子结点。

(5)统计二叉树的结点个数。

源码:
#include <stdio.h>

#include <stdlib.h>

typedef struct TreeNode {

    char data;

    struct TreeNode *left;

    struct TreeNode *right;

} TreeNode;

// 创建二叉树

TreeNode* createBinaryTree(char *str, int *index) {

    if (str[*index] == '\0') {

        return NULL;

    }

    if (str[*index] == '#') {

        (*index)++;

        return NULL;

    }

    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));

    root->data = str[*index];

    (*index)++;

   

    root->left = createBinaryTree(str, index);

    root->right = createBinaryTree(str, index);

    return root;

}

// 先序遍历

void preorder(TreeNode *root) {

    if (root != NULL) {

        printf("%c ", root->data);

        preorder(root->left);

        preorder(root->right);

    }

}

// 后序遍历

void postorder(TreeNode *root) {

    if (root != NULL) {

        postorder(root->left);

        postorder(root->right);

        printf("%c ", root->data);

    }

}

// 中序遍历

void inorder(TreeNode *root) {

    if (root != NULL) {

        inorder(root->left);

        printf("%c ", root->data);

        inorder(root->right);

    }

}

// 输出叶子节点

void printLeaves(TreeNode *root) {

    if (root != NULL) {

        if (root->left == NULL && root->right == NULL) {

            printf("%c ", root->data);

        }

        printLeaves(root->left);

        printLeaves(root->right);

    }

}

// 统计节点个数

int countNodes(TreeNode *root) {

    if (root == NULL) {

        return 0;

    }

    return 1 + countNodes(root->left) + countNodes(root->right);

}

int main() {

    char str[] = "AB#D##CE##"; // 示例扩展先序遍历序列

    int index = 0;

    TreeNode *root = createBinaryTree(str, &index);

    printf("先序遍历序列: ");

    preorder(root);

    printf("\n");

    printf("后序遍历序列: ");

    postorder(root);

    printf("\n");

    printf("中序遍历序列: ");

    inorder(root);

    printf("\n");

    printf("叶子节点: ");

    printLeaves(root);

    printf("\n");

    printf("节点个数: %d\n", countNodes(root));

    return 0;

}

2.编写非递归遍历算法,实现:给定一棵二又树的先序 遍历序列和中序通历序列,创建这棵二叉树。

(1)输出二叉树的后序遍历的结点序列。

(2)输出二叉树的叶子结点。

(3)统计二叉树的结点个数。

(4)求二叉树的深度。

(5)输出二叉树指定结点的路径。

源码:
#include <iostream>

#include <stack>

#include <vector>

#include <unordered_map>

using namespace std;

struct TreeNode {

    char data;

    TreeNode* left;

    TreeNode* right;

    TreeNode(char val) : data(val), left(NULL), right(NULL) {}

};

TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {

    if (preorder.empty() || inorder.empty()) return NULL;

    unordered_map<char, int> inorder_map;

    for (int i = 0; i < inorder.size(); ++i) {

        inorder_map[inorder[i]] = i;

    }

    stack<TreeNode*> stk;

    TreeNode* root = new TreeNode(preorder[0]);

    stk.push(root);

    for (int i = 1; i < preorder.size(); ++i) {

        TreeNode* node = new TreeNode(preorder[i]);

        TreeNode* top = stk.top();

        if (inorder_map[node->data] < inorder_map[top->data]) {

            top->left = node;

        } else {

            TreeNode* parent = NULL;

            while (!stk.empty() && inorder_map[node->data] > inorder_map[stk.top()->data]) {

                parent = stk.top();

                stk.pop();

            }

            parent->right = node;

        }

        stk.push(node);

    }

    return root;

}

void postorderTraversal(TreeNode* root) {

    if (root == NULL) return;

   

    stack<TreeNode*> stk;

    vector<char> result;

    stk.push(root);

    while (!stk.empty()) {

        TreeNode* node = stk.top();

        stk.pop();

        result.insert(result.begin(), node->data);

        if (node->left) stk.push(node->left);

        if (node->right) stk.push(node->right);

    }

    for (char ch : result) {

        cout << ch << " ";

    }

}

void printLeaves(TreeNode* root) {

    if (root == NULL) return;

    if (root->left == NULL && root->right == NULL) {

        cout << root->data << " ";

    }

    printLeaves(root->left);

    printLeaves(root->right);

}

int countNodes(TreeNode* root) {

    if (root == NULL) return 0;

    return 1 + countNodes(root->left) + countNodes(root->right);

}

int maxDepth(TreeNode* root) {

    if (root == NULL) return 0;

    return 1 + max(maxDepth(root->left), maxDepth(root->right));

}

void findPath(TreeNode* root, char target, vector<char>& path) {

    if (root == NULL) return;

    path.push_back(root->data);

    if (root->data == target) {

        for (char ch : path) {

            cout << ch << " ";

        }

        cout << endl;

    }

    findPath(root->left, target, path);

    findPath(root->right, target, path);

    path.pop_back();

}

int main() {

    vector<char> preorder = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};

    vector<char> inorder = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};

    TreeNode* root = buildTree(preorder, inorder);

    cout << "后序遍历序列: ";

    postorderTraversal(root);

    cout << endl;

    cout << "叶子节点: ";

    printLeaves(root);

    cout << endl;

    cout << "节点个数: " << countNodes(root) << endl;

    cout << "二叉树深度: " << maxDepth(root) << endl;

    char target = 'D';

    cout << "路径(" << target << "): ";

    vector<char> path;

    findPath(root, target, path);

    return 0;

}

3.1题,编写算法实现二叉树的先序线索化,并查找结点p的先序前驱结点和先序后继结点。

源码:
#include <iostream>

#include <stack>

using namespace std;

struct TreeNode {

    char data;

    TreeNode *left;

    TreeNode *right;

    bool isThreaded; // 线索化标记

    TreeNode(char val) : data(val), left(NULL), right(NULL), isThreaded(false) {}

};

void preorderThreading(TreeNode* root, TreeNode*& prev) {

    if (root == NULL) return;

    if (root->left == NULL) {

        root->left = prev;

        root->isThreaded = true;

    }

    if (prev != NULL && prev->right == NULL) {

        prev->right = root;

        prev->isThreaded = true;

    }

    prev = root;

    if (!root->isThreaded) {

        preorderThreading(root->left, prev);

    }

    preorderThreading(root->right, prev);

}

TreeNode* preorderSuccessor(TreeNode* node) {

    if (node->isThreaded) {

        return node->right;

    } else {

        TreeNode* curr = node->right;

        while (curr != NULL && !curr->isThreaded) {

            curr = curr->left;

        }

        return curr;

    }

}

TreeNode* preorderPredecessor(TreeNode* node) {

    if (node->left != NULL) {

        TreeNode* curr = node->left;

        while (curr->right != NULL && !curr->right->isThreaded) {

            curr = curr->right;

        }

        return curr;

    } else {

        return node->right;

    }

}

int main() {

    TreeNode *root = new TreeNode('A');

    root->left = new TreeNode('B');

    root->right = new TreeNode('C');

    root->left->left = new TreeNode('D');

    root->left->right = new TreeNode('E');

    root->right->left = new TreeNode('F');

    root->right->right = new TreeNode('G');

    TreeNode *prev = NULL;

    preorderThreading(root, prev);

    TreeNode *target = root->left; // 以结点'B'为例

    TreeNode *predecessor = preorderPredecessor(target);

    TreeNode *successor = preorderSuccessor(target);

    if (predecessor) {

        cout << "结点'" << target->data << "'的先序前驱结点是: " << predecessor->data << endl;

    } else {

        cout << "结点'" << target->data << "'没有先序前驱结点" << endl;

    }

    if (successor) {

        cout << "结点'" << target->data << "'的先序后继结点是: " << successor->data << endl;

    } else {

        cout << "结点'" << target->data << "'没有先序后继结点" << endl;

    }

    return 0;

}

四、心得体会:

通过实现二叉树的先序线索化算法,并查找指定结点的先序前驱和后继结点,我深刻体会到了树结构的复杂和线索化的重要性。在操作过程中,我学会了如何处理线索化和利用前序遍历进行结点的查找,进一步加深了对二叉树数据结构的理解。通过这一实践,我意识到了算法设计的精妙之处,同时也深感数据结构对于解决复杂问题的重要性。在编写代码的过程中,我不断思考优化方案,增强了自己的编程能力和逻辑思维能力。总的来说,这次实践让我收获颇丰,同时也更加坚定了我对算法与数据结构学习的重要性,激发了我对计算机科学领域的无限热情。

http://www.lryc.cn/news/414962.html

相关文章:

  • 基于Django+MySQL球馆场地预约系统的设计与实现(源码+论文+部署讲解等)
  • 8 MQTT
  • 【文件系统】抽象磁盘的存储结构 CHS寻址法 | sector数组 | LAB数组
  • 基于python旅游推荐系统(源码+论文+部署讲解等)
  • Mysql大单表JSON优化
  • 电脑开机启动项管理小工具,绿色免安装
  • 一例AutoHotkey语言生成的文件夹病毒分析
  • 【机器学习第7章——贝叶斯分类器】
  • C++ QT开发 学习笔记(3)
  • 【Python实战】如何优雅地实现文字 二维码检测?
  • 行为型设计模式3:模板方法/备忘录/解释器/迭代器
  • 思源笔记软件的优缺点分析
  • 追问试面试系列:Dubbo
  • 动手学深度学习V2每日笔记(卷积层)
  • qcom ucsi probe
  • flask和redis配合
  • 深度学习中的早停法
  • 科普文:JUC系列之多线程门闩同步器CountDownLatch的使用和源码
  • foreach循环和for循环在PHP中各有什么优势
  • 巧用casaos共享挂载自己的外接硬盘为局域网共享
  • 标题:解码“八股文”:助力、阻力,还是空谈?
  • 语言无界,沟通无限:2024年好用在线翻译工具推荐
  • 【Golang 面试 - 进阶题】每日 3 题(十八)
  • 二分+dp,CF 1993D - Med-imize
  • 三十种未授权访问漏洞复现 合集( 三)
  • 数据湖和数据仓库核心概念与对比
  • 探索WebKit的奥秘:打造高效、兼容的现代网页应用
  • 【leetcode】平衡二叉树、对称二叉树、二叉树的层序遍历(广度优先遍历)(详解)
  • 最短路径算法:Floyd-Warshall算法
  • 3DM游戏运行库合集离线安装包2024最新版