数据结构 — 二叉树的基本操作实现(递归算法)

刺骨的言语ヽ痛彻心扉 2022-06-11 22:39 176阅读 0赞

我们直接切入主题相信大家都应该知道什么叫二叉树吧。二叉树里面有几个常见的操作，他们分别是构造二叉树，前序遍历，中序

遍历，后序遍历，还有 求树的叶子结点，树的深度，树中第K层的节点个数，树中结点的个数，以及在树中查找一个结点。

注意这里大部分都是用递归实现的！！ （也就是这篇文章是入门的，非递归我还会写一个博客）

好了现在开始，我们一个一个的解决他们吧。

科普：

所谓的前序遍历，中序遍历，后序遍历分别代表着什么？

![96B915803D1B0CBEFA351D4B3526E613.net_2F20170508210523116][]

# template<class T> struct BinaryTreeNode \{ BinaryTreeNode<T>\* \_letf; BinaryTreeNode<T>\* \_right; T \_data; BinaryTreeNode(const T& x) :\_letf(NULL) , \_right(NULL) , \_data(x) \{\} \};  这是我定义的一个二叉树的结点。  接下来 typedef BinaryTreeNode<T> Node;  也就是接下来我们看到的每一个Node表示的就是一个二叉树的结点。 #

# 构造二叉树 #

在这里invalid就是所谓的非法值，而index就是数组的下标。

比如:int array\[10\] = \{ 1, 2, 3, '\#', '\#', 4, '\#', '\#', 5, 6 \};

这里的invalid就是'\#'.

BinaryTree()
    	:_root(NULL)
    	{}
    	BinaryTree(T* a, size_t n, const T& invalid)
    	{
    		size_t index = 0;
    		_root = CreateTree(a, n, invalid, index);
    	}
    //注意这里的index 要使用引用， 若是没有使用 上一层递归里面的++index 对上一层没有任何影响.
    
    	//构建二叉树表
    	Node* CreateTree(T* a, size_t n, const T& invalid, size_t& index)
    	{
    		Node* root = NULL;
    		if (index < n && a[index] != invalid)
    		{
    			root = new Node(a[index]);
    			root->_letf = CreateTree(a, n, invalid, ++index);
    			root->_right = CreateTree(a, n, invalid, ++index);
    		}
    		return root;
    	}

在这里我用一个图来还原实现过程，因为涉及递归那么我就少说话多画图：

![ABAFAF8B68F35ED01F381A181233BA52.net_2F20170508204621573][]

### 这里呢，按照代码一步一步的在图中移动，相信你会理解的，毕竟我这么笨的人都理解了。 ###

###  ###

# 二叉树的前序遍历 #

//前序遍历
    	void _prevOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return ;
    		}
    		cout << root->_data << " ";
    		_prevOrder(root->_letf);
    		_prevOrder(root->_right);
    
    	}

图解：

# ![675ABC921326EF09168EF18F85A560ED.net_2F20170508205341875][] #

#  #

# 二叉树的中序遍历 #

#  #

# //中序遍历 void \_InOrder(Node\* root) \{ if (root == NULL) \{ return; \} \_InOrder(root->\_letf); cout << root->\_data << " "; \_InOrder(root->\_right); \} #

#  #

这里和前序遍历很相似，我就不画图了

#  #

# 二叉树的后序遍历 #

//后序遍历
    	void PosOrder()
    	{
    		return _PosOrder(_root);
    	}
    	void _PosOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_PosOrder(root->_letf);
    		_PosOrder(root->_right);
    		cout << root->_data <<" ";
    	}

# 图解: #

![900479081DCB071912F35BDC9D663F3E.net_2F20170508205603798][]

#  #

# 二叉树的层序遍历 #

void _LevelOrder(Node* root)
    	{
    		queue<Node*> q;
    		if (root != NULL)
    		{
    			q.push(root);
    			while (!q.empty())
    			{
    				Node* front = q.front();
    				cout << front->_data << " ";
    				if (front->_letf)
    				{
    					q.push(front->_letf);
    				}
    				if (front->_right)
    				{
    					q.push(front->_right);
    				}
    				
    				q.pop();
    			}
    		}
    	}

这里层序遍历就是少数没办法用递归实现的函数，在这里它借助了队列-/-，具体的过程:

![EF42CC5B1870B9633FA34360AFCB72DB.net_2F20170508205906612][]

#  #

# 二叉树叶子结点个数 #

在这里就要对问题进行分解：

