手机百度搜索重庆seo服务

     “二叉树”作为特殊的树，适合于计算机处理，所以二叉树是研究的重点。我们通常将满足下列的条件称为二叉树，每个节点的度都不大于2，每个节点的孩子节点次序不能任意颠倒。也就是说，一个二叉树中的每个节点只能含有0,1或2个孩子，而且每个孩子有左右孩子之分，位于左边的孩子称为左孩子，位于右边的孩子称为右孩子。说到二叉树：就需要提到“满二叉树”和“完全二叉树”。

        满二叉树：在满二叉树中，每层节点都是满的，即每层节点都具有最大节点数。

        完全二叉树：深度为k，节点数为n的二叉树，即就是节点1-n的位置序号分别与满二叉树的节点1~n的位置序号一一对应。

       二叉树的存储有两种方式，顺序存储结构，链式存储结构，这里主要讨论的是二叉树的顺序存储方式，下面为简单的图示：

      下面主要讨论二叉树的三种遍历，前序（根-左-右）、中序（左-根-右）、后序（左-右-根）的递归和非递归的方式，还有针对二叉树的一些操作：

—BinaryTree.h文件#pragma once
#include <queue>
#include <stack>
#include <assert.h>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
{typedef BinaryTreeNode<T> Node;
public:BinaryTree()     //无参构造:_root(NULL){ }BinaryTree(const T* arr, size_t size, const T& invalid)  //有参构造{size_t index = 0;_root = _CreateTree(arr, size, index, invalid);}BinaryTree(const BinaryTree<T>& t)     //拷贝构造{_root = _copy(t._root);}//Node& operator=(const Node& t)     //赋值运算符重载//{// if (this != &t)// {//      Node* tmp = _copy(t._root);//      _Destroy(_root);//      _root = tmp;// }// return *this;//}Node& operator=(Node t){swap(this->_root, t._root);return *this;}~BinaryTree()    //析构函数(后序){_Destroy(_root);_root = NULL;}public:Node* _CreateTree(const T* arr, size_t size, size_t& index, const T& invalid)  //构造二叉树{Node* root = NULL;if ((index < size) && (arr[index] != invalid)){root = new Node(arr[index]);root->_left = _CreateTree(arr, size, ++index, invalid);   root->_right = _CreateTree(arr, size, ++index, invalid);//不能使用index+1（没有更改index值，不能递归），不能使用index++（返回的是index的临时变量）}_root = root;return _root;}void PrevOrder()   //前序遍历二叉树{_PrevOrder(_root);}void InOrder()     //中序遍历二叉树{_InOrder(_root);}void BackOrder()    //后序遍历二叉树{_BackOrder(_root);}void PrevOrder_NonR()     //前序(非递归实现，利用栈)  根-左-右{stack<Node*> S;S.push(_root);while (!S.empty()){Node* tmp = S.top();cout << tmp->_data << " ";S.pop();if (tmp->_right != NULL){S.push(tmp->_right);}if (tmp->_left != NULL){S.push(tmp->_left);}}cout << endl;}void InOrder_NonR()    //中序遍历（非递归）左-根-右{Node* cur = _root;stack<Node*> S;while (cur || !S.empty())   //当cur指向不为空，或者栈不为空时，则树没有遍历完成{while (cur)         //将树的左节点进行压栈，直到最左的节点{S.push(cur);cur = cur->_left;}if (!S.empty())        //当S栈中不为空时，证明此时还没有访问到根节点{Node* tmp = S.top();S.pop();cout << tmp->_data << " ";cur = tmp->_right;}}cout << endl;}void BackOrder_NonR()        //后序遍历（非递归）左-右-根{Node* prev = NULL;Node* cur = _root;stack<Node*> S;while (cur || !S.empty()){while (cur){S.push(cur);cur = cur->_left;}Node* tmp = S.top();if (tmp->_right == NULL || tmp->_right == prev){cout << tmp->_data << " ";S.pop();prev = tmp;}else{cur = tmp->_right;}}cout << endl;}size_t size()      //二叉树的节点个数{return _size(_root);}size_t Depth()     //二叉树的深度{return _Depth(_root);}size_t LeafSize()     //二叉树叶子节点个数{return _LeafSize(_root);}void LevelOrder()       //二叉树的层次遍历{if (_root == NULL){return;}queue<Node*> Q;      //将节点插入队列中Q.push(_root);while (!Q.empty()){cout << Q.front()->_data << " ";//Q.pop();if (Q.front()->_left != NULL){Q.push(Q.front()->_left);}if (Q.front()->_right != NULL){Q.push(Q.front()->_right);}Q.pop();}}size_t GetKLevel(int k)     //得到树第k层的节点个数{assert(k >= 1);return _GetKLevel(_root, k);}protected: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 _BackOrder(Node* root)    //后序{if (root == NULL){return;}_BackOrder(root->_left);_BackOrder(root->_right);cout << root->_data << " ";}size_t _size(Node* root)         //节点个数{if (root == NULL){return 0;}return _size(root->_left) + _size(root->_right) + 1;}size_t _Depth(Node* root)     //深度{if (root == NULL){return 0;}int leftDepth = _Depth(root->_left);int rightDepth = _Depth(root->_right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}size_t _LeafSize(Node* root)    //叶子节点个数{if (root == NULL){return 0;}size_t size = 0;if (root->_left == NULL && root->_right == NULL){return 1;}return _LeafSize(root->_left) + _LeafSize(root->_right);}//size_t _LeafSize(Node* root)    //叶子节点个数//{//     static size_t size = 0;//     if (root == NULL)//     {//          return 0;//     }//     if (root->_left == NULL && root->_right == NULL)//     {//          size++;//          return size;//     }//     _LeafSize(root->_left);//     _LeafSize(root->_right);//     return size;//}size_t _GetKLevel(Node* root, int k)    //得到第k层树的节点{if (root == NULL){return 0;}if (k == 1){return 1;}return _GetKLevel(root->_left, (k - 1)) + _GetKLevel(root->_right, k - 1);}Node* _copy(Node* root)    //前序拷贝（递归）{if (root == NULL){return NULL;}Node* newroot = new Node(root->_data);newroot->_left = _copy(root->_left);newroot->_right = _copy(root->_right);return newroot;}void _Destroy(Node* root)     //删除所有节点(后序){if (root == NULL){return;}_Destroy(root->_left);_Destroy(root->_right);delete[] root;}protected:BinaryTreeNode<T>* _root;
};