完全二叉树

完全二叉树是一种特殊的二叉树，它的性质是：

1. 对于任意一个节点，如果它有左子树，则一定有右子树。
2. 在一颗有n个节点的完全二叉树中，除了最后一层外，其他层的节点数都是满的，最后一层的节点都靠左排列。
3. 任何一个节点，如果该节点编号为n，则该节点的父节点的编号是（n - 1）/ 2
4. 任何一个节点，如果该节点编号为n，则该节点的左子节点的编号是 2*n+1
5. 任何一个节点，如果该节点编号为n，则该节点的右子节点的编号是 2*n+2
6. 完全二叉树的深度为k，最多有2^k-1个节点。

完全二叉树的性质可以帮助我们快速查找完全二叉树中的节点，也可以帮助我们判断一颗二叉树是否为完全二叉树。

下面是一颗完全二叉树的示意图：

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

在这颗完全二叉树中，每一层的节点都是满的，最后一层的节点都靠左排列。

完全二叉树的实现并不难，根据结点与结点之间的性质很容易找到插入点。

完全二叉树的实现、

#include<iostream>
using namespace std;

#include<stack>
#include<queue>
#include<vector>

//完全二叉树节点设计
class CBT_Tree_Node
{
public:
	CBT_Tree_Node(int data = 0):data(data){}
	CBT_Tree_Node* left = nullptr;
	CBT_Tree_Node* right = nullptr;
	int data = 0;
};

//完全二叉树设计
class CBT_Tree
{
public:

	CBT_Tree():_root(nullptr){}

	~CBT_Tree()noexcept
	{
		clear();
	}

	void clear()noexcept
	{
		for (CBT_Tree_Node* node : v)
		{
			delete node;
			node = nullptr;
		}
		v.resize(0);
		_root = nullptr;
	}

	size_t size()const
	{
		return v.size();
	}

	void insert(int data)
	{
		if (_root == nullptr)
		{
			_root = new CBT_Tree_Node{ data };
			v.push_back(_root);
			return;
		}

                //根据完全二叉树的性质来找到插入点
		CBT_Tree_Node* new_node = new CBT_Tree_Node{ data };
		CBT_Tree_Node* parent = v[(v.size() - 1) / 2];
		if (!parent->left)
		{
			parent->left = new_node;
		}
		else if (!parent->right)
		{
			parent->right = new_node;
		}
		v.push_back(new_node);
	}

	CBT_Tree_Node* find(int data)
	{
		for (const CBT_Tree_Node* node : v)
		{
			if (node->data == data)
			{
				return node;
			}
		}
		return nullptr;
	}

	size_t height()const
	{
		return _height_(_root);
	}

	void BFS()const
	{
		if (_root == nullptr)
		{
			return;
		}
		queue<CBT_Tree_Node*> q{};
		q.push(_root);
		CBT_Tree_Node* tmp = nullptr;
		while (!q.empty())
		{
			tmp = q.front();
			q.pop();
			cout << tmp->data << "  ";
			if (tmp->left)
			{
				q.push(tmp->left);
			}
			if (tmp->right)
			{
				q.push(tmp->right);
			}
		}
	}

	void DFS()const
	{
		if (_root == nullptr)
		{
			return;
		}
		stack<CBT_Tree_Node*> s{};
		s.push(_root);
		CBT_Tree_Node* tmp = nullptr;
		while (!s.empty())
		{
			tmp = s.top();
			s.pop();
			cout << tmp->data << "  ";
			if (tmp->left)
			{
				s.push(tmp->left);
			}
			if (tmp->right)
			{
				s.push(tmp->right);
			}
		}
	}

protected:

	size_t _height_(CBT_Tree_Node* _p)const
	{
		if (_p == nullptr)
		{
			return 0;
		}
		size_t lh = 0, rh = 0;
		lh = _height_(_p->left);
		rh = _height_(_p->right);
		return lh > rh ? ++lh : ++rh;
	}

private:
	CBT_Tree_Node* _root;
	vector<CBT_Tree_Node*>v{};  //使用一个动态数组来存储信息
};

int main()
{
	
	CBT_Tree t{};

	for (int i = 1; i < 8; ++i)
	{
		t.insert(i);
	}

	t.DFS();
	cout << endl;

	t.BFS();
	cout << endl;
	
	return 0;
}