1.这里所有的叶子结点其实就是 左孩子里面的叶子结点个数+右孩子里面的叶子节点个数

2.当你把每一个结点看做根节点时，一层一层的把叶子结点总数就统计出来了

(这里当你为叶子节点是你只返回1就好)

size_t _LeafSize(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (root->_letf == NULL &&root->_right == NULL)
    		{
    			return 1;
    		}
    		size_t i = _LeafSize(root->_letf);
    		size_t j = _LeafSize(root->_right);
    		return i + j;
    	}

#  #

# 二叉树深度 #

size_t _Depth(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		else
    		{
    			size_t i = _Depth(root->_letf);
    			size_t j = _Depth(root->_right);
    			if (i > j)
    			{
    				return i + 1;
    			}
    			else
    			{
    				return j + 1;
    			}
    		}
    	}

图解：

![BA4A5686ABE757837043C3A860B7C973.net_2F20170508213837443][]

#  #

# 二叉树总结点数 #

这里也是把主问题分解成无数个子问题：

#  #

### 1.对于根节点来说它的总节点个数，就是左孩子和右孩子结点的个数加上自己的总和 也就是    左孩子总结点数 + 1 + 右孩 子总结点  2.当你使用递归时也就是每一个结点都可以看成根节点，所以就是每个结点的左孩子+1+右孩子总结点个数.  size\_t \_Size(Node\* root) \{ if (root == NULL) \{ return 0; \} size\_t i = \_Size(root->\_letf); size\_t j = \_Size(root->\_right); return i + j + 1; \} ###

# 二叉树第K层节点个数 #

# size\_t \_GetKLevel(Node\* root, size\_t k) \{ if (root == NULL) \{ return 0; \} if (k == 1) \{ return 1; \} return \_GetKLevel(root->\_letf, k - 1) + \_GetKLevel(root->\_right, k - 1); \} #

#  #

# 二叉树查找节点 #

Node* _find(Node* root,const T& x)
    	{
    		if (root == NULL)
    		{
    			return NULL;
    		}
    		if (root->_data == x)
    		{
    			return root;
    		}
    		Node* ret = _find(root->_letf, x);
    		if (ret)
    		{
    			return ret;
    		}
    		return _find(root->_right, x);
    	}

实现代码：

