数据结构之二叉树的递归实现

喜欢ヅ旅行 2022-07-16 00:39 165阅读 0赞

**二叉树的概念篇>**

(1).二叉树是一颗特殊的树,二叉树每个结点最多有两个孩子结点,即就是左孩子和右孩子

(2).满二叉树：若一颗树的高度为h,则h层均满

(3).完全二叉树：若一棵树的高度为h,则前h-1层均满最后一层可以不满,且最后一层的结点都连续集中在最左边.

我们知道一个数组可以表示一颗树,它的思想是如果该处有结点则直接将该结点放在对应的下标处，如果没有结点则以符号占位 .

(1).假若一个子结点的下标为i,那仫它的父节点的下标为:(i-1)/2;

(2).假若一个父结点的下标为i，那仫它的左孩子的下标为:2\*i+1,它的右孩子的下标为:2\*i+2.

(3).缺点：如果不是满二叉树和完全二叉树则有太多的内存浪费，且插入删除不便.

用数组表示一个树适用于满二叉树和完全二叉树.

**实例分析篇>**

如果一个数组表示的二叉树:int array\[\]=\{1,2,'\#',3,'\#','\#',4,5,'\#',6,'\#',7,'\#','\#',8\},'\#'代表该位置没有结点，该树被还原之后为:

![Center][]

递归求一个树的前序遍历，中序遍历，后序遍历，层序遍历,树的叶子节点的数量，树的总结点的数量，树的深度，统计每一层的结点总数.

(1).前序遍历：先访问根结点，再递归访问左子树，最后访问右子树.

(2).中序遍历：先访问左子树，再访问根结点，最后访问右子树.

(3).后序遍历：先访问左子树，再访问右子树，最后访问根结点.

(4).层序遍历：一层层结点依次遍历，在实现层序遍历的时候用到了队列先进先出的性质,将每一层的数据一次进队列，而每次出队列的元素就是层序遍历的当前元素.

(5).树的总结点数：根结点+左子树的结点数+右子树的结点数.

(6).树的叶子节点数:叶子节点(即没有左子树也没有右子树),左子树的叶子节点总数+右子树的叶子节点总数.

**代码实现>,**

BinaryTree.h

