【数据结构】二叉树的简单遍历及基本操作

1、构造

2、拷贝构造

3、析构

4.深度

5、叶子数

6.前序遍历递归非递归

7、中序遍历递归非递归

8、中序遍历递归非递归

9、第k层子树

等

定义树节点结构体

struct BinTreeNode
{
	BinTreeNode* left;
	BinTreeNode* right;
	T _date;
	BinTreeNode(const T& x)
		:left(NULL),right(NULL),_date(x)
	{}
};

内部函数实现

	void _CreateTree(Node*& root,T a[],size_t size,int& index,const T& invalid)
	{

		if(index< size&& a[index]!=invalid)
		{
			root=new Node(a[index]);
			_CreateTree(root->left,a,size,++index,invalid);
			_CreateTree(root->right,invalid);

		}
	}
	Node*  _CopyBinTree(Node* root)
	{
		Node* newNode=NULL;
		if(!root)
		{
        newNode=new Node(root->_date);
		newNode->left=_CopyBinTree(root->left);
		newNode->right=_CopyBinTree(root->right);
		}
		return newNode;
	}
	void  _Destory(Node* root)
	{
		if(root==NULL)
			return;
		_Destory(root->left);
		_Destory(root->right);
		delete root;
	}
	void  _PrevOrder(Node* root)
	{
		if(root==NULL)
			return;
        cout<<root->_date<<" ";
		_PrevOrder(root->left);
		_PrevOrder(root->right);
		
	}
	void  _InOrder(Node* root)
	{
		if(root==NULL)
			return;
		_InOrder(root->left);
         cout<<root->_date<<" ";
		_InOrder(root->right);
		
	}
	void  _PostOrder(Node* root)
	{
		if(!root)
			return;
		_PostOrder(root->left);
		_PostOrder(root->right);
		cout<<root->_date<<" ";
	}
	int _Size(Node* root)
	{

		if (!root)
		return 0;
		return _Size(root->left)+_Size(root->right)+1;
	}
	int _Depth(Node* root)
	{
		if(!root)
			return 0;
		int leftchilddepth=_Depth(root->left)+1;
		int rightchilddepth=_Depth(root->right)+1;
		if(leftchilddepth>=rightchilddepth)
		{
			return leftchilddepth;
		}
		else
		{
			return rightchilddepth;
		}
	}
	int _GetKLevel(Node* root,size_t k)
	{
if(root==NULL)
	return 0;
if(k==1)
	return 1;
else 
	return _GetKLevel(root->left,k-1)+_GetKLevel(root->right,k-1);
	}
	int _LeafSize(Node* root)
	{
		if(root==NULL)
			return 0;
		if(root->left==NULL&&root->right==NULL)
			return 1;
		return _LeafSize(root->left)+_LeafSize(root->right);
	}

	BinTree(T* a,const T& invalid)//构造
	{
	int index=0;
	_CreateTree( _root,index,invalid);
	}
	BinTree(const BinTree<T>& t)//拷贝构造
	{
		_root=_CopyBinTree(t._root);

	}
	BinTree<T>& operator=(const BinTree<T> &t)//运算符重载
	{
		if(this!=&t)
		{
			swap(_root=t._root);
		}
		return *this;
	}
	void PrevOrder()//递归前序
	{
		_PrevOrder(_root);
		cout<<endl;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}
	void PostOrder()
	{
		_PostOrder(_root);
		cout<<endl;
	}
	void LevelOrder()///层序
	{
		queue<Node*> q;
		Node* cur=_root;
		if(cur)
			q.push(cur);
		while (!q.empty())
		{
			cur=q.front();
			cout<<cur->_date<<" ";
			if(cur->left)
			{
				q.push(cur->left);
			}
			if(cur->right)
			{
				q.push(cur->right);
			}
			q.pop();
		}
		cout<<endl;
	}
	void PrevOrder_NonR()//非递归前序
	{
		stack<Node*> sn;
		if(_root)
		{
			sn.push(_root);
		}
		while (sn.empty()==NULL)
		{
			Node* root=sn.top();
			cout<<root->_date<<" ";
			sn.pop();
			if (root->left)
			{
				sn.push(root->left);
			}
		    if (root->right)
			{
				sn.push(root->right);
			}
		}
		cout<<endl;
	}
	void InOrder_NonR()
	{
		stack<Node*> sn;
		Node* cur=_root;
		while (cur||!sn.empty())
		{
			while (cur)
			{
				sn.push(cur);
				cur=cur->left;
			}
			if (!sn.empty())
			{
				Node* tmp=sn.top();
				cout<<tmp->_date<<" ";
				sn.pop();
				cur=tmp->right;
			}
		}
		cout<<endl;
	}
	void PostOrder_NonR() 
	{
		stack<Node*> s;
		Node *cur; 
		Node *pre=NULL; 
		s.push(_root);
		while(!s.empty())
		{
			cur=s.top();
			if((cur->left==NULL&&cur->right==NULL)||
				(pre!=NULL&&(pre==cur->left||pre==cur->right)))
			{
				cout<<cur->_date<<" "; 
				s.pop();
				pre=cur; 
			}
			else
			{
				if(cur->right!=NULL)
					s.push(cur->right);
				if(cur->left!=NULL) 
					s.push(cur->left);
			}
		} 
		cout<<endl;
	}
	size_t Size()
	{
		return _Size(_root);
		
	}
	size_t Depth()
	{
		return _Depth(_root);
	}
	size_t LeafSize()
	{
		return _LeafSize(_root);
	}
	size_t GetKLevel(size_t k)
	{
		return _GetKLevel(_root,k);
	}
	void Destory()
	{
		_Destory(_root);
	}