#include<iostream>
    #include<Windows.h>
    #include<queue>
    using namespace std;
    
    template<class T>
    struct BinaryTreeNode
    {
    	BinaryTreeNode<T>* _letf;
    	BinaryTreeNode<T>* _right;
    	T _data;
    	BinaryTreeNode(const T& x)
    		:_letf(NULL)
    		, _right(NULL)
    		, _data(x)
    	{}
    };
    
    
    template<class T>
    class BinaryTree
    {
    	typedef BinaryTreeNode<T> Node;
    public:
    	BinaryTree()
    		:_root(NULL)
    	{}
    	BinaryTree(T* a, size_t n, const T& invalid)
    	{
    		size_t index = 0;
    		_root = CreateTree(a, n, invalid, index);
    	}
    	BinaryTree(const BinaryTree<T>& t);
    	BinaryTree<T>& operator = (const BinaryTree<T>& t);
    
    	//前序遍历
    	void  PrevOrder()
    	{
    		return _prevOrder(_root);
    	}
    	//中序遍历
    	void InOrder()
    	{
    		return _InOrder(_root);
    	}
    
    	//后序遍历
    	void PosOrder()
    	{
    		return _PosOrder(_root);
    	}
    
    	//层序遍历
    	void LevelOrder()
    	{
    		return _LevelOrder(_root);
    	}
    
    	//尺寸大小
    	size_t Size()
    	{
    		return _Size(_root);
    	}
    
    	//叶子结点
    	size_t LeafSize()
    	{
    		return _LeafSize(_root);
    	}
    
    	//第K个结点的节点个数
    	size_t GetKLevel(size_t k)
    	{
    		return _GetKLevel(_root, k);
    	}
    
    	//树深度
    
    	size_t Depth()
    	{
    		return _Depth(_root);
    	}
    
    	//查找
    
    	Node* find(const T& x)
    	{
    		return _find(_root,x);
    	}
    
    protected:
    
    	//第K层的节点数
    
    	size_t _GetKLevel(Node* root, size_t k)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (k == 1)
    		{
    			return 1;
    		}
    
    		return _GetKLevel(root->_letf, k - 1) + _GetKLevel(root->_right, k - 1);
    	}
    
    	//查找
    
    	Node* _find(Node* root,const T& x)
    	{
    		if (root == NULL)
    		{
    			return NULL;
    		}
    		if (root->_data == x)
    		{
    			return root;
    		}
    		Node* ret = _find(root->_letf, x);
    		if (ret)
    		{
    			return ret;
    		}
    		return _find(root->_right, x);
    	}
    
    	//深度
    
    	size_t _Depth(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		else
    		{
    			size_t i = _Depth(root->_letf);
    			size_t j = _Depth(root->_right);
    			if (i > j)
    			{
    				return i + 1;
    			}
    			else
    			{
    				return j + 1;
    			}
    		}
    	}
    
    	//叶子结点求解
    
    	size_t _LeafSize(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (root->_letf == NULL &&root->_right == NULL)
    		{
    			return 1;
    		}
    		size_t i = _LeafSize(root->_letf);
    		size_t j = _LeafSize(root->_right);
    		return i + j;
    	}
    
    	//层序遍历
    
    	void _LevelOrder(Node* root)
    	{
    		queue<Node*> q;
    		if (root != NULL)
    		{
    			q.push(root);
    			while (!q.empty())
    			{
    				Node* front = q.front();
    				cout << front->_data << " ";
    				if (front->_letf)
    				{
    					q.push(front->_letf);
    				}
    				if (front->_right)
    				{
    					q.push(front->_right);
    				}
    				
    				q.pop();
    			}
    		}
    	}
    
    	//总成员数
    
    	size_t _Size(Node* root)
    	{
    		if (root == NULL)
    		{
    			return 0;
    		}
    		size_t i = _Size(root->_letf);
    		size_t j = _Size(root->_right);
    		return i + j + 1;
    	}
    
    	//后序遍历
    	void _PosOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_PosOrder(root->_letf);
    		_PosOrder(root->_right);
    		cout << root->_data <<" ";
    	}
    
    	//中序遍历
    	void _InOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_InOrder(root->_letf);
    		cout << root->_data << " ";
    		_InOrder(root->_right);
    	}
    
    	//前序遍历
    	void _prevOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return ;
    		}
    		cout << root->_data << " ";
    		_prevOrder(root->_letf);
    		_prevOrder(root->_right);
    
    	}
    
    	//注意这里的index 要使用引用， 若是没有使用 上一层递归里面的++index 对上一层没有任何影响.
    
    	Node* CreateTree(T* a, size_t n, const T& invalid, size_t& index)
    	{
    		Node* root = NULL;
    		if (index < n && a[index] != invalid)
    		{
    			root = new Node(a[index]);
    			root->_letf = CreateTree(a, n, invalid, ++index);
    			root->_right = CreateTree(a, n, invalid, ++index);
    		}
    		return root;
    	}
    protected:
    
    	Node* _root;
    	size_t index;
    	size_t invalid;
    };
    
    void Test1()
    {
    	int array[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    	BinaryTree<int> t1(array, sizeof(array) / sizeof(array[0]), '#');
    	t1.PrevOrder();
    	//t1.InOrder();
    	//t1.PosOrder();
    	//cout<<t1.Size()<<" ";
    	//t1.LevelOrder();
    	//cout<<t1.LeafSize();
    	//cout<<t1.Depth();
    	//cout<<(t1.find(3));
    	//cout<<t1.GetKLevel(3);
    }

[96B915803D1B0CBEFA351D4B3526E613.net_2F20170508210523116]: http://img.dmc.csdn.net/96B915803D1B0CBEFA351D4B3526E613.net%2F20170508210523116
[ABAFAF8B68F35ED01F381A181233BA52.net_2F20170508204621573]: http://img.dmc.csdn.net/ABAFAF8B68F35ED01F381A181233BA52.net%2F20170508204621573
[675ABC921326EF09168EF18F85A560ED.net_2F20170508205341875]: http://img.dmc.csdn.net/675ABC921326EF09168EF18F85A560ED.net%2F20170508205341875
[900479081DCB071912F35BDC9D663F3E.net_2F20170508205603798]: http://img.dmc.csdn.net/900479081DCB071912F35BDC9D663F3E.net%2F20170508205603798
[EF42CC5B1870B9633FA34360AFCB72DB.net_2F20170508205906612]: http://img.dmc.csdn.net/EF42CC5B1870B9633FA34360AFCB72DB.net%2F20170508205906612
[BA4A5686ABE757837043C3A860B7C973.net_2F20170508213837443]: http://img.dmc.csdn.net/BA4A5686ABE757837043C3A860B7C973.net%2F20170508213837443