C++ 二叉树（1）构造、析构及相关操作实现_cpp构造二叉树

本篇介绍二叉树的性质及完全二叉树和二叉搜索树的构建操作，定义就不赘述了。

一、性质

$约定：二叉树的层次从$ 0 $开始。$

• $1.第i层最多有2^i个节点。$
• $2.高度为h(总层数为h+1，最底层为h)的二叉树最多有2^{h+1}-1个节点。$
  $说明：第i层有2^i个节点，将每层节点相加，则总结点数为N={\sum }_0^h{2}^i=2^{h+1}-1。$
• $3.节点数为n的完全二叉树高度为\lfloor lo{g}_{2}n\rfloor +1。$
  $说明：由2可得。$
• $4.对任意二叉树，设其叶节点(度为0的节点)个数为n_0，度为2的节点个数为n_2,则有n_0=n_2+1。$
  $说明：$
  $(1)度的定义：当前节点的子节点个数称为当前节点的度。$
  $(2)公式计算：$
  $节点总个数n=n_0+n_1+n_2$
  $二叉树的边的个数b=n_0\ast 0+n_1\ast 1+n_2\ast 2=n_1+2n_2$
  $从二叉树的结构知：b=n-1$
  $联立上式可得n_0=n_2+1$
• $5.一棵节点数为n的完全二叉树的高度h=lo{g}_2(n+1)。$
  $说明：由性质2，高度为h的满二叉树节点数为2^{h+1}-1，设所求完全二叉树高度h_0，有2^{h_0}-1<n<=2^{h_0+1}-1，(完全二叉树的节点数夹在层数为h_0-1和h_0的满二叉树之间)，取对数可得结果。$

二、代码实现

---

2.1 类的声明

class BinaryTree {
private:
	class Node {//节点定义
	public:
		int value;
		Node* left;//左子女
		Node* right;//右子女
		Node(int newval, Node* l = NULL, Node* r = NULL) : 
			value(newval), left(l), right(r) {};
	};
	Node* root;//根节点
	//辅助函数
	Node* ConstructAux(Node* cursubroot, Node* orgsubroot);//递归实现复制构造时的辅助函数
public:
	BinaryTree() : root(NULL){};//默认构造
	BinaryTree(const BinaryTree& origin);//复制构造
	~BinaryTree();//析构

	void CompleteBinaryTree();//输入完全树
	void BinarySearchTree();//输入二叉搜索树

