【c++】构建一棵简单的二叉树

曾经终败给现在 2022-07-16 10:53 149阅读 0赞

本文主要讲了如何使用c++来构建一个二叉树类，以及一些功能算法的实现。文中大部分函数的思想都是递归，其中赋值运算符重载有传统写法和现代写法两个版本，层序遍历是非递归，前、中、后序遍历有递归和非递归两个版本。

1、构造函数（递归）

2、拷贝构造函数（递归）

3、析构函数（递归）

4、赋值运算符重载（传统/现代）

5、前中后序遍历（递归/非递归）

6、层序遍历（非递归）

7、查找第k层结点个数（递归）

8、精确查找值为x的结点，并返回当前结点的指针（递归）

9、查找叶子结点个数（递归）

10、查找结点总个数（递归）

11、计算树的深度（递归）

树的结点类型，每个结点都需要有一个指向右孩子的指针，一个指向左孩子的指针，以及一个数据。（当然，如果你想构造三叉树的话，也可以增加一个指向父节点的指针。）

这里我写出了结点的构造函数，方便我们在创建树的时候使用。

注意：这棵树我使用了模板

template<typename T>
    struct BinaryTreeNode
    {
    	BinaryTreeNode<T>* _left;//左孩子
    	BinaryTreeNode<T>* _right;//右孩子
    	T _data;//数据
    	BinaryTreeNode(T data = T())//结点自己的构造函数，T()为一个匿名对象。
    		:_left(NULL)//初始化为空
    		, _right(NULL)
    		, _data(data)
    	{}
    };

下面代码中会经常用到BinaryTreeNode<T>   所以将其重命名为Node

typedef BinaryTreeNode<T> Node;

当我们向写二叉树类的时候，直接给类设定一个根结点，以这个根结点为基础，构建二叉树。

class BinaryTree
    {
     public:
     private:
        BinaryTreeNode<T>* _root;//根节点
    };

1、构造函数

BinaryTree(const T\* a, size\_t size,int index, const T& invalid)

构造函数有4个参数，T类型的指针a，传参时传一个数组，负责传入数据。size保存数组a 的大小，index记录下标，invalid表示非法值。

因为我们需要用到递归，所以在这个函数内部我们需要再封装一个递归函数\_MakeTree()，并让它的返回值为一个Node\*类型的指针。

BinaryTree(const T* a, size_t size,int index, const T& invalid)
    {
    	_root = _MakeTree(a,size,index,invalid);
    }

我们先来观察一个树：

![Center][]

你会看到上面有许多NULL，这些NULL我们就可以理解为非法值invalid。这棵树的前序遍历为:

1  2  3  NULL  NULL  4   NULL   NULL  5   6

最后一个结点不需要非法值，到时候直接创建即可。

与上对应，我们传数组时，应该传的值即为 int a\[10\] = \{1,2,3,'\#','\#',4,'\#','\#',5,6\}。非法值的值可以随意设，这里我设为‘\#’，注意，你向以什么的样的顺序建树，就以什么样的顺序传参，事先要约定好。（这里我用的是前序）

递归：当我们从数组读取到一个数据时，我们先要判断这个值是不是合法，如果合法则new出一个结点并初始化作为当前结点，此时，进入左孩子递归函数读取下一个数据（++index），并把这个函数的返回值链到当前结点root的left，同理，将右孩子递归函数的返回值链到当前结点的right。如果不合法则return，返回上一层函数。最后我们会得到一个根节点，例图中的1。

\_MakeTree函数实现:

Node* _MakeTree(const T* a, size_t size, int& index, const T& invalid)
    {
    	Node *root = NULL;
    	if (index < size && a[index] != invalid)
    	{
    		root = new Node(invalid);
    		root->_data = a[index];
    		root->_left = _MakeTree(a, size, ++index, invalid);
    		root->_right = _MakeTree(a, size, ++index, invalid);
    	}
    	return root;
    }

2、拷贝构造函数

同上，同样实现一个递归函数，返回值仍为Node\*

BinaryTree(const BinaryTree<T>& t)
    {
    	_root = CopyTree(t._root);
    }

递归：同样为前序，从根节点开始，先访问当前结点，判断，若当前结点为空，则返回一个空。若当前结点不为空，则拷贝当期结点。然后递归进入当前结点的左子树，同样进行之前的步骤。左子树处理完之后递归处理右子树。然后返回当前结点（每一层的根节点）。

注意：上文提到的当前结点，在每一层的递归中值都是不一样的。每递归一层，当前结点就会变成传入的参数root。包括下文

CopyTree实现代码：

Node* CopyTree(const BinaryTreeNode<T>* _root)3、
    {
    	if (_root == NULL)
    	{
    		return NULL;
    	}
    	Node* root = new Node(_root->_data);
    	root->_left = CopyTree(_root->_left);
    	root->_right = CopyTree(_root->_right);
    	return root;
    }