#pragma once
    
    template<typename T>
    struct BinaryTreeNode
    {
    	BinaryTreeNode(const T& data=T())
    		:_data(data)
    		,_left(NULL)
    		,_right(NULL)
    	{}
    	T _data;
    	BinaryTreeNode *_left;
    	BinaryTreeNode *_right;
    };
    
    template<typename T>
    class BinaryTree
    {
    	typedef BinaryTreeNode<T> Node;
    public:
    	BinaryTree()
    		:_root(NULL)
    	{}
    	BinaryTree(const T *array,size_t size,const T& invalid)
    	{
    		size_t index=0;
    		_root=_CreatTree(array,size,index,invalid);
    	}
    	BinaryTree(const BinaryTree<T>& bt)
    	{
    		_root=_Copy(bt._root);
    	}
    	//BinaryTree<T>& operator=(const BinaryTree<T>& bt)
    	//{
    	//	//传统的写法
    	//	if (this != &bt)
    	//	{
    	//		Node *root=_Copy(bt._root);
    	//		_Destroy(_root);
    	//		_root=root;
    	//	}
    	//	return *this;
    	//}
    	BinaryTree<T>& operator=(const BinaryTree<T>& bt)
    	{
    		//现代的写法
    		if (this != &bt)   //防止自赋值
    		{
    			BinaryTree<T> tmp(bt);
    			std::swap(_root,tmp._root);
    		}
    		return *this;
    	}
    	~BinaryTree()
    	{
    		_Destroy(_root);
    	}
    public:
    	void PrevOrder()   //前序遍历
    	{
    		_PrevOrder(_root);
    		cout<<endl;
    	}
    	void InOrder()     //中序遍历
    	{
    		_InOrder(_root);
    		cout<<endl;
    	}
    	void PostOrder()   //后序遍历
    	{
    		_PostOrder(_root);
    		cout<<endl;
    	}
    	void LevelOrder()   //层序遍历
    	{
    		_LevelOrder(_root);
    		cout<<endl;
    	}
    	size_t Size()       //求该树的总结点数
    	{
    		size_t size=_Size(_root);
    		return size;
    	}
    	size_t Depth()     //求该树的深度
    	{
    		size_t depth=_Depth(_root);
    		return depth;
    	}
    	size_t LeafSize()   //求一个树叶子节点的总数
    	{
    		size_t leaf=_LeafSize(_root);
    		return leaf;
    	}
    	size_t GetKLevel(int level)   //level层的所有节点的个数
    	{
    		size_t count=_GetKLevel(_root,level);
    		return count;
    	}
    protected:
    	Node *_CreatTree(const T *array,size_t size,size_t& index,const T& invalid)
    	{
    		assert(array);
    		Node *root=NULL;
    		if (index < size && array[index] != invalid)
    		{
    			root=new Node(array[index]);
    			root->_left=_CreatTree(array,size,++index,invalid);
    			root->_right=_CreatTree(array,size,++index,invalid);
    		}
    		return root;
    	}
    	Node *_Copy(Node *root)
    	{
    		//proot是拷贝的新树的根节点
    		Node *cur=root;
    		Node *proot=NULL;
    		if (cur)
    		{
    			proot=new Node(cur->_data);
    			proot->_left=_Copy(cur->_left);
    			proot->_right=_Copy(cur->_right);
    		}
    		return proot;
    	}
    	void _Destroy(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_Destroy(cur->_left);
    			_Destroy(cur->_right);
    			delete cur;
    			cur=NULL;
    		}
    	}
    protected:
    	void _PrevOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			cout<<cur->_data<<" ";
    			_PrevOrder(root->_left);
    			_PrevOrder(root->_right);
    		}
    	}
    	void _InOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_InOrder(cur->_left);
    			cout<<cur->_data<<" ";
    			_InOrder(cur->_right);
    		}
    	}
    	void _PostOrder(Node *root)
    	{
    		Node *cur=root;
    		if (cur)
    		{
    			_PostOrder(cur->_left);
    			_PostOrder(cur->_right);
    			cout<<cur->_data<<" ";
    		}
    	}
    	void _LevelOrder(Node *root)
    	{
    		queue<Node *> q;
    		Node *cur=root;
    		q.push(cur);
    		while(!q.empty())
    		{
    			Node *t=q.front();
    			cout<<t->_data<<" ";
    			if (t->_left != NULL)
    			{
    				q.push(t->_left);
    			}
    			if (t->_right != NULL)
    			{
    				q.push(t->_right);
    			}
    			q.pop();
    		}
    	}
    	size_t _Size(Node *root)
    	{
    		if (root == NULL)
    		{
    			return 0;     //空树
    		}
    		return 1+_Size(root->_left)+_Size(root->_right);
    	}
    	size_t _Depth(Node *root)
    	{
    		Node *cur=root;
    		if (root == NULL)
    		{
    			return 0;
    		}
    		return 1+(_Depth(cur->_left)>_Depth(cur->_right)
    			?_Depth(cur->_left):_Depth(cur->_right));
    	}
    	size_t _LeafSize(Node *root)
    	{
    		Node *cur=root;
    		if (cur == NULL)   //空树
    		{
    			return 0;
    		}
    		else if ((cur->_left == NULL) && (cur->_right == NULL))
    		{
    			//叶子结点--一个结点即没有左子树也没有右子树
    			return 1;
    		}
    		else
    			return _LeafSize(cur->_left)+_LeafSize(cur->_right);
    	}
    	size_t _GetKLevel(Node *root,int level)
    	{
    		size_t count=0;
    		if (root == NULL)
    		{
    			return 0;
    		}
    		if (level == 1)
    		{
    			count++;
    		}
    		else
    		{
    			count += _GetKLevel(root->_left,level-1);
    			count += _GetKLevel(root->_right,level-1);
    		}
    		return count;
    	}
    protected:
    	Node *_root;
    };

test.cpp

void testBinaryTree()
    {
    	int array[]={1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
    	size_t sz=sizeof(array)/sizeof(array[0]);
    	BinaryTree<int> bt(array,sz,'#');
    
    	bt.PrevOrder();   //1 2 3 4 5 6 7 8
    	bt.InOrder();     //2 3 1 5 6 7 4 8
    	bt.PostOrder();   //3 2 7 6 5 8 4 1
    	bt.LevelOrder();  //1 2 4 3 5 8 6 7 
    	cout<<bt.Size()<<endl;    //8
    	cout<<bt.Depth()<<endl;   //5
    
    	BinaryTree<int> bt1(bt);
    	bt1.PrevOrder();
    	bt1.InOrder();
    	bt1.PostOrder();
    	bt1.LevelOrder();
    	cout<<bt1.Size()<<endl;    //8
    	cout<<bt1.Depth()<<endl;   //5
    
    	BinaryTree<int> bt2;
    	bt2=bt;
    	bt2.PrevOrder();
    	bt2.InOrder();
    	bt2.PostOrder();
    	bt2.LevelOrder();
    	cout<<bt2.Size()<<endl;     //8
    	cout<<bt2.Depth()<<endl;    //5
    	cout<<bt2.LeafSize()<<endl; //3  
    	//该树的每一层共有多少个结点
    	cout<<bt2.GetKLevel(1)<<endl;;  //1
    	cout<<bt2.GetKLevel(2)<<endl;;  //2
    	cout<<bt2.GetKLevel(3)<<endl;;  //3
    	cout<<bt2.GetKLevel(4)<<endl;;  //1
    	cout<<bt2.GetKLevel(5)<<endl;;  //1
    }

[Center]: /images/20220716/6c5108aef4ce472e9e1d4561b924cdcb.png