怎么使用二叉樹

這篇文章主要介紹“怎么使用二叉樹”，在日常操作中，相信很多人在怎么使用二叉樹問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么使用二叉樹”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

「以下以前序遍歷為例：」

「確定遞歸函數(shù)的參數(shù)和返回值」：因為要打印出前序遍歷節(jié)點的數(shù)值，所以參數(shù)里需要傳入vector在放節(jié)點的數(shù)值，除了這一點就不需要在處理什么數(shù)據(jù)了也不需要有返回值，所以遞歸函數(shù)返回類型就是void，代碼如下：

void traversal(TreeNode* cur, vector<int>& vec)

「確定終止條件」：在遞歸的過程中，如何算是遞歸結(jié)束了呢，當(dāng)然是當(dāng)前遍歷的節(jié)點是空了，那么本層遞歸就要要結(jié)束了，所以如果當(dāng)前遍歷的這個節(jié)點是空，就直接return，代碼如下：

if (cur == NULL) return;

「確定單層遞歸的邏輯」：前序遍歷是中左右的循序，所以在單層遞歸的邏輯，是要先取中節(jié)點的數(shù)值，代碼如下：

vec.push_back(cur->val);    // 中 traversal(cur->left, vec);  // 左 traversal(cur->right, vec); // 右

單層遞歸的邏輯就是按照中左右的順序來處理的，這樣二叉樹的前序遍歷，基本就寫完了，在看一下完整代碼：

前序遍歷：

class Solution { public:     void traversal(TreeNode* cur, vector<int>& vec) {         if (cur == NULL) return;         vec.push_back(cur->val);    // 中         traversal(cur->left, vec);  // 左         traversal(cur->right, vec); // 右     }     vector<int> preorderTraversal(TreeNode* root) {         vector<int> result;         traversal(root, result);         return result;     } };

那么前序遍歷寫出來之后，中序和后序遍歷就不難理解了，代碼如下：

中序遍歷：

void traversal(TreeNode* cur, vector<int>& vec) {        if (cur == NULL) return;        traversal(cur->left, vec);  // 左        vec.push_back(cur->val);    // 中        traversal(cur->right, vec); // 右    }

后序遍歷：

void traversal(TreeNode* cur, vector<int>& vec) {         if (cur == NULL) return;         traversal(cur->left, vec);  // 左         traversal(cur->right, vec); // 右         vec.push_back(cur->val);    // 中     }

此時大家可以做一做leetcode上三道題目，分別是：

• 144.二叉樹的前序遍歷

• 145.二叉樹的后序遍歷

• 94.二叉樹的中序遍歷

到此，關(guān)于“怎么使用二叉樹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>