3、析构函数

同上，但是析构函数不需要返回值。

~BinaryTree()
    {
    	Destroy(_root);
    }

递归的道理都与上面两个相同，这里直接给出代码：

void Destroy( Node* _root)
    {
    	Node* tmp = _root;
    	if (tmp == NULL)//如果根结点为空，则不需要delete，直接return。
    	     return;
    	Destroy(tmp->_left);
    	Destroy(tmp->_right);
    	delete tmp;
    	tmp = NULL;
    }

4、赋值运算符重载（=）

当我们写任何赋值运算符重载时，都会有两种写法

①传统写法，一个元素一个元素的拷贝，传参时传的是const的引用。

这样赋值有个麻烦的地方，我们知道，当给一个结点赋值的时候，这个结点原本的内容，空间就要被销毁掉。就是说我们既要new又要delete。当这个树有1个亿结点时，我们岂不是要重复1亿次？有没有一种更简单的方法呢？

②现代写法（建议使用，很巧妙），调用swap函数，交换两个树的root。传参时用的值传递。

BinaryTree<T>& operator=(BinaryTree<T> t)
    {
    	if (this != &t)//自赋值的优化
    	{
    		std::swap(_root, t._root);
    	}
    	return *this;
    }

我们都知道，值传递传的是一份临时拷贝（t为一份临时拷贝），临时拷贝的特性就是，它的存活周期只限于这个函数，当函数调用完毕时，它会自动销毁，而我们也恰恰利用了这个特性。当我们运行std::swap(\_root,t.\_root)这个语句的时候，临时拷贝t的\_root 和 本树的(this)\_root发生了交换。\_root原本的值被赋给了临时拷贝t.\_root，t.\_root的值被赋给了\_root。当我们执行完这个程序的时候t自动销毁，帮我们完成了销毁\_root原本内容的工作。我们即完成了赋值，又省去了一大部分工作，一举两得。

5、前中后序遍历（递归）

①前序

这个我就不再多说了，构造，拷贝构造，析构，都是利用前序遍历的道理来做的。当前结点-->左子树-->右子树。

代码：

void PrevOrder()
    {
    	_PrevOrder(_root);
    	cout << endl;
    }

\_PrevOrder()

void _PrevOrder(Node* _root)
    {
    	Node* tmp = _root;
    	if (tmp == NULL)
    	{
    		return;
    	}
    	cout << tmp->_data << " ";
    	_PrevOrder(tmp->_left);
    	_PrevOrder(tmp->_right);
    }

②中序

判断当前结点是否为空，为空的话，不处理，直接返回。先递归访问当前结点左子树，当左子树处理完毕，再依次返回处理当前结点，再递归访问当前结点右子树。

void InOrder()
    {
    	_InOrder(_root);
    	cout << endl;
    }

\_InOrder()

void _InOrder(Node* _root)
    {
    	Node* tmp = _root;
    	if (tmp == NULL)
    	{
    		return;
    	}
    	_InOrder(tmp->_left);
    	cout << tmp->_data << " ";
    	_InOrder(tmp->_right);
    }

③后序

判断当前结点是否为空，为空的话，不处理，直接返回。不为空的话，先递归访问当前结点节点的左子树，再递归访问当前结点根节点的右子树，最后访问当前结点。

void PostOrder()
    {
    	_PostOrder(_root);
    	cout << endl;
    }

\_PostOrder()

void _PostOrder(Node* _root)
    {
    	Node* tmp = _root;
    	if (tmp == NULL)
    	{
    		return;
    	}
    	_PostOrder(tmp->_left);
    	_PostOrder(tmp->_right);
    	cout << tmp->_data << " ";
    }

6、前中后序非递归。

这里我告诉大家一个真理，任何的递归都可以用栈来替换实现。这里我就用一个辅助栈来实现前中后序的非递归。

①前序

![20161016150501630][]

![20161016150605224][]

![20161016150619959][]

代码：

void PrevOrder_NonR()
    {
    	Node* cur = _root;
    	stack<Node*> s;
    	if (cur == NULL)
    	{
    		return;
    	}
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);
    			cout << cur->_data << " ";
    			cur = cur->_left;
    		}
    		Node* top = s.top();
    		s.pop();
    		cur = top->_right;
    	}
    	cout << endl;
    }

中序和后序的道理与上相同，只是当前节点的输出做了小小的改动。下面直接贴出代码

②中序（非递归）

void InOrder_NonR()
    {
    	Node* cur = _root;
    	stack<Node*> s;
    	if (cur == NULL)
    	{
    		return;
    	}
    	while (cur || !s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);
    		        cur = cur->_left;
    	        }
    		Node* top = s.top();
    		cout << top->_data << " ";
    		s.pop();
    		cur = top->_right;
    	}
    	cout << endl;
    }

