二叉树

二叉树:

二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。

实例：

节点结构:

template <class T>
struct BinaryTreeNode
{
	BinaryTreeNode(T data)
		:_data(data)
		,_left(NULL)
		,_right(NULL)
	{}
	T _data;
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
};

二叉树成员变量；

protected:
	BinaryTreeNode<T>* _root;

构造函数：调用_CreateTree

Node* _CreateTree(const T* a,size_t size,size_t& index,const T& invalid)//注意index用引用
	{
		Node* root=NULL;
		if((index<size)&&(a[index]!=invalid))
		{
			root=new Node(a[index]);
			root->_left=_CreateTree(a,size,++index,invalid);
			root->_right=_CreateTree(a,size,++index,invalid);
		}
		return root;
	}

析构函数：调用_Destory

void _Destory(Node* root)
	{
		Node* cur=root;
		Node* del=cur;
		if(cur->_left!=NULL)
		{
			_Destory(cur->_left);
		}
		if(cur->_right!=NULL)
		{
			_Destory(cur->_right);
		}
		delete del;
	}

拷贝构造函数：调用_Copy

Node* _Copy(Node* root)
	{
		if(root==NULL)
			return NULL;
		Node* newroot=new Node(root->_data);
		Node* cur=newroot;
		cur->_left=_Copy(root->_left);
		cur->_right=_Copy(root->_right);
		return newroot;
	}

重载赋值运算符

BinaryTree& operator=(BinaryTree tree)
	{
		swap(_root,tree._root);
		return *this;
	}

前序遍历：调用_PrevOrder

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

中序遍历：调用_InOrder

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

后序遍历：调用_PoseOrder

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

求深度：调用_Depth

size_t _Depth(Node* root)
	{
		Node* cur=root;
		size_t depth=0;
		if(cur==NULL)
			return 0;
		else
		{
			depth=1;
			size_t leftdepth=_Depth(cur->_left);
			size_t rightdepth=_Depth(cur->_right);
			if(leftdepth>=rightdepth)
			{
				return depth+leftdepth;
			}
			else
			{
				return depth+rightdepth;
			}
		}
	}

求size：调用_Size

size_t _Size(Node* root)
	{
		size_t count=0;
		if(root==NULL)
			return 0;
		else
		{
			++count;
		}
		count+=_Size(root->_left);
		count+=_Size(root->_right);
		return count;
	}

求叶子节点的个数：调用_LeafSize

size_t _LeafSize(Node* root)
	{
		size_t size=0;
		if(root==NULL)
			return 0;
		else
		{
			if((root->_left==NULL)&&(root->_right==NULL))
			{
				size=1;
				return size;
			}
			else
			{
				size_t left=_LeafSize(root->_left);
				size_t right=_LeafSize(root->_right);
				return left+right;
			}
		}
	}

二叉树

原文：http://lovemeright.blog.51cto.com/10808587/1765914