本文用于存储有关于如何建立二叉树的代码头文件写的有点乱#include iostream #include queue #includestdio.h #includevector using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; TreeNode* parent; bool leftis; }; TreeNode* initTree(char data) { TreeNode* root new TreeNode; root-data data; root-left nullptr; root-right nullptr; root-parent nullptr; root-leftis false; return root; } void buildTree(TreeNode* root) { char data; queueTreeNode*queue; cin data; if (data #) { root nullptr; return; } root initTree(data); queue.push(root); //while ( (data getchar() )!EOF) while(1) { scanf_s(%c, data); if (data \n) break; if (data ! #) { TreeNode* newNode new TreeNode; newNode-data data; newNode-left nullptr; newNode-right nullptr; newNode-leftis false; newNode-parent queue.front(); if (queue.front()-leftis false) { queue.front()-left newNode; queue.front()-leftis true; } else { queue.front()-right newNode; queue.pop(); } queue.push(newNode); } else { if (queue.front()-leftis false) { queue.front()-left nullptr; queue.front()-leftis true; } else { queue.front()-right nullptr; queue.pop(); } } //if (queue.empty()) { // break; //} } } void preOrder(TreeNode* root) { if (root ! nullptr) { cout root-data ; preOrder(root-left); preOrder(root-right); } } void postOrder(TreeNode* root) { if (root ! nullptr) { postOrder(root-left); postOrder(root-right); cout root-data ; } } void inOrder(TreeNode* root) { if (root ! nullptr) { inOrder(root-left); cout root-data ; inOrder(root-right); } } void deleteTree(TreeNode* root) { if (root ! nullptr) { deleteTree(root-left); deleteTree(root-right); delete root; } } // 返回 true 表示找到了false 表示没找到 bool searchAndPrintPath(TreeNode* root, char target) { if (root nullptr) return false; // 1. 如果当前节点就是目标 if (root-data target) { cout Path from Target to Root: ; TreeNode* curr root; // 沿着 parent 指针一直向上直到 nullptr while (curr ! nullptr) { cout curr-data ; curr curr-parent; } cout endl; // 如果想打印 Root to Target可以用 vector 存一下再反转 vectorchar path; curr root; while(curr){ path.push_back(curr-data); curr curr-parent; } reverse(path.begin(), path.end()); cout Path from Root to Target: ; for(char c : path) cout c ; cout endl; return true; } // 2. 在左子树找 if (searchAndPrintPath(root-left, target)) { return true; // 找到了就直接返回不再找右边 } // 3. 在右子树找 if (searchAndPrintPath(root-right, target)) { return true; } return false; } int main() { char data; TreeNode* rootnullptr; buildTree(root); cout \nbuild tree successfully! endl; preOrder(root); cout \npreorder traversal successfully! endl; inOrder(root); cout \ninorder traversal successfully! endl; postOrder(root); cout \npostorder traversal successfully! endl; searchAndPrintPath(root,F); deleteTree(root); } //测试输入为ABC##DE##F##G##