小朋友學數據結構（3）：二叉樹的建立和遍歷

一、基本概念

BinaryTree.png

二叉樹：每個結點的子結點個數不大于2的樹，叫做二叉樹。
根結點：最頂部的那個結點叫做根結點，根結點是所有子結點的共同祖先。比如上圖中的“7”結點就是根結點。
子結點：除了根結點外的結點，都叫子結點。
葉子結點：沒有子結點的結點，叫做葉子結點。比如上圖中的“1”結點、“5”結點和“11”結點。

二叉樹的遍歷，有三種：
（1）前序遍歷：先遍歷根結點，再遍歷左子樹，最后遍歷右子樹。上圖的前序遍歷順序為：7->4->1->5->12->8->11->13
（2）中序遍歷：先遍歷左子樹，再遍歷根結點，最后遍歷右子樹。上圖的中序遍歷順序為：1->4->5->7->8->11->12->13
（3）后序遍歷：先遍歷左子樹，再遍歷右子樹，最后遍歷根結點。上圖的后序遍歷順序為：1->5->4->11->8->13->12->7

二叉排序樹：左子結點 <= 根結點 <= 右子結點的二叉樹，叫做二叉排序樹（或排序二叉樹）。上圖就是一個二叉排序樹。

二、二叉樹的建立和遍歷

#include<iostream> using namespace std; struct BTreeNode //定義二叉樹結點的數據結構 { int data; BTreeNode *leftChild; //左子結點指針 BTreeNode *rightChild; //右子結點指針 }; class Btree { private: //private可以不寫，因為默認就是private BTreeNode *root; //根結點的指針 void preOrderTraverse(BTreeNode *); //前序遍歷具體過程，內部接口 void inOrderTraverse(BTreeNode *); //中序遍歷具體過程，內部接口 void postOrderTraverse(BTreeNode *);//后序遍歷具體過程，內部接口 public: Btree() //構造函數 { root = NULL; } void createBtree(int); void preOrder() //前序遍歷方法，對外接口 { preOrderTraverse(root); } void inOrder() //中序遍歷方法，對外接口 { inOrderTraverse(root); } void postOrder() //后序遍歷方法，對外接口 { postOrderTraverse(root); } }; void Btree::createBtree(int x) { BTreeNode *newnode = new BTreeNode; newnode->data = x; newnode->leftChild = NULL; newnode->rightChild = NULL; if(NULL == root) //如果沒有根結點，則第一個結點就是根結點 { root = newnode; } else //根據數值大小判斷是左子結點還是右子結點 { BTreeNode *father; BTreeNode *current = root; while(current != NULL) //找到要插入newnode的節點指針 { father = current; if(current->data > x) { current = current->leftChild; } else { current = current->rightChild; } } //newnode插入到father結點的左（或右）子結點位置 if(father->data > x) { father->leftChild = newnode; } else { father->rightChild = newnode; } } } void Btree::preOrderTraverse(BTreeNode *root) { if(root) { cout << root->data << " "; preOrderTraverse(root->leftChild); preOrderTraverse(root->rightChild); } } void Btree::inOrderTraverse(BTreeNode *root) { if(root) { inOrderTraverse(root->leftChild); cout << root->data << " "; inOrderTraverse(root->rightChild); } } void Btree::postOrderTraverse(BTreeNode *root) { if(root) { postOrderTraverse(root->leftChild); postOrderTraverse(root->rightChild); cout << root->data << " "; } } int main() { Btree btree; int a[] = {7, 4, 1, 5, 12, 8, 13, 11}; //排序二叉樹：左子結點<根節點<右子節點 cout << "建立排序二叉樹: "; int cnt = sizeof(a) / sizeof(int); for(int i = 0; i < cnt; i++) { cout << a[i] << " "; btree.createBtree(a[i]); } cout << endl; cout << "前序遍歷: "; btree.preOrder(); cout << endl; cout << "中序遍歷: "; btree.inOrder(); cout << endl; cout << "后序遍歷: "; btree.postOrder(); cout << endl; return 0; }

運行結果：

建立排序二叉樹： 7 4 1 5 12 8 13 11 前序遍歷：7 4 1 5 12 8 11 13 中序遍歷：1 4 5 7 8 11 12 13 后序遍歷：1 5 4 11 8 13 12 7

?

轉載于:https://www.cnblogs.com/alan-blog-TsingHua/p/9607574.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的小朋友学数据结构（3）：二叉树的建立和遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

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