参考链接： 1.https://blog.csdn.net/ns_code/article/details/12977901 2.https://blog.csdn.net/libingbojava/article/details/81080036
后续需要加入二叉树的增删查改等基本操作 #include <iostream> #include <vector> using std::vector; using std::cout; using std::cin; using std::endl; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} TreeNode() {}; }; //先序遍历 void pre_traverse(TreeNode *pTree) { if (pTree) { cout << pTree->val; if (pTree->left) pre_traverse(pTree->left); if (pTree->right) pre_traverse(pTree->right); } } //中序遍历 void in_traverse(TreeNode *pTree) { if (pTree) { if (pTree->left) in_traverse(pTree->left); cout << pTree->val; if (pTree->right) in_traverse(pTree->right); } } //后序遍历 void pos_traverse(TreeNode* pTree) { if (pTree) { if (pTree->left) pos_traverse(pTree->left); if (pTree->right) pos_traverse(pTree->right); cout << pTree->val; } } //先序递归创建二叉树,方法1,输入方式例如ABC###D## void CreateBiTree_test1(TreeNode* &pTree) { //按先序输入二叉树中结点的值（一个字符），#字符代表空树， char ch; if ((ch = getchar()) == '#') pTree = NULL;//其中getchar（）为逐个读入标准库函数 else { pTree = new TreeNode;//产生新的子树 pTree->val = ch;//由getchar（）逐个读入来 CreateBiTree_test1(pTree->left);//递归创建左子树 CreateBiTree_test1(pTree->right);//递归创建右子树 } } //先序递归创建二叉树,方法2,输入方式逐个输入并回车ABC###D## void CreateBiTree_test2(TreeNode* &pTree) //此处pTree为引用 { //按先序序列输入二叉树中的节点值,#代表空树 char ch; //接收输入的字符 cout << "先序输入字符" << endl; cin >> ch; if (ch == '#') pTree = NULL; else { pTree = new TreeNode;//产生新的子树 pTree->val = ch; CreateBiTree_test2(pTree->left); //构造左子树 CreateBiTree_test2(pTree->right);//构造右子树 } } void ConnectTreeNodes(TreeNode* pParent, TreeNode* pLeft, TreeNode* pRight) { if (pParent != nullptr) { pParent->left = pLeft; pParent->right = pRight; } } struct TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> in) { if (pre.size() == NULL) return NULL; TreeNode* root = new TreeNode(pre[0]); unsigned int i; //此处i的类型需为unsigned int;因为in.size()的返回类型为unsigned int; for (i = 0; i < in.size() && in[i] != pre[0]; i++); vector<int> pre_left, in_left, pre_right, in_right; int pre_i = 1; for (unsigned int j = 0; j < in.size(); j++) { if (j < i) { in_left.push_back(in[j]); pre_left.push_back(pre[pre_i]); pre_i++; } else if (j > i) { in_right.push_back(in[j]); pre_right.push_back(pre[pre_i]); pre_i++; } } root->left = reConstructBinaryTree(pre_left, in_left); root->right = reConstructBinaryTree(pre_right, in_right); return root; } void PrintTreeNode(const TreeNode* pNode) { if (pNode != nullptr) { printf("value of this node is: %d\n", pNode->val); if (pNode->left != nullptr) printf("value of its left child is: %d.\n", pNode->left->val); else printf("left child is nullptr.\n"); if (pNode->right != nullptr) printf("value of its right child is: %d.\n", pNode->right->val); else printf("right child is nullptr.\n"); } else { printf("this node is nullptr.\n"); } printf("\n"); } void PrintTree(const TreeNode* pRoot) { PrintTreeNode(pRoot); if (pRoot != nullptr) { if (pRoot->left != nullptr) PrintTree(pRoot->left); if (pRoot->right != nullptr) PrintTree(pRoot->right); } } int main() { vector<int> pre = { 1, 2, 4, 5, 3, 6, 7 }; vector<int> in = { 4, 2, 5, 1, 6, 3, 7 }; cout << "the pre is :"; for (vector<int>::iterator v = pre.begin(); v != pre.end(); v++) { cout << (*v) << " "; } cout << endl; cout << "the in is :"; for (vector<int>::iterator v = in.begin(); v != in.end(); v++) { cout << (*v) << " "; } cout << endl; //测试由先序遍历数组与中序遍历数据得出二叉树结构 TreeNode* root = reConstructBinaryTree(pre, in); PrintTree(root); cout << "the preorder traversal is :"; pre_traverse(root); cout << endl; cout << "the inorder traversal is :"; in_traverse(root); cout << endl; cout << "the postorder traversal is :"; pos_traverse(root); cout << endl; cout << endl; //测试二叉树的创建 TreeNode *test; cout << "进入二叉树的创建测试" << endl; CreateBiTree_test1(test); cout << "the preorder traversal is :"; pre_traverse(test); cout << endl; cout << "the inorder traversal is :"; in_traverse(test); cout << endl; cout << "the postorder traversal is :"; pos_traverse(test); cout << endl; return 0; }