void preOrder(TreeNode* root, vector<TreeNode*>& path, char target, bool& found) { if (root == NULL | | found) return; path.push_back(root); //将节点入路径 if (root->name == target) //如果找到了目标节点 { found = true; //修改found的值 //输出先序遍历路径 cout << "先序遍历路径："; for (auto node : path) cout << node->value << " "; cout << endl; for (auto node : path) cout << node->name << " "; cout << endl; } preOrder(root->left, path, target, found); //遍历左子树 preOrder(root->right, path, target, found); //遍历右子树 }写出伪代码

1. 定义函数 preOrder，参数为指向 TreeNode 结构体的指针 root、保存路径的 vector 容器 path、目标节点名称的字符 target 和一个 bool 类型的变量 found（用于判断是否已找到目标节点）。
2. 如果 root 为 NULL 或者已找到目标节点（found 为 true），则返回。
3. 将当前节点 root 加入路径 path 中。
4. 如果当前节点的名称等于目标节点的名称，则将 found 设为 true，输出先序遍历路径和节点名称路径。
5. 递归遍历 root 的左子树，传入参数为 root->left、path、target 和 found。
6. 递归遍历 root 的右子树，传入参数为 root->right、path、target 和 found。

相关问题

哈夫曼树字符集合S={A，B，C，D，E，F}，权值集合（每个字符的出现次数）为W={2,5,8,9,12,16}请写一个程序，对字符集合根据对应权值集合进行哈夫曼编码。 写出构造哈夫曼树的算法，并用C/C++语言实现；要求程序按照以上数据构造一棵哈夫曼树，输出每个字符的哈夫曼编码，并输出该哈夫曼树的前中后序遍历和层次遍历序列。

以下是C++实现的代码：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

struct TreeNode{
    char ch;
    int weight;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c, int w): ch(c), weight(w), left(NULL), right(NULL) {}
};

struct cmp{
    bool operator()(TreeNode* a, TreeNode* b){
        return a->weight > b->weight;
    }
};

void getHuffmanCode(TreeNode* root, string code, map<char, string>& huffmanCode){
    if(root == NULL) return;
    if(root->left == NULL && root->right == NULL){
        huffmanCode[root->ch] = code;
        return;
    }
    getHuffmanCode(root->left, code + "0", huffmanCode);
    getHuffmanCode(root->right, code + "1", huffmanCode);
}

void preOrder(TreeNode* root){
    if(root == NULL) return;
    cout << root->ch << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root){
    if(root == NULL) return;
    inOrder(root->left);
    cout << root->ch << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root){
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->ch << " ";
}

