数据结构--二叉树(1)-创新互联

二叉树

创新互联是网站建设专家,致力于互联网品牌建设与网络营销，专业领域包括成都网站设计、做网站、电商网站制作开发、微信平台小程序开发、微信营销、系统平台开发，与其他网站设计及系统开发公司不同，我们的整合解决方案结合了恒基网络品牌建设经验和互联网整合营销的理念，并将策略和执行紧密结合，且不断评估并优化我们的方案，为客户提供全方位的互联网品牌整合方案！

构建：二叉树的构建采用的是先序遍历，->先储存根节点然后左右节点，用递归的思想将所有数据放在树中。

代码实现：实现了4种访问方法，先序，中序，后序，和层序的访问方法都采用递归的方式。

#include
#include
#include
using namespace std;

template 
struct rootnode
{
	T _value;
	rootnode *_leftnode;
	rootnode *_rightnode;
	rootnode(T value)
		: _value(value),
		_leftnode(NULL),
		_rightnode(NULL)
	{}
};

template 
class BinaryTree
{
public:
	BinaryTree( T *str)
	{
		T *tmp = str;
		_root = _BinaryTree(tmp);
	}
	~BinaryTree()
	{
		_Clear(_root);
	}
	BinaryTree (BinaryTree &t)
	{
		_root=_Copy(t._root);
	}
	BinaryTree& operator=(BinaryTree t)
	{
		if (*this != t)
		{
			swap(_root, t._root);
		}
	}
	void Fastorder()
	{
		_Fastorder(_root);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	void Postorder()
	{
		_Postorder(_root);
	}
	void Levelorder()
	{
		queue*> q;
			if (_root == NULL)
			{
				return;
			}
			q.push(_root);
			while (!q.empty())
			{
				rootnode* root = q.front();
				cout << root->_value;
				q.pop();
				if (root->_leftnode != NULL)
				{
					q.push(root->_leftnode);
				}
				if (root->_rightnode != NULL)
				{
					q.push(root->_rightnode);
				}
			}	
	}
	int leafnum()
	{
		int num = 0;
		num=_Leafnum(_root,num);
		return num;
	}
	int Size()
	{
		int size = 0;
		_Size(_root,size);
		return size;
	}
	int Depth()
	{
		int Depth = _Depth(_root);
		return Depth;
	}
	void NRfastorder()
	{
		stack*> s;
		if (_root != NULL)
		{
			s.push(_root);
		}
		while (!s.empty())
		{
			rootnode* front=s.top();
			cout<_value;
			s.pop();
			if (front->_rightnode != NULL)
			{
				s.push(front->_rightnode);
			}
			if (front->_leftnode != NULL)
			{
				s.push(front->_leftnode);
			}
		}
	}
	void NRinorder()
	{
		stack*>s;
		rootnode*cur = _root;
		rootnode* top = NULL;
		while (cur||!s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_leftnode;
			}			
			if (top != s.top()->_rightnode)
			{
				top = s.top();
				cout << top->_value;
				s.pop();
				cur = top->_rightnode;
			}
			else
			{
				top = s.top();
				cout << top->_value;
				s.pop();
			}

		}
	}

	void NRpostorder()
	{
		rootnode*cur = _root;
		stack*> s;
		rootnode*top = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_leftnode;
			}
			if (s.top()->_rightnode != NULL&&top != s.top()->_rightnode)
			{

				top = s.top();
				cur = top->_rightnode;
			
			}
			else
			{
				top = s.top();
				s.pop();
				cout << top->_value;
			}
		

		}
	}
protected:
	rootnode* _BinaryTree(T *&str)
	{
		rootnode *root = NULL;
		if (*str != '#'&&*str != '\0')
		{
			root = new rootnode(*str);
			str++;
			root->_leftnode = _BinaryTree(str);
			str++;
			root->_rightnode = _BinaryTree(str);
		}
		return root;
	}
	void _Fastorder(rootnode *&root)
	{
		if (root == NULL)
		{
			
			return;
		}
		else
		{
			cout << root->_value;
			_Fastorder(root->_leftnode);
			_Fastorder(root->_rightnode);
			
		}
	}
	void _Inorder(rootnode *root)
	{
		if (root == NULL)
		{
			return;
		}
		_Inorder(root->_leftnode);
		cout << root->_value;
		_Inorder(root->_rightnode);
	}

	void _Postorder(rootnode *root)
	{
		if (root == NULL)
		{
			return;
		}
		_Postorder(root->_leftnode);
		_Postorder(root->_rightnode);
		cout << root->_value;
	}
	void _Clear(rootnode *root)
	{
		if (root == NULL)
		{
			return;
		}
		rootnode *tmp = root->_leftnode;
		rootnode *tmp2 = root->_rightnode;
		delete root;
		_Clear(tmp);
		_Clear(tmp2);
	}
	rootnode* _Copy(rootnode *root)
	{
		rootnode *newroot = NULL;
		if (root == NULL)
		{
			return newroot;
		}
		newroot = new rootnode(root->_value);
		newroot->_leftnode = _Copy(root->_leftnode);
		newroot->_rightnode = _Copy(root->_rightnode);
		return newroot;
	}
	int _Size(rootnode *root,int &size)
	{
		if (root == NULL)
		{
			return 0;
		}
		size++;
		_Size(root->_leftnode,size);
		_Size(root->_rightnode,size);
		return size;
	}
	int _Depth(rootnode *root)
	{
		if (root==NULL)
		{
			return 0;
		}
		int hight = 1;
		int left = 0;
		int right = 0;
		left += _Depth(root->_leftnode) + hight;
		right += _Depth(root->_rightnode) + hight;
		if (left > right)
		{
			return left;
		}
		else
		{
			return right;
		}
		
	}
	int _Leafnum(rootnode* root,int &num)
	{
		if (root == NULL)
		{
			return 0;
		}
		if (root->_leftnode == NULL&&root->_rightnode == NULL)
		{
			num++;
		}
		_Leafnum(root->_leftnode, num);
		_Leafnum(root->_rightnode, num);
		return num;
	}
private:
	rootnode *_root;
};

void Test1()
{
	char *str = "123##45##6##78###";
	BinaryTree b1(str);
	BinaryTree b2(b1);
	BinaryTree b3 = b2;
	b1.Fastorder();
	cout << endl;
	b1.Inorder();
	cout << endl;
	b1.Postorder();
	cout << endl;
	b2.Fastorder();
	cout << endl;
	b3.Fastorder();
	cout << endl;
	cout << b3.Size()<
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
            

            当前文章：数据结构--二叉树(1)-创新互联            

            分享地址：http://6mz.cn/article/iihce.html