void test()
{
	int a1[10]={1,2,3,'#',4,5,6};
	BinTree<int> t1(a1,10,'#');
	t1.PrevOrder();
	t1.InOrder();
	t1.PostOrder();
	t1.PrevOrder_NonR();
	t1.InOrder_NonR();
	t1.PostOrder_NonR();
	t1.LevelOrder();
	cout<<t1.Size()<<endl;
	cout<<t1.Depth()<<endl;
	cout<<t1.LeafSize()<<endl;
	cout<<t1.GetKLevel(2);
}

#include <iostream>
#include <cstdlib>
#include <assert.h>
#include <stack>
#include<queue>
using namespace std;
template<typename T>
struct BinTreeNode
{
	BinTreeNode* left;
	BinTreeNode* right;
	T _date;
	BinTreeNode(const T& x)
		:left(NULL),_date(x)
	{}
};
template<typename T>
class BinTree
{
	typedef BinTreeNode<T> Node;
public:
	BinTree()
		:_root(NULL)
	{}
	~BinTree()
	{
		Destory();
	}
	BinTree(T* a,const T& invalid)
	{
	int index=0;
	_CreateTree( _root,invalid);
	}
	BinTree(const BinTree<T>& t)
	{
		_root=_CopyBinTree(t._root);

	}
	BinTree<T>& operator=(const BinTree<T> &t)
	{
		if(this!=&t)
		{
			swap(_root=t._root);
		}
		return *this;
	}
	void PrevOrder()
	{
		_PrevOrder(_root);
		cout<<endl;
	}
	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}
	void PostOrder()
	{
		_PostOrder(_root);
		cout<<endl;
	}
	void LevelOrder()
	{
		queue<Node*> q;
		Node* cur=_root;
		if(cur)
			q.push(cur);
		while (!q.empty())
		{
			cur=q.front();
			cout<<cur->_date<<" ";
			if(cur->left)
			{
				q.push(cur->left);
			}
			if(cur->right)
			{
				q.push(cur->right);
			}
			q.pop();
		}
		cout<<endl;
	}
	void PrevOrder_NonR()
	{
		stack<Node*> sn;
		if(_root)
		{
			sn.push(_root);
		}
		while (sn.empty()==NULL)
		{
			Node* root=sn.top();
			cout<<root->_date<<" ";
			sn.pop();
			if (root->left)
			{
				sn.push(root->left);
			}
		    if (root->right)
			{
				sn.push(root->right);
			}
		}
		cout<<endl;
	}
	void InOrder_NonR()
	{
		stack<Node*> sn;
		Node* cur=_root;
		while (cur||!sn.empty())
		{
			while (cur)
			{
				sn.push(cur);
				cur=cur->left;
			}
			if (!sn.empty())
			{
				Node* tmp=sn.top();
				cout<<tmp->_date<<" ";
				sn.pop();
				cur=tmp->right;
			}
		}
		cout<<endl;
	}
	void PostOrder_NonR() 
	{
		stack<Node*> s;
		Node *cur; 
		Node *pre=NULL; 
		s.push(_root);
		while(!s.empty())
		{
			cur=s.top();
			if((cur->left==NULL&&cur->right==NULL)||
				(pre!=NULL&&(pre==cur->left||pre==cur->right)))
			{
				cout<<cur->_date<<" "; 
				s.pop();
				pre=cur; 
			}
			else
			{
				if(cur->right!=NULL)
					s.push(cur->right);
				if(cur->left!=NULL) 
					s.push(cur->left);
			}
		} 
		cout<<endl;
	}
	size_t Size()
	{
		return _Size(_root);
		
	}
	size_t Depth()
	{
		return _Depth(_root);
	}
	size_t LeafSize()
	{
		return _LeafSize(_root);
	}
	size_t GetKLevel(size_t k)
	{
		return _GetKLevel(_root,k);
	}
	void Destory()
	{
		_Destory(_root);
	}