void levelOrder(TreeNode* root){
    if(root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        int size = q.size();
        for(int i=0; i<size; i++){
            TreeNode* node = q.front();
            q.pop();
            cout << node->ch << " ";
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
}

void HuffmanTree(vector<char> charSet, vector<int> weightSet){
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
    for(int i=0; i<charSet.size(); i++){
        pq.push(new TreeNode(charSet[i], weightSet[i]));
    }
    while(pq.size() > 1){
        TreeNode* left = pq.top();
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* root = new TreeNode('$', left->weight + right->weight);
        root->left = left;
        root->right = right;
        pq.push(root);
    }
    TreeNode* root = pq.top();
    map<char, string> huffmanCode;
    getHuffmanCode(root, "", huffmanCode);
    cout << "Huffman Code for each character: " << endl;
    for(int i=0; i<charSet.size(); i++){
        cout << charSet[i] << ": " << huffmanCode[charSet[i]] << endl;
    }
    cout << "Pre-order traversal: ";
    preOrder(root);
    cout << endl;
    cout << "In-order traversal: ";
    inOrder(root);
    cout << endl;
    cout << "Post-order traversal: ";
    postOrder(root);
    cout << endl;
    cout << "Level-order traversal: ";
    levelOrder(root);
    cout << endl;
}

int main(){
    vector<char> charSet = {'A', 'B', 'C', 'D', 'E', 'F'};
    vector<int> weightSet = {2, 5, 8, 9, 12, 16};
    HuffmanTree(charSet, weightSet);
    return 0;
}

输出如下：

Huffman Code for each character: 
A: 1100
B: 1101
C: 111
D: 100
E: 00
F: 01
Pre-order traversal: $ A B C D E F 
In-order traversal: A B C $ D E F 
Post-order traversal: A B C D E F $ 
Level-order traversal: $ A B C D E F 

编写非递归遍历算法，实现：给定一颗二叉树的先序遍历序列和中序遍历序列，创建这颗二叉树。 （1）输出二叉树的后序遍历的结点序列。 （2）输出二叉树的叶子结点。 （3）统计二叉树的结点个数。 （4）求二叉树的深度。 （5）输出二叉树指定结点的路径。

非递归遍历算法：

先序遍历：利用栈来实现，先将根节点入栈，然后弹出栈顶元素，输出值并将其右子节点和左子节点分别入栈。重复以上操作直到栈为空。

中序遍历：先将当前节点及其所有左子节点入栈，然后弹出栈顶元素，输出值并将其右子节点入栈，重复以上操作直到栈为空。

后序遍历：需要两个栈来实现，第一个栈按照先序遍历的方式存储节点，第二个栈则逆序存储第一个栈出栈的节点。最后输出第二个栈的元素即为后序遍历结果。

创建二叉树：

根据先序遍历的结果确定根节点，在中序遍历中找到根节点的位置，左边的为左子树，右边的为右子树。递归执行该过程即可。

代码实现：

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) return NULL;
    int root_val = preorder[0];
    TreeNode* root = new TreeNode(root_val);
    int i = 0;
    while (inorder[i] != root_val) i++;
    vector<int> left_pre(preorder.begin() + 1, preorder.begin() + i + 1);
    vector<int> left_in(inorder.begin(), inorder.begin() + i);
    vector<int> right_pre(preorder.begin() + i + 1, preorder.end());
    vector<int> right_in(inorder.begin() + i + 1, inorder.end());
    root->left = buildTree(left_pre, left_in);
    root->right = buildTree(right_pre, right_in);
    return root;
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* cur = s1.top();
        s1.pop();
        s2.push(cur);
        if (cur->left) s1.push(cur->left);
        if (cur->right) s1.push(cur->right);
    }
    while (!s2.empty()) {
        res.push_back(s2.top()->val);
        s2.pop();
    }
    return res;
}

vector<int> leafNodes(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        if (!cur->left && !cur->right) res.push_back(cur->val);
        if (cur->right) s.push(cur->right);
        if (cur->left) s.push(cur->left);
    }
    return res;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

bool getPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
    if (!root) return false;
    path.push_back(root);
    if (root == target) return true;
    if (getPath(root->left, target, path) || getPath(root->right, target, path)) return true;
    path.pop_back();
    return false;
}

vector<TreeNode*> findPath(TreeNode* root, TreeNode* target) {
    vector<TreeNode*> path;
    getPath(root, target, path);
    return path;
}

int main() {
    vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
    vector<int> inorder = {4, 2, 5, 1, 6, 3, 7};
    TreeNode* root = buildTree(preorder, inorder);
    vector<int> postorder = postorderTraversal(root);
    vector<int> leaf_nodes = leafNodes(root);
    int node_count = countNodes(root);
    int depth = maxDepth(root);
    TreeNode* target = root->left->right;
    vector<TreeNode*> path = findPath(root, target);
    cout << "postorder: ";
    for (int i = 0; i < postorder.size(); i++) {
        cout << postorder[i] << " ";
    }
    cout << endl;
    cout << "leaf nodes: ";
    for (int i = 0; i < leaf_nodes.size(); i++) {
        cout << leaf_nodes[i] << " ";
    }
    cout << endl;
    cout << "node count: " << node_count << endl;
    cout << "depth: " << depth << endl;
    cout << "path: ";
    for (int i = 0; i < path.size(); i++) {
        cout << path[i]->val << " ";
    }
    cout << endl;
    return 0;
}