樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，二叉樹是樹型結(jié)構(gòu)的一種重要類型。本學(xué)年論文介紹了二叉樹的定義，二叉樹的存儲結(jié)構(gòu)，二叉樹的相關(guān)術(shù)語，以此引入二叉樹這一概念，為展開二叉樹的基本操作做好理論鋪墊。二叉樹的基本操作主要包含以下幾個模塊：二叉樹的遍歷方法，計算二叉樹的結(jié)點個數(shù)，計算二叉樹的葉子結(jié)點個數(shù)，二叉樹深度的求解等內(nèi)容。
前序遍歷（遞歸&非遞歸）
//前序非遞歸 void PrevOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { cout << cur->_data << " "; s.push(cur); cur = cur->_left; } //此時當(dāng)前節(jié)點的左子樹已遍歷完畢 Node *tmp = s.top(); s.pop(); cur = tmp->_right; } cout << endl; } //前序遞歸 void PrevOrderR() { _PrevOrder(_root); cout << endl; } void _PrevOrder(Node *root) { if (root == NULL) //必須有遞歸出口！！！ return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); }中序遍歷（遞歸&非遞歸）
//中序非遞歸 void InOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } //此時當(dāng)前節(jié)點的左子樹已遍歷完畢 Node *tmp = s.top(); cout << tmp->_data << " "; s.pop(); cur = tmp->_right; } cout << endl; } //中序遞歸 void InOrderR() { _InOrder(_root); cout << endl; } void _InOrder(Node *root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); }后序遍歷（遞歸&非遞歸）
//后序非遞歸 //后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點 void PostOrder() { stack<Node*> s; Node *cur = _root; Node *prev = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node *tmp = s.top(); if (tmp->_right && tmp->_right != prev) { cur = tmp->_right; } else { cout << tmp->_data << " "; prev = tmp; s.pop(); } } cout << endl; } //后序遞歸 void PostOrderR() { _PostOrder(_root); cout << endl; } void _PostOrder(Node *root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; }層序遍歷
從根節(jié)點開始，依次訪問每層結(jié)點。
利用隊列先進(jìn)先出的特性，把每層結(jié)點從左至右依次放入隊列。
void LevelOrder() //利用隊列！！！ { queue<Node*> q; Node *front = NULL; //1.push根節(jié)點 if (_root) { q.push(_root); } //2.遍歷當(dāng)前節(jié)點，push當(dāng)前節(jié)點的左右孩子，pop當(dāng)前節(jié)點 //3.遍歷當(dāng)前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空 while (!q.empty()) { front = q.front(); cout << front->_data << " "; if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); q.pop(); } cout << endl; }求二叉樹的高度
size_t Depth() { return _Depth(_root); } size_t _Depth(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else { size_t leftDepth = _Depth(root->_left) + 1; size_t rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } }求葉子節(jié)點的個數(shù)
size_t LeafSize() { return _LeafSize(_root); } size_t _LeafSize(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); }求二叉樹第k層的節(jié)點個數(shù)
size_t GetKLevel(int k) { return _GetKLevel(_root, k); } size_t _GetKLevel(Node *root, int k) { if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); }完整代碼如下：
template<class T>struct BinaryTreeNode{ T _data; BinaryTreeNode *_left; BinaryTreeNode *_right; BinaryTreeNode(const T& d) :_data(d) , _left(NULL) , _right(NULL) {}};template<class T>class BinaryTree{public: typedef BinaryTreeNode<T> Node; BinaryTree() :_root(NULL) {} BinaryTree(T *arr, size_t n, const T& invalid) { size_t index = 0; _root = _CreateBinaryTree(arr, n, invalid, index); } BinaryTree(const BinaryTree<T>& t) :_root(NULL) { _root = _CopyTree(t._root); } BinaryTree<T>& operator=(const BinaryTree<T>& t) { if (this != t) { Node *tmp = new Node(t._root); if (tmp != NULL) { delete _root; _root = tmp; } } return *this; } ~BinaryTree() { _DestroyTree(_root); cout << endl; } //前序非遞歸 void PrevOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { cout << cur->_data << " "; s.push(cur); cur = cur->_left; } //此時當(dāng)前節(jié)點的左子樹已遍歷完畢 Node *tmp = s.top(); s.pop(); cur = tmp->_right; } cout << endl; } //前序遞歸 void PrevOrderR() { _PrevOrder(_root); cout << endl; } //中序非遞歸 void InOrder() { stack<Node*> s; Node *cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } //此時當(dāng)前節(jié)點的左子樹已遍歷完畢 Node *tmp = s.top(); cout << tmp->_data << " "; s.pop(); cur = tmp->_right; } cout << endl; } //中序遞歸 void InOrderR() { _InOrder(_root); cout << endl; } //后序非遞歸 //后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點 void PostOrder() { stack<Node*> s; Node *cur = _root; Node *prev = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node *tmp = s.top(); if (tmp->_right && tmp->_right != prev) { cur = tmp->_right; } else { cout << tmp->_data << " "; prev = tmp; s.pop(); } } cout << endl; } //后序遞歸 void PostOrderR() { _PostOrder(_root); cout << endl; } void LevelOrder() //利用隊列！！！ { queue<Node*> q; Node *front = NULL; //1.push根節(jié)點 if (_root) { q.push(_root); } //2.遍歷當(dāng)前節(jié)點，push當(dāng)前節(jié)點的左右孩子，pop當(dāng)前節(jié)點 //3.遍歷當(dāng)前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空 while (!q.empty()) { front = q.front(); cout << front->_data << " "; if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); q.pop(); } cout << endl; } size_t Size() { return _Size(_root); } size_t LeafSize() { return _LeafSize(_root); } size_t GetKLevel(int k) { return _GetKLevel(_root, k); } size_t Depth() { return _Depth(_root); } Node* Find(const T& d) { return _Find(_root, d); }protected: Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index) { Node *root = NULL; if (index < n && arr[index] != invalid) { root = new Node(arr[index]); index++; root->_left = _CreateBinaryTree(arr, n, invalid, index); index++; root->_right = _CreateBinaryTree(arr, n, invalid, index); } return root; } Node* _CopyTree(Node *root) { Node *newRoot = NULL; if (root) { newRoot = new Node(root->_data); newRoot->_left = _CopyTree(root->_left); newRoot->_right = _CopyTree(root->_right); } return newRoot; } void _DestroyTree(Node *root) { if (root) { _Destroy(root->_left); _Destroy(root->_right); delete root; } } void _PrevOrder(Node *root) { if (root == NULL) //必須有遞歸出口！！！ return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void _InOrder(Node *root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void _PostOrder(Node *root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } size_t _Size(Node *root) { if (root == NULL) return 0; else return _Size(root->_left) + _Size(root->_right) + 1; } size_t _LeafSize(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); } size_t _GetKLevel(Node *root, int k) { if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); } size_t _Depth(Node *root) { if (root == NULL) return 0; else if (root->_left == NULL && root->_right == NULL) return 1; else { size_t leftDepth = _Depth(root->_left) + 1; size_t rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } } Node* _Find(Node *root, const T& d) { if (root == NULL) return NULL; else if (root->_data == d) return root; else if (Node *ret = _Find(root->_left, d)) return ret; else _Find(root->_right, d); }protected: Node *_root;};以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持武林網(wǎng)。
新聞熱點
疑難解答