protected:
	void _CreateTree(Node*& root,invalid);

		}
	}
	Node*  _CopyBinTree(Node* root)
	{
		Node* newNode=NULL;
		if(!root)
		{
        newNode=new Node(root->_date);
		newNode->left=_CopyBinTree(root->left);
		newNode->right=_CopyBinTree(root->right);
		}
		return newNode;
	}
	void  _Destory(Node* root)
	{
		if(!root)
			return;
		_Destory(root->left);
		_Destory(root->right);
		delete root;
	}
	void  _PrevOrder(Node* root)
	{
		if(root==NULL)
			return;
        cout<<root->_date<<" ";
		_PrevOrder(root->left);
		_PrevOrder(root->right);
		
	}
	void  _InOrder(Node* root)
	{
		if(root==NULL)
			return;
		_InOrder(root->left);
         cout<<root->_date<<" ";
		_InOrder(root->right);
		
	}
	void  _PostOrder(Node* root)
	{
		if(!root)
			return;
		_PostOrder(root->left);
		_PostOrder(root->right);
		cout<<root->_date<<" ";
	}
	int _Size(Node* root)
	{

		if (!root)
		return 0;
		return _Size(root->left)+_Size(root->right)+1;
	}
	int _Depth(Node* root)
	{
		if(!root)
			return 0;
		int leftchilddepth=_Depth(root->left)+1;
		int rightchilddepth=_Depth(root->right)+1;
		if(leftchilddepth>=rightchilddepth)
		{
			return leftchilddepth;
		}
		else
		{
			return rightchilddepth;
		}
	}
	int _GetKLevel(Node* root,k-1);
	}
	int _LeafSize(Node* root)
	{
		if(root==NULL)
			return 0;
		if(root->left==NULL&&root->right==NULL)
			return 1;
		return _LeafSize(root->left)+_LeafSize(root->right);
	}
	Node* _root;
};
void test()
{
	int a1[10]={1,'#');
	t1.PrevOrder();
	t1.InOrder();
	t1.PostOrder();
	t1.PrevOrder_NonR();
	t1.InOrder_NonR();
	t1.PostOrder_NonR();
	t1.LevelOrder();
	cout<<t1.Size()<<endl;
	cout<<t1.Depth()<<endl;
	cout<<t1.LeafSize()<<endl;
	cout<<t1.GetKLevel(2);
}

<pre name="code" class="cpp">void test2()
{
   int array1[10] = { 1,6 };
   BinTree<int> tree(array1,'#');
  BinTree<int> tree1=tree;//拷贝
   tree1.PrevOrder();
 

}

#include "BinTree.h"
int main()
{
<span style="white-space:pre">	</span>test();
<span style="white-space:pre">	</span>test2();
<span style="white-space:pre">	</span>system("pause");
<span style="white-space:pre">	</span>return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!