③后序（非递归）

后序的非递归较上面两个多了一个变量，prev，它记录了上一次访问的节点。因为后序是最后访问当前节点的，当我们访问一个节点，我们不知道这个节点的右树是否被访问过。所以我们需要记录一下上一个访问的节点。以便访问右树时做判断。

void PostOrder_NonR()
    {
    	Node* cur = _root;
    	Node* prev = NULL;
    	stack<Node*> s;
    	while (cur || s.empty())
    	{
    		while (cur)
    		{
    			s.push(cur);
    			cur = cur->_left;
    		}
    		Node* top = s.top();
    
    		//如果右树为空或者右树已经访问过，则访问当前结点，并出栈
    		//如果右树不为空并且没有访问过，则访问右树
    		if (top->_right == NULL || prev == top->_right)
    		{
    			cout << top->_data << " ";
    			prev = top;
    			s.pop();//返回父节点
    		}
    		else
    		{
    			cur = top->_right;
    		}
    	}
    	cout << endl;
    }

7、层序遍历

顾名思义。层序遍历就是按层来访问一颗树，一次访问一层。这里我们用到了一个队列。

![20161016151949680][]

![20161016153122917][]

代码：

void _LevelOrder(Node* _root)
    {
    	Node *tmp = _root;
            queue<Node*> q;
    	q.push(tmp);
    	while (!q.empty())
    	{
    		Node* top = q.front();
    		q.pop();
    		cout << top->_data << " ";
    		if (top->_left)
    		{
    			q.push(top->_left);
    		}
    		if (top->_right)
    		{
    			q.push(top->_right);
    		}
    	}
    }

8、查找第k层节点个数

这个问题，我们只需要查找第k-1层有多少个孩子就行了。

同样为递归，前序。

size_t FindKlevel(size_t k)
    {
    	return _FindKlevel(_root,k);
    }

\_FindKlevel()

size_t _FindKlevel(Node* _root,size_t k)
    {
    	Node *cur = _root;
    	if (cur == NULL || k < 0)
    	{
    		return 0;
    	}
    	if (k == 1)
    	{
    		return 1;
    	}
    	size_t left = _FindKlevel(cur->_left, k-1);
    	size_t right = _FindKlevel(cur->_right, k-1);
    
    	return  left + right;
    }

9、精确查找值为x的结点

前序递归查找，如果根节点为空，返回NULL，如果当前节点等于x，返回当前节点的指针。如果当前节点不等于x，则递归进入左子树查找，若左子树没有，则递归进入右子树查找，若这棵树中没有x，返回NULL。

Node* Find(const T& x)
    {
    	return _Find(_root,x);
    }

\_Find()

Node* _Find(Node* _root,const T& x)
    {
    	Node* ret = NULL;
    	Node* cur = _root;
    	if (cur == NULL)
    	{
    		return NULL;
    	}
    	if (cur->_data == x)
    	{
    		ret = cur;
    	}
    	else
    	{
    	    ret = _Find(cur->_left,x);
    	    if (ret == NULL)
    	    {
    		ret = _Find(cur->_right,x);
    	    }
    	}
    	return ret;
    }

10、查找结点总个数。

结点总个数 = 当前节点个数+左子树节点个数+右子树节点个数。

前序递归查找，若当前节点为空，返回，不为空则加1，--->递归左子树----->递归右子树。

size_t Size()
    {
    	return _Size(_root);
    }

\_Size()

size_t _Size( BinaryTreeNode<T>* _root )
    {
    	size_t ret = 0;
    	if (_root == NULL)
    	{
    		return ret;
    	}
    	ret++;
    	ret += _Size(_root->_left);
    	ret += _Size(_root->_right);
    }

11、计算树的深度

树的深度取左子树深度+1和右子树深度+1的最大值。(+1为根节点的深度)

size_t Depth()
    {
    	return _Depth(_root);
    }

\_Depth()

size_t _Depth(Node* _root)
    {
    	if (_root == NULL)
    	{
    		return 0;
    	}
    	int left = _Depth(_root->_left) + 1;
    	int right = _Depth(_root->_right) + 1;
    	return left > right ? left : right;
    }

。请大家采用批评的态度来看这篇博文，博主水平也一般。。。。

[Center]: /images/20220716/5467f9be59ad44b48765901c19fb47cc.png
[20161016150501630]: /images/20220716/f6ff4aeaca564b8fabb9e068631e01da.png
[20161016150605224]: /images/20220716/34d15e549e9d4e558cfc0d0db33d7575.png
[20161016150619959]: /images/20220716/2bb508210b1140af952a19a23c42dab0.png
[20161016151949680]: /images/20220716/792e4ae3fb7b46a88252b6814726de05.png
[20161016153122917]: /images/20220716/081d8bddc520467d874c3f6086bcc91d.png