zheng.cpp

二叉树木后序遍历代码欢迎批评指正,如果有好的代码欢迎发到该网站让大家共享

#include "Zheng.h"
#include <iostream.h>

BTree::BTree()
{
	pRoot = NULL;
	int nArr[] = {1,2,8,6,7,2,0,-1};
	int *nTemp = nArr;
	this->CreatBTree(nTemp,pRoot);
}
void BTree::CreatBTree(ElemType* &pArr,BTreeNode *&pCur)
{
	while (*pArr != -1){
		pCur = new BTreeNode();
		pCur->Data = *pArr;
		pCur->pLeft = NULL;
		pCur->pRight = NULL;
		pArr++;
		CreatBTree(pArr,pCur->pLeft);
		CreatBTree(pArr,pCur->pRight);
	}
}

BOOL BTree::IsBTreeEmpty()
{
	return pRoot == NULL;
}

ULONG BTree::GetBTreeLength()
{
	if (pRoot == NULL){
		return 0;
	}
	else{
		int nDepthLeft = GetBTreeLength(pRoot->pLeft);
		int nDepthRight = GetBTreeLength(pRoot->pRight);
		if (nDepthLeft >nDepthRight){
			return nDepthLeft+1;
		}
		else{
			return nDepthRight+1;
		}
	}
}
ULONG BTree::GetBTreeLength(BTreeNode *pBtr)
{
	if (pBtr == NULL){
		return 0;
	}
	else{
		int nDepthLeft = GetBTreeLength(pBtr->pLeft);
		int nDepthRight = GetBTreeLength(pBtr->pRight);
		if (nDepthLeft >nDepthRight){
			return nDepthLeft+1;
		}
		else{
			return nDepthRight+1;
		}
	}
}

ULONG BTree::GetBTreeCount()
{
	if (pRoot == NULL){
		return 0;
	}
	else
	{
		int nCountLeft = GetBTreeCount(pRoot->pLeft);
		int nCountRight = GetBTreeCount(pRoot->pRight);
		return nCountLeft+nCountRight+1;
	}
}
ULONG BTree::GetBTreeCount(BTreeNode *pBtr)
{
	if (pBtr == NULL){
		return 0;
	}
	else
	{
		int nCountLeft = GetBTreeCount(pBtr->pLeft);
		int nCountRight = GetBTreeCount(pBtr->pRight);
		return nCountLeft+nCountRight+1;
	}
}
ULONG BTree::GetBTreeLeafCount(BTreeNode *pBtr)
{
	int nLeafSum = 0;
	if (pBtr == NULL)
	{
		return 0;
	}
	else{
		int nLeafCountLeft = GetBTreeLeafCount(pBtr->pLeft);
		int nLeafCountRight = GetBTreeLeafCount(pBtr->pRight);
		if (nLeafCountLeft == 0 && nLeafCountRight == 0)
		{
			nLeafSum++;
		}
	}
	return nLeafSum;
}

void BTree::TraversBTree(TraversType TraversType)
{
	
}

void BTree::preOrderTravers()
{
	BTreeNode* pBtr;
	Stack stack;
	stack.Push(pRoot);
	while(!stack.IsStackEmpty()){
		while (stack.GetTop()){
			pBtr = stack.GetTop();
			cout<<pBtr->Data<<endl;
			stack.Push(pBtr->pLeft);
		}
		stack.Pop();
		if (!stack.IsStackEmpty())
		{
			//Important must be care!
			pBtr = stack.GetTop();
			stack.Pop();
			
			stack.Push(pBtr->pRight);
		}
	}
}

void BTree::InOrderTravers()
{
	BTreeNode* pBtr;
	Stack stack;
	stack.Push(pRoot);
	while(!stack.IsStackEmpty()){
		while (stack.GetTop()){
			pBtr = stack.GetTop();
//			cout<<pBtr->Data<<endl;
			stack.Push(pBtr->pLeft);
		}
		stack.Pop();
		if (!stack.IsStackEmpty()){
			//Important must be care!
			cout<<stack.GetTop()->Data;
			pBtr = stack.GetTop();
			stack.Pop();
			stack.Push(pBtr->pRight);
		}
	}
}




void BTree::PostOrderTravers()
{
	BTreeNode * pCur = pRoot;
	BTreeNode * pPre = NULL;
	Stack stack;
	while (!pCur || !stack.IsStackEmpty()){
		while (pCur){
			stack.Push(pCur);
			pCur = pCur->pLeft;
		}
		pCur = stack.GetTop();
		if (pCur->pRight == NULL || pCur->pRight == pPre){
			cout<<pCur->Data<<endl;
			pPre = pCur;
			stack.Pop();
			pCur = NULL;
		}
		else{
			pCur = pCur->pRight;
		}
	}
}

void BTree::Path(ElemType a_Data)
{
	BTreeNode * pCur = pRoot;
	BTreeNode * pPre = NULL;
	Stack stack;
	Stack outStack;
//	int nFlag = 0;
	while (pCur || !stack.IsStackEmpty()){
		while (pCur){
			stack.Push(pCur);
			pCur = pCur->pLeft;
		}
		pCur = stack.GetTop();
		if (pCur->pRight == NULL || pCur->pRight == pPre){
			if (pCur->Data == a_Data){
				break;									
			}
			pPre = pCur;
			stack.Pop();
			pCur = NULL;
		}
		else{
			pCur = pCur->pRight;
		}
	}
	while (!stack.IsStackEmpty())
	{
		pCur = stack.GetTop();
		stack.Pop();
		outStack.Push(pCur);
	}
	while (!outStack.IsStackEmpty())
	{
		cout<<outStack.GetTop()->Data<<endl;
		outStack.Pop();
	}
}

int BTree::GetLayers(BTreeNode *pCur,ElemType a_Data)
{
	if (pCur == NULL)
	{
		return 0;
	}

	if (pCur->Data == a_Data)
	{
		return 1;
	}
	else{
		int nLeft = GetLayers(pCur->pLeft,a_Data);
		int nRight = GetLayers(pCur->pRight,a_Data);
/*
		if (nLeft != 0){
			return nLeft+1;
		}
		if (nRight != 0)
		{
			return nRight +1;
		}
*/
		if (nLeft + nRight != 0){
			return (nLeft+nRight+1);
		}
		else{
			return 0;
		}
				
	}
}
Stack::Stack()
{
	memset(pStack,0,sizeof(pStack));
	nTop = 0;
}

BOOL Stack::IsStackEmpty()
{
	return nTop==0;
}

BOOL Stack::Push(BTreeNode* pBtr)
{
	if (nTop == 99){
		cout<<"Exceed the Stack!";
		return FALSE;
	}
	
	pStack[nTop] = pBtr;
	nTop++;
	return TRUE;
}

BTreeNode* Stack::Pop()
{
	nTop--;
	BTreeNode* pTemp;
	pTemp = pStack[nTop];
	return pTemp;
}

BTreeNode* Stack::GetTop()
{
	return pStack[nTop-1];
}
void main()
{
	BTree btr1;
	btr1.Path(0);
	cout<<btr1.GetLayers(btr1.pRoot,0);

}