Raison D'etre

You do the little job you're trained to do.Pull a lever. Push a button.You don't understand any of it. And then you just die.

2010-09-18

二元樹的走訪

二元樹的走訪

在這篇文章中我們建立一個二元樹

然後用遞回的方式來走訪他

除了常見的傳統走訪方式 (前序 中序 後序)

另外還有一種橫向的走訪方式

 

 

以下程式碼為一個二元樹的物件

		#define LEFT 0
		#define RIGHT 1
		#define NAME_LEN 128
		 
		 
		// Note:
		// If you delete the node.
		// Its child nodes will be deleted in same time.
		// Detail can be found in destruct.
		class CTreeNode
		{
		public:
		CTreeNode(const char* acName_);
		~CTreeNode();
		 
		BOOL Add(int iSide_, char* acName_);
		BOOL Add(int iSide_, CTreeNode* pChildNode_);
		 
		CTreeNode* GetNode(int iSide_) const;
		
		void GetName(char* acName_);
		 
		private:
		char _acName[NAME_LEN]; 
		CTreeNode* _pTreeNode[2];
		
		};
		 
		CTreeNode::CTreeNode(const char* acName_)
		{
		this->_pTreeNode[LEFT] = NULL;
		 
		this->_pTreeNode[RIGHT] = NULL;
		
		::memset(this->_acName, 0, sizeof(this->_acName));
		 
		::memcpy(this->_acName, acName_, sizeof(this->_acName));
		 
		//std::cout << this->_acName << "  constructed" << std::endl;
		}
		 
		 
		CTreeNode::~CTreeNode()
		{
		if(this->_pTreeNode[LEFT] != NULL)
		delete this->_pTreeNode[LEFT];
		 
		if(this->_pTreeNode[RIGHT] != NULL)
		delete this->_pTreeNode[RIGHT];
		 
		//std::cout << this->_acName << "  destructed" << std::endl;
		
		}
		 
		 
		void CTreeNode::GetName(char* acName_)
		{
		::memcpy(acName_, this->_acName, sizeof(this->_acName));
		}
		 
		 
		BOOL CTreeNode::Add(int iSide_, CTreeNode* pChildNode_)
		{
		if(this->_pTreeNode[iSide_] != NULL)
		{
		assert(0);
		return FALSE;
		}
		
		this->_pTreeNode[iSide_] = pChildNode_;
		 
		return TRUE;
		}
		 
		 
		BOOL CTreeNode::Add(int iSide_, char* acName_)
		{
		return this->Add(iSide_, new CTreeNode(acName_));
		}
		 
		 
		CTreeNode* CTreeNode::GetNode(int iSide_) const
		{
		return this->_pTreeNode[iSide_];
		}

 

 

 

我們使用手動的方式來建立我們需要的二元樹

		void Program()
		{
		CTreeNode* pRootNode = new CTreeNode("Root");
		 
		 
		pRootNode->Add(0, "0");
		
		pRootNode->GetNode(0)->Add(0, "0-0");
		pRootNode->GetNode(0)->GetNode(0)->Add(0, "0-0-0");
		pRootNode->GetNode(0)->GetNode(0)->Add(1, "0-0-1");
		 
		pRootNode->GetNode(0)->Add(1, "0-1");
		pRootNode->GetNode(0)->GetNode(1)->Add(0, "0-1-0");
		pRootNode->GetNode(0)->GetNode(1)->Add(1, "0-1-1");
		 
		 
		pRootNode->Add(1, "1");
		pRootNode->GetNode(1)->Add(0, "1-0");
		pRootNode->GetNode(1)->Add(1, "1-1");
		pRootNode->GetNode(1)->GetNode(1)->Add(1, "1-1-1");
		 
		 
		TraditionRecurrence(pRootNode);
		
		std::cout << std::endl;
		 
		int i=0;
		while(RecurrenceByLevel(pRootNode, i++)){}
		
		 
		delete pRootNode;
		}
		 
		void Visit(CTreeNode* pNode_)
		{
		char acBuff[128];
		::memset(acBuff, 0, sizeof(acBuff));
		pNode_->GetName(acBuff);
		std::cout << acBuff << std::endl;
		}

 

 

 

這是傳統的二元樹走訪方式

		void TraditionRecurrence(CTreeNode* pNode_)
		{
		if(pNode_==NULL)
		return;
		 
		// You can swap their sequence.
		// The result will be different (pre order, mid order, post order)
		Visit(pNode_);
		 
		TraditionRecurrence(pNode_->GetNode(0));
		 
		TraditionRecurrence(pNode_->GetNode(1));
		}

 

 

 

這是橫向的走訪方式

		int RecurrenceByLevel(CTreeNode* pNode_, int iLevel_)
		{
		if(!pNode_ || iLevel_<0)
		return 0;
		 
		if(iLevel_==0)
		{
		Visit(pNode_);
		return 1;
		}
		 
		return RecurrenceByLevel(pNode_->GetNode(0),iLevel_-1) + RecurrenceByLevel(pNode_->GetNode(1),iLevel_-1);
		}