二叉树搜索

#include <iostream>
#include <vector>using namespace std;struct Node{int value;Node* left_node;Node* right_node;Node(int v){value = v;left_node = nullptr;right_node = nullptr;    }
};bool findNode(Node* node, int target_node, vector<int>& path){if (!node) return false;cout << "---node->value : "<< node->value << endl; // save pathpath.push_back(node->value);// find target nodeif (node->value == target_node){cout << "---find target_node--- "<< endl;   return true;}// cout << "---2--- "<< endl;    // 如果左分支或者右分支找到了if (findNode(node->left_node, target_node, path)){return true;} if (findNode(node->right_node, target_node, path)){return true;}path.pop_back();return false;
}void findTreePath(Node* root_node, int curr_node ,int goal_node, vector<int>& path){// find curr node path vector<int> path1;bool ret = findNode(root_node, curr_node, path1);cout << "ret: " << ret << endl;cout << "path1," << path1.size() << ":";for (auto p: path1){cout << p << " --> " ;}cout << endl;vector<int> path2;// find goal node path findNode(root_node, goal_node, path2);cout << "path2" << endl;for (auto p: path2){cout << p << " --> " ;}cout << endl;// pingjie pathfor (int i = path1.size()-1; i >= 0; i--){path.push_back(path1[i]);}for (int i = 1; i < path2.size(); i++){path.push_back(path2[i]);}}int main(){Node* root_node  = new Node(4);root_node->left_node = new Node(3);root_node->right_node = new Node(5);root_node->left_node->left_node = new Node(1);root_node->left_node->right_node = new Node(2);root_node->right_node->left_node = new Node(6);root_node->right_node->right_node = new Node(7);int curr_node = 1;int goal_node = 7;vector<int> path;findTreePath(root_node, curr_node, goal_node, path);cout << "Total path:" << endl;for (auto p: path){cout << p << " --> " ;}cout << endl;return 0;
}

输出

---node->value : 4
---node->value : 3
---node->value : 1
---find target_node--- 
ret: 1
path1,3:4 --> 3 --> 1 --> 
---node->value : 4
---node->value : 3
---node->value : 1
---node->value : 2
---node->value : 5
---node->value : 6
---node->value : 7
---find target_node--- 
path2
4 --> 5 --> 7 --> 
Total path:
1 --> 3 --> 4 --> 5 --> 7 --> Normal program termination. Exit status: 0