	bool empty() const;//判空
	void add(int newdata);//按完全树的规则添加元素
	void insert(int newdata);//按二叉搜索树的规则添加元素
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

由于二叉树实现篇幅较长，本篇先介绍构造、析构、添加元素、输入完全树、输入二叉搜索树这5个函数，在之后介绍遍历等其他操作。

各函数的功能已在代码中注释。

---

2.2 复制构造函数

在学校做作业时实现的是循环的方法，而这个方法实现起来比较麻烦，在写这篇时才想起来可以用递归实现，以上两个方法都介绍一下。

递归版

BinaryTree(const BinaryTree& origin)//复制构造函数
{
	root = NULL;//初始化
	if(!origin.empty())root = ConstructAux(root,origin.root);//如果原二叉树不为空就进行复制
}
Node* ConstructAux(Node* cursubroot, Node* orgsubroot)
{
	cursubroot = new Node(orgsubroot->value);//复制根
	if (orgsubroot->left != NULL) cursubroot->left = ConstructAux(cursubroot->left,orgsubroot->left);//复制左树
	if (orgsubroot->right != NULL) cursubroot->right = ConstructAux(cursubroot->right,orgsubroot->right);//复制右树
	return cursubroot;//返回当前的根节点
}
1
2
3
4
5
6
7
8
9
10
11
12

ConstructAux()为一个辅助函数，用于实现递归，执行以下功能：

• 为新二叉树的当前位置创建节点并复制原二叉树对应节点值

• 如果origin当前节点左子树不为空，那么就调用ConstructAux()复制该左子树。

• 如果origin当前节点右子树不为空，那么就调用ConstructAux()复制该右子树。

• 将当前节点返回给上一级，供上一级根节点连接该子节点。

循环版

循环版按行从左到右从上到下复制原二叉树，主要使用了队列的先入先出特性来遍历并复制原二叉树。

BinaryTree(const BinaryTree& origin)
{
	root = NULL;
	if (!origin.empty())
	{
		root = new Node(origin.root->value);//创建新树的根节点
		queue<Node*> org, cur;//队列用来存放节点,org存放原树origin的节点,cur存放新树的节点
		org.push(origin.root);//队列加入根
		cur.push(root);
		while (!org.empty())
		{
			Node* orgfront = org.front(),//在本轮循环要被复制的节点
				* curfront = cur.front();
			
			if (orgfront->left != NULL)//复制左子树
			{
				org.push(orgfront->left);//在org加入原树的左节点，用于树下一层的复制
				curfront->left = new Node(orgfront->left->value);//复制左节点的值
				cur.push(curfront->left)//在cur加入新树刚创建的节点，用于下一层的复制
			}
			if (orgfront->right != NULL)//复制右子树，操作同复制左子树
			{
				org.push(orgfront->right);
				curfront->right = new Node(orgfront->right->value);
				cur.push(curfront->right);
			}
			org.pop();//把已经复制完的节点删去
			cur.pop();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

2.3 析构函数

析构函数使用了和迭代版复制构造函数类似的方法按行来释放节点空间。

~BinaryTree()
{
	if (!empty())
	{
		queue<Node*> q;
		q.push(root);
		while (!q.empty())
		{
			Node* f = q.front();
			if (f->left != NULL) q.push(f->left);//如果子女不为空就加入子女，一会儿删除
			if (f->right != NULL) q.push(f->right);
			delete f;//删除当前节点
			q.pop();//把没用的指针弹出
		}
		root = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

不在当前节点直接删除子女是因为如果直接删除了当前节点和其子女，那么其子女下面的节点就找不到了，所以每次只删除当前节点。

2.4 加入元素

2.4.1 按完全树的规则加入元素

add()在按从左到右从上到下的顺序找到的第一个空位处加入新节点，显然，如果仅使用该函数构造一个二叉树，构造的二叉树为完全二叉树。

void add(int newdata)
{
	if (empty()) root = new Node(newdata);
	else {
		queue<Node*> q;//队列
		q.push(root);//加入根
		while (1)
		{
			Node* f = q.front();
            //检查当前节点f的左右子女中是否有空位，如果有就在空位加入新元素
			if (f->left == NULL) {
				f->left = new Node(newdata);
				break;
			}
			else if (f->right == NULL) {
				f->right = new Node(newdata);
				break;
			}
            //如果f的子女都满了就在队列加入子女。
			else {
				q.push(f->left);
				q.push(f->right);
				q.pop();//把遍历过的弹出
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.4.2按二叉搜索树的规则添加元素

insert()在按二叉搜索树的规则找到的第一个空位放置新节点。

void BinaryTree::insert(int newdata)
{
	if (empty()) root = new Node(newdata);//为空，在根加入元素
	else {
		Node* ptr = root;
		while (1)
		{
			if (ptr->value == newdata) {//搜索树元素不能重复
				cout << "数据与树中已有元素重复，不能插入" << endl;
				break;
			}
			else if (ptr->value > newdata) {//若新元素小于当前节点，就把新元素加在左子树
				if (ptr->left == NULL) {//如果左节点为空，就把数据放在左节点
					ptr->left = new Node(newdata);
					break;
				}
				else ptr = ptr->left;//如果左节点不空，就在左子树找位置
			}
			else {//新元素大于当前节点就放在右子树，规则同上
				if (ptr->right == NULL) {
					ptr->right = new Node(newdata);
					break;
				}
				else ptr = ptr->right;
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.5输入完全树

使用add()输入完全树。

void BinaryTree::CompleteBinaryTree()
{
	if (!empty())this->~BinaryTree();
	cout << "请输入数据（以空格分隔、Ctrl+z结束）："<< endl;
	int data;
	while (cin >> data) add(data);
}
1
2
3
4
5
6
7

2.6输入二叉搜索树

使用insert()输入搜索树，与2.5仅调用的添加元素的函数不同。

void BinaryTree::BinarySearchTree()
{
	if (!empty())this->~BinaryTree();
	cout << "请输入数据（以空格分隔、Ctrl+z结束）：" << endl;
	int data;
	while (cin >> data) insert(data);
}
1
2
3
4
5
6
7

在下一篇我们说明输出二叉树的方法，检验以上输入功能是否正确。