二叉树实现
#pragma once #include <queue> #include <stack> using namespace std; template<class T> struct BinaryTreeNode //树节点 { T _data; BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {} }; template<class T> class BinaryTree { public: BinaryTree() :_root(NULL) {} BinaryTree(const T* a, size_t size) { size_t index = 0; _root = _CreateTree(a, size, index); } ~BinaryTree() { _Destroy(_root); _root = NULL; } BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); } BinaryTree<T>& operator=(BinaryTree<T> t) { swap(_root, t._root); return *this; } void PrevOrder() { _PrevOrder(_root); cout << endl; } void InOrder() { _InOrder(_root); cout << endl; } void PostOrder() { _PostOrder(_root); cout << endl; } //二叉树的层次遍历 void LevelOrder() { queue<BinaryTreeNode<T>*> q; //定义一个队列q if (_root) //判断_root是否为空 { q.push(_root); } while (!q.empty()) { BinaryTreeNode<T>* front = q.front(); q.pop(); cout << front->_data << " "; if (front->_left) //由左向右依次进入队列,依次输出 { q.push(front->_left); } if (front->_right) { q.push(front->_right); } } cout << endl; } int Size() { int size = 0; _Size(_root, size); return size; } int Depth() { return _Depth(_root); } BinaryTreeNode<T>* Find(const T& x) { return _Find(_root, x); } //二叉树前序遍历 void PrevOrder_NonR() { stack<BinaryTreeNode<T>*> s; if (_root) { s.push(_root); //将树入栈 } while (!s.empty()) //栈不为空,根节点先出栈 { BinaryTreeNode<T>* top = s.top(); s.pop(); cout << top->_data << " "; if (top->_right) //压入右子树 { s.push(top->_right); } if (top->_left) //压入左子树 { s.push(top->_left); } } cout << endl; } void InOrder_NonR() { stack<BinaryTreeNode<T>*> s; BinaryTreeNode<T>* cur = _root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } if (!s.empty()) { BinaryTreeNode<T>* top = s.top(); cout << top->_data << " "; s.pop(); cur = top->_right; } } cout << endl; } void PostOrder_NonR() { stack<BinaryTreeNode<T>*> s; BinaryTreeNode<T>* cur = _root; BinaryTreeNode<T>* prevVisited = NULL; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } BinaryTreeNode<T>* top = s.top(); if (top->_right == NULL || top->_right == prevVisited) { cout << top->_data << " "; prevVisited = top; s.pop(); } else { cur = top->_right; } } cout << endl; } int GetLeafNum() { int num = 0; _GetLeafNum(_root, num); return num; } protected: BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root) { if (root == NULL) { return NULL; } BinaryTreeNode<T>* newRoot = new BinaryTreeNode<T>(root->_data); newRoot->_left = _Copy(root->_left); newRoot->_right = _Copy(root->_right); return newRoot; } void _Destroy(BinaryTreeNode<T>*& root) { if (root == NULL) { return; } if (root->_left == NULL && root->_right == NULL) { delete root; root = NULL; return; } _Destroy(root->_left); _Destroy(root->_right); delete root; } BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index) { BinaryTreeNode<T>* root = NULL; if (index < size && a[index] != ‘#‘) { root = new BinaryTreeNode<T>(a[index]); root->_left = _CreateTree(a, size, ++index); root->_right = _CreateTree(a, size, ++index); } return root; } void _PrevOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void _InOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void _PostOrder(BinaryTreeNode<T>* root) { if (root == NULL) { return; } _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } void _Size(BinaryTreeNode<T>* root, int& size) { if (root == NULL) { return; } else { size++; } _Size(root->_left, size); _Size(root->_right, size); } int _Depth(BinaryTreeNode<T>* root) { if (root == NULL) { return 0; } int leftDepth = _Depth(root->_left); int rightDepth = _Depth(root->_right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } BinaryTreeNode<T>* _Find(BinaryTreeNode<T>* root, const T& x) { if (root == NULL) { return NULL; } else if (root->_data == x) { return root; } else { BinaryTreeNode<T>* ret = _Find(root->_left, x); if (ret) { return ret; } else { return _Find(root->_right, x); } } } void _GetLeafNum(BinaryTreeNode<T>* root, int& num) { if (root == NULL) { return; } if (root->_left == NULL&&root->_right == NULL) { ++num; return; } _GetLeafNum(root->_left, num); _GetLeafNum(root->_right, num); } protected: BinaryTreeNode<T>* _root; }; 简单测试: s void Test1() { int a[10] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘, ‘#‘, 5, 6 }; BinaryTree<int>t1(a, 10); t1.PrevOrder(); t1.InOrder(); t1.PostOrder(); t1.LevelOrder(); cout << "size:" << t1.Size() << endl; cout << "depth:" << t1.Depth() << endl; int b[15] = { 1, 2, ‘#‘, 3, ‘#‘, ‘#‘, 4, 5, ‘#‘, 6, ‘#‘, 7, ‘#‘, ‘#‘, 8 }; BinaryTree<int>t2(b, 15); t2.PrevOrder(); cout << "size:" << t2.Size() << endl; cout << "depth:" << t2.Depth() << endl; cout << t2.Find(8)->_data << endl; cout << t2.Find(6)->_data << endl; t2.PrevOrder(); t2.PrevOrder_NonR(); t2.InOrder(); t2.InOrder_NonR(); t2.PostOrder(); t2.PostOrder_NonR(); cout << "叶子节点的个数:" << t2.GetLeafNum() << endl; }
本文出自 “木木侠” 博客,谢绝转载!
原文:http://10324228.blog.51cto.com/10314228/1757214