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

桂 林 理 工 大 学

实  验  报  告

一、实验名称：

实验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;

}

四、心得体会：

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