用C++实现根据二叉树的抽象数据类型的定义使用二叉链表实现一个二叉树。 二叉树的基本功能： 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他：自定义操作 编写测试 main函数测试二叉树的正确性

#include #include using namespace std;

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

// 建立二叉树 void createTree(TreeNode* &root){ char c; cin >> c; if(c == '#') return; root = new TreeNode(c); createTree(root->left); createTree(root->right); }

// 前序遍历 void preorder(TreeNode* root){ if(root == NULL) return; cout << root->val << " "; preorder(root->left); preorder(root->right); }

// 中序遍历 void inorder(TreeNode* root){ if(root == NULL) return; inorder(root->left); cout << root->val << " "; inorder(root->right); }

// 后序遍历 void postorder(TreeNode* root){ if(root == NULL) return; postorder(root->left); postorder(root->right); cout << root->val << " "; }

// 层序遍历 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->val << " "; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } } }

// 求深度 int depth(TreeNode* root){ if(root == NULL) return 0; int leftDepth = depth(root->left); int rightDepth = depth(root->right); return max(leftDepth, rightDepth) + 1; }

// 求指定结点到根的路径 bool getPath(TreeNode* root, char val, vector& path){ if(root == NULL) return false; path.push_back(root->val); if(root->val == val) return true; if(getPath(root->left, val, path)) return true; if(getPath(root->right, val, path)) return true; path.pop_back(); return false; }

// 销毁二叉树 void destroyTree(TreeNode* &root){ if(root == NULL) return; destroyTree(root->left); destroyTree(root->right); delete root; root = NULL; }

int main(){ TreeNode* root = NULL; createTree(root); cout << "前序遍历："; preorder(root); cout << endl; cout << "中序遍历："; inorder(root); cout << endl; cout << "后序遍历："; postorder(root); cout << endl; cout << "层序遍历："; levelorder(root); cout << endl; cout << "深度为：" << depth(root) << endl; vector path; char val; cout << "请输入要查找路径的结点："; cin >> val; if(getPath(root, val, path)){ cout << "路径为："; for(int i = 0; i < path.size(); i++){ cout << path[i] << " "; } cout << endl; }else{ cout << "未找到该结点" << endl; } destroyTree(root); return 0;