BinaryTree

BinaryTree 一、介绍在前面        二叉树结构是学习数据结构的一大重点，是学习后面的搜索二叉树、AVL树、红黑树等的基础（后面会一一介绍）。        二叉树的应用也很多，比如可以帮助我们做排序的工作，提高查找数据的速度；二叉树基础的优化能不断优化我们系统的结构；在海量数据处理方面也有很大的运用，是优先级队列的雏形。       本文实现的是二叉树的一些基本操作：             （1）用递归方法和非递归方法实现前、中、后序的遍历             （2）求取节点的个数             （3）求取叶子节点的个数             （4）求取深度             （5）查找一个节点             （6）求取第K层的数据             （7）层序遍历 二、二叉树中节点的结构 第一种：包括左孩子、右孩子、数据 template<class T> struct BinaryTreeNode { T _data; BinaryTreeNode<T>* _leftchild; BinaryTreeNode<T>* _rightchild; }; 第二种：包括左孩子、右孩子和父亲 template<class T> struct BinaryTreeNode { T _data; BinaryTreeNode<T>* _leftchild; BinaryTreeNode<T>* _rightchild; BinaryTreeNode<T>* _parent; }; 三、遍历           （1）递归前序遍历                      DLR-->先遍历当前节点，再遍历左孩子，最后遍历右孩子，以上图为例：1 2 4 5 3 6 7           （2）递归中序遍历                     LDR-->先遍历左孩子，再遍历当前节点，最后遍历右孩子，以上图为例：4 2 5 1 6 3 7           （3）递归后序遍历                     LRD-->先遍历左孩子，再遍历右孩子，最后遍历当前节点，以上图为例：4 5 2 6 7 3 1           （4）层序遍历                     一层一层的遍历，借助队列（先进先出），将当前节点push进队列，pop当前节点，再push左孩子，pop左孩子；push右孩子，pop右孩子。            非遍历的前、中、后序遍历原理与递归相同，本文是借助栈（stack）实现的，详情见代码。 四、基本操作             （1）树的深度（高度）                       只有一个节点是，深度记为1，树的深度等于左孩子和右孩子深度的较大者加1             （2）节点的个数                     节点个数等于左孩子节点个数加上右孩子节点个数再加1            （3）叶子节点个数                      叶子节点个数等于左孩子叶子节点个数加上右孩子节点个数            （4）第K层的数据                      递归，找到第K层遍历            （5）查找一个节点                      遍历查找 五、代码 #pragma once #include<iostream> #include<stack> #include<queue> #include<assert.h> using namespace std; template<class T> struct BinaryTreeNode { T _data; BinaryTreeNode<T>* _leftchild; BinaryTreeNode<T>* _rightchild; BinaryTreeNode(const T& x) :_data(x) , _leftchild(NULL) , _rightchild(NULL) {} }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree(const T* a, size_t size,const T& invalid) { size_t index = 0; _root = _CreateTree(a, size, invalid,index); } BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); } BinaryTree<T>& operator=(const BinaryTree<T>& t) { if (this != &t) { Node* newnode = _Copy(t._root); _Destroy(_root); _root = newnode; } return *this; } ~BinaryTree() { _Destroy(_root); } void PrevOrder()//先序遍历 { _PrevOrder(_root); } void InOrder()//递归中序遍历 { _InOrder(_root); } void PostOrder()//递归后序遍历 { _PostOrder(_root); } void LevelOrder()//递归层序遍历 { _LevelOrder(_root); } size_t Size()//节点的个数 { size_t count = 0; return _Size(_root, count); } size_t Depth()//深度 { //size_t count = 0; return _Depth(_root); } size_t LeafSize()//叶节点的个数 { return _LeafSize(_root); } size_t GetKLevel(size_t k)//打印第k层的数据的个数 { assert(k > 0); return _GetKLevel(_root, k); } Node* Find(const T& x)//找一个节点 { return _Find(_root, x); } void PrevOrderNonR()//非递归前序遍历 { Node* cur = _root; stack<Node*> s; while (cur || !s.empty()) { while (cur) { s.push(cur); cout << cur->_data << " "; cur = cur->_leftchild; } Node* top = s.top(); s.pop(); cur = top->_rightchild; } cout << endl; } void InOrderNonR()//非递归中序遍历 { Node* cur = _root; stack<Node*> s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_leftchild; } Node* top = s.top(); cout << top->_data << " "; s.pop(); cur = top->_rightchild; } cout << endl; } void PostOrderNonR()//非递归后序遍历 { Node* cur = _root; Node* prev = NULL; stack<Node*> s; while (cur||!s.empty()) { while (cur) { s.push(cur); cur = cur->_leftchild; } Node* top = s.top(); if (top->_rightchild == NULL||top->_rightchild == prev) { cout << top->_data << " "; prev = top; s.pop(); } cur = top->_rightchild; } cout << endl; } protected: void _Copy(Node* root) { Node* newnode = new Node(root->_data); newnode->_leftchild = root->_leftchild; newnode->_rightchild = root->_rightchild; } void Destroy(Node* root) { if (root == NULL) return; delete root->_leftchild; delete root->_rightchild; delete root; } Node* _Find(Node* root, const T& x) { if (root == NULL) return NULL; if (root->_data == x) return root; Node* ret = _Find(root->_leftchild, x); if (ret) return ret; return _Find(root->_rightchild, x); } size_t _GetKLevel(Node* root, size_t K) { if (root == NULL) return 0; if (K == 1) return 1; return _GetKLevel(root->_leftchild, K - 1) + _GetKLevel(root->_rightchild, K - 1); } size_t _LeafSize(Node* root) { if (root == NULL) return 0; if (root->_leftchild == NULL&&root->_rightchild == NULL) return 1; return _LeafSize(root->_leftchild) + _LeafSize(root->_rightchild); } size_t _LeafSize(Node* root, size_t& count) { if (root == NULL) return 0; if (root->_leftchild == NULL && root->_rightchild == NULL) ++count; _LeafSize(root->_leftchild, count); _LeafSize(root->_rightchild, count); return count; } size_t _Depth(Node* root) { if (root == NULL) { return 0; } size_t left = _Depth(root->_leftchild); size_t right = _Depth(root->_rightchild); return left >= right ? left + 1 : right + 1; } Node* _CreateTree(const T* a, size_t size, const T& invalid,size_t &index) { Node* root = NULL; if (index < size && a[index] != invalid) { root = new Node(a[index]); root->_leftchild = _CreateTree(a, size, invalid,++index); root->_rightchild = _CreateTree(a, size,invalid, ++index); } return root; } void _PrevOrder(Node* root) { if (root == NULL) { return; } cout << root->_data << " "; _PrevOrder(root->_leftchild); _PrevOrder(root->_rightchild); } void _InOrder(Node* root) { if (root == NULL) { return; } _InOrder(root->_leftchild); cout << root->_data << " "; _InOrder(root->_rightchild); } void _PostOrder(Node* root) { if (root == NULL) { return; } _PostOrder(root->_leftchild); _PostOrder(root->_rightchild); cout << root->_data << " "; } void _LevelOrder(Node* root) { if (root == NULL) { return; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* front = q.front(); cout << front->_data << " "; q.pop(); if (front->_leftchild) { q.push(front->_leftchild); } if (front->_rightchild) { q.push(front->_rightchild); } } } size_t _Size(Node* root, size_t& count) { if (root == NULL) { return 0; } return _Size(root->_leftchild, ++count) + _Size(root->_rightchild, ++count) + 1; } protected: Node* _root; }; void TEST() { int a[12] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6, '#', '#' }; BinaryTree<int> bt(a, 12,'#'); //bt.PrevOrder(); //cout << endl; //bt.InOrder(); //cout << endl; //bt.PostOrder(); //cout << endl; //bt.LevelOrder(); //cout << endl; //bt.PrevOrderNonR(); //bt.InOrderNonR(); //bt.PostOrderNonR(); //cout << "Size=" << bt.Size() << endl; //cout << "Depth()=" << bt.Depth() << endl; //cout << "LeafSize()=" << bt.LeafSize() << endl; //cout << "GetKLevel()=" << bt.GetKLevel(2) << endl; //cout << "Find()="<<bt.Find(2)->_data << endl; }