二叉樹的創建和遍歷-C語言實現

---

鏈式存儲結構

struct BinaryTreeNode {//數據char data;//左子樹BinaryTreeNode *leftChild;//右子樹BinaryTreeNode *rightChild;};

三種遍歷方式

• 中序遍歷

• 中序遍歷其左子樹
• 訪問根節點
• 中序遍歷其右子樹

• 先序遍歷（前序遍歷）

• 訪問根節點
• 先序遍歷其左子樹
• 先序遍歷其右子樹
• 后序遍歷
  
• 后序遍歷其左子樹
• 后序遍歷其右子樹
• 訪問根節點

樹的形狀

代碼實現

#include <iostream> #include <stack> #include<vector> #include <queue>using namespace std;//起別名 typedef struct BinaryTreeNode *BinaryTree;struct BinaryTreeNode {//數據char data;//左子樹BinaryTreeNode *leftChild;//右子樹BinaryTreeNode *rightChild; };/*** 訪問二叉樹的節點* @param binaryTree*/ void visit(BinaryTree binaryTree) {if (binaryTree) {cout << binaryTree->data << " ";} }/*** 創建一棵二叉樹，約定用戶遵照前序遍歷的方式輸入數據* @param binaryTree*/ void createTree(BinaryTree *binaryTree) {// abd**fe***cg*h**i** 根據創建二叉樹char dataTemp;cin >> dataTemp;//用*來表示該節點的數據為空即該節點為空if ('*' == dataTemp) {*binaryTree = NULL;} else {//先創建該結點*binaryTree = (BinaryTree) (malloc(sizeof(BinaryTreeNode)));//前序遍歷：數據->左子樹->右子樹(*binaryTree)->data = dataTemp;createTree(&(*binaryTree)->leftChild);createTree(&(*binaryTree)->rightChild);} }/*** 中序遍歷二叉樹（遞歸算法）* @param binaryTree*/ void InOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {InOrderTraversal(binaryTree->leftChild);visit(binaryTree);InOrderTraversal(binaryTree->rightChild);} }/*** 中序遍歷（非遞歸）* @param binaryTree*/ void InOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//初始化棧stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指針進棧，遍歷左子樹if (temp != NULL) {myStack.push(temp);temp = temp->leftChild;} else {//根指針退棧，訪問根節點，遍歷右子樹temp = myStack.top();myStack.pop();visit(temp);temp = temp->rightChild;}} }/*** 先序遍歷二叉樹(遞歸算法)* @param binaryTree*/ void PreOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {visit(binaryTree);PreOrderTraversal(binaryTree->leftChild);PreOrderTraversal(binaryTree->rightChild);} }/*** 先序遍歷（非遞歸）* @param binaryTree*/ void PreOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//初始化棧stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指針進棧，遍歷左子樹if (temp != NULL) {visit(temp);myStack.push(temp);temp = temp->leftChild;} else {//根指針退棧，訪問根節點，遍歷右子樹temp = myStack.top();myStack.pop();temp = temp->rightChild;}} }/*** 后序遍歷二叉樹（遞歸算法）* @param binaryTree*/ void PostOrderTraversal(BinaryTree binaryTree) {if (binaryTree) {PostOrderTraversal(binaryTree->leftChild);PostOrderTraversal(binaryTree->rightChild);visit(binaryTree);} }/** 要保證根結點在左孩子和右孩子訪問之后才能訪問，因此對于任一結點P，* 先將其入棧。如果P不存在左孩子和右孩子，則可以直接訪問它；* 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。* 若非上述兩種情況，則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，* 左孩子在右孩子前面被訪問，左孩子和右孩子都在根結點前面被訪問。*/ void PostOrderTraversalNO(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}BinaryTree temp = binaryTree;stack<BinaryTreeNode *> myStack;//當前結點BinaryTree current;//前一次訪問的結點BinaryTree pre = NULL;myStack.push(binaryTree);while (!myStack.empty()) {current = myStack.top();if ((current->leftChild == NULL && current->rightChild == NULL) ||(pre != NULL && (pre == current->leftChild || pre == current->rightChild))) {//如果當前結點沒有孩子結點或者孩子節點都已被訪問過visit(current);myStack.pop();pre = current;} else {if (current->rightChild != NULL) {myStack.push(current->rightChild);}if (current->leftChild != NULL) {myStack.push(current->leftChild);}}} }char ch; bool flag;void findpath(BinaryTree binaryTree, char x, vector<char> &v) {if (binaryTree == NULL) {return;}v.push_back(binaryTree->data);if (binaryTree->data == x) {flag = 1;for (int i = 0; i < v.size(); i++) {putchar(v[i]);}putchar(10);return;}findpath(binaryTree->leftChild, x, v);findpath(binaryTree->rightChild, x, v);v.pop_back(); }/*** 二叉樹的層序遍歷* @param binaryTree*/ void levelOrderTraversal(BinaryTree binaryTree) {if (binaryTree == NULL) {return;}//定義使用的隊列queue<BinaryTreeNode *> myQueue;BinaryTree temp = binaryTree;//根節點入隊myQueue.push(temp);//隊列不為空的時候循環while (!myQueue.empty()) {//隊頭元素出隊temp = myQueue.front();myQueue.pop();//訪問temp指向的節點visit(temp);//左子樹不為空，入隊左子樹if (temp->leftChild != nullptr) {myQueue.push(temp->leftChild);}//右子樹不為空，入隊右子樹if (temp->rightChild != nullptr) {myQueue.push(temp->rightChild);}} }/*** 獲取雙分支節點的個數* @param binaryTree*/ int PreOrderTraversalGet2(BinaryTree binaryTree) {if (binaryTree == NULL) {return 0;}int number = 0;//初始化棧stack<BinaryTreeNode *> myStack;BinaryTree temp = binaryTree;while (temp != NULL || !myStack.empty()) {//根指針進棧，遍歷左子樹if (temp != NULL) {if (temp->rightChild != NULL && temp->leftChild != NULL) {number++;}myStack.push(temp);temp = temp->leftChild;} else {//根指針退棧，訪問根節點，遍歷右子樹temp = myStack.top();myStack.pop();temp = temp->rightChild;}}return number; }/*** 求二叉樹的深度* @param binaryTree* @return*/ int postOrderGetHeight(BinaryTree binaryTree) {if (binaryTree) {//求左子樹的深度int leftHeight = postOrderGetHeight(binaryTree->leftChild);//求右子樹的深度int rightHeight = postOrderGetHeight(binaryTree->rightChild);int max = leftHeight > rightHeight ? leftHeight : rightHeight;return max + 1;} else {return 0;} }/*如果需要構建一顆如下所示的二叉樹：AB CD F G IE H 輸入ABD**FE***CG*H**I**即可創建該二叉樹**/ int main() {BinaryTree binaryTree = NULL;createTree(&binaryTree);cout << "中序遍歷：（遞歸）" << endl;InOrderTraversal(binaryTree);cout << endl;cout << "中序遍歷：（非遞歸）" << endl;InOrderTraversalNO(binaryTree);cout << endl;cout << "先序遍歷：（遞歸）" << endl;PreOrderTraversal(binaryTree);cout << endl;cout << "先序遍歷：（非遞歸）" << endl;PreOrderTraversalNO(binaryTree);cout << endl;cout << "后序遍歷：（遞歸）" << endl;PostOrderTraversal(binaryTree);cout << endl;cout << "后序遍歷：（非遞歸）" << endl;PostOrderTraversalNO(binaryTree);cout << endl;cout << "層序遍歷：" << endl;levelOrderTraversal(binaryTree);cout << endl;cout << "二叉樹的深度：" << postOrderGetHeight(binaryTree) << endl;cout << "二叉樹的中雙分支節點的個數為：" << PreOrderTraversalGet2(binaryTree) << endl;char x;cout << "請輸入查找路徑字符：";cin >> x;vector<char> v;cout << "根節點到" << x << "的路徑為：";findpath(binaryTree, x, v);cout << endl;return 0; }

總結

以上是生活随笔為你收集整理的二叉树的创建和遍历-C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。