두 갈래 나무의 몇 가지 전형적인 예제

1. 두 갈래 나무의 높이를 구한다

int _GetTreeHight(Node* pRoot)
	{
		if(pRoot==NULL)
			return 0;

		if(pRoot->_pLeft==NULL&&pRoot->_pRight==NULL)
			return 1;

		int left=_GetTreeHight(pRoot->_pLeft)+1;
		int right=_GetTreeHight(pRoot->_pRight)+1;

		return left>right?left:right;
	}

2.잎결점의 개수를 구하다

	int _LeafNodeNum(Node* pRoot)
	{
		if(pRoot==NULL)
			return 0;

		if(pRoot->_pLeft==NULL&&pRoot->_pRight==NULL)
			return 1;

		int left=_LeafNodeNum(pRoot->_pLeft);
		int right=_LeafNodeNum(pRoot->_pRight);

		return left+right;
	}

3.하나의 데이터가 두 갈래 나무에 있는지 아닌지를 판단하다

Node* _Find(Node* pRoot,const T& data)
	{
		if(pRoot==NULL)
			return NULL;

		if(pRoot->_value==data)
			return pRoot;

		Node* pcur=_Find(pRoot->_pLeft,data);
		if(pcur)
			return pcur;

		return _Find(pRoot->_pRight,data);
	}

4. 두 갈래 나무 중 두 개의 결점을 구하는 최근 공공조상의 결점

	bool GetWay(Node* pRoot,Node* N,vector*>& v,size_t index)
	{
		if(pRoot==NULL)
			return false;

		v.push_back(pRoot);
		if(pRoot==N)
			return true;

		pRoot=v.back();
		if(GetWay(pRoot->_pLeft,N,v,index+1))
			return true;

		v.pop_back();
		pRoot=v.back();
		return GetWay(pRoot->_pRight,N,v,index+1);
	}

	Node* _LastAncestorNode(Node* pRoot,Node* N1,Node* N2)
	{
		if(pRoot==NULL||(pRoot->_pLeft==NULL&&pRoot->_pRight==NULL))
			return NULL;

		vector*> v1;
		vector*> v2;
		if(GetWay(pRoot,N1,v1,0)&&GetWay(pRoot,N2,v2,0))
		{
			for(size_t i=v1.size();i>0;--i)
			{
				for(size_t j=v2.size();j>0;--j)
				{
					if(v1[i-1]==v2[j-1])
						return v1[i-1];
				}
			}
		}
		
		return NULL;
	}

5.노드의 양친 노드 찾기

	Node* _FindParent(Node* pRoot,Node* pRet)
	{
		if(pRoot==NULL||pRet==pRoot)
			return NULL;

		if(pRoot->_pLeft==pRet||pRoot->_pRight==pRet)
		{
			return pRoot;
		}
		
		Node* pcur=_FindParent(pRoot->_pLeft,pRet);
		if(pcur)
			return pcur;

		return _FindParent(pRoot->_pRight,pRet);

	}

6. 두 갈래 나무 중 가장 먼 두 결점 사이의 거리를 구한다

	int _DistanceOfNodes(Node* pRoot)
	{
		if(pRoot==NULL)
			return 0;

		int left=_GetTreeHight(pRoot->_pLeft);
		int right=_GetTreeHight(pRoot->_pRight);

		return left+right;
	}

7. 두 갈래 나무가 완전 두 갈래 나무인지 아닌지 판단

	bool _IsCompleteBinaryTree(Node* pRoot)
	{
		if(pRoot==NULL)
			return false;

		queue*> q;
		q.push(pRoot);

		while((pRoot=q.front())!=NULL)
		{
			q.push(pRoot->_pLeft);
			q.push(pRoot->_pRight);
			q.pop();
		}

		while(!q.empty()&&(pRoot=q.front())==NULL)
		{
			q.pop();	
		}

		if(!q.empty())
			return false;

		return true;

	}

8. 두 갈래 나무의 거울 구하기

	BinaryTree ImageBinaryTree()
	{
		BinaryTree bt;
		bt._pRoot=CopyTree(_pRoot);
		_ImageBinaryTree(bt._pRoot);
		return bt;
	}
	
        void _ImageBinaryTree(Node* pRoot)
	{
		Node* pcur=pRoot;

		if(pcur==NULL||(pcur->_pLeft==NULL&&pcur->_pRight==NULL))
			return ;

		swap(pcur->_pLeft,pcur->_pRight);

		_ImageBinaryTree(pcur->_pLeft);
		_ImageBinaryTree(pcur->_pRight);
	}