데이터 구조 = = 이 진 트 리 (링크 구현)

링크 가 이 진 트 리 를 실현 하 는 원 리 는 배열 이 실현 하 는 원리 와 크게 다 르 지만 링크 이기 때문에 조작 의 유연성 이 배열 보다 더욱 좋 고 난이도 도 배열 보다 높다.링크 는 이 진 트 리 를 실현 하고 중요 한 것 이 하나 더 생 겼 습 니 다. 그것 은 바로 옮 겨 다 니 는 방법 입 니 다. 앞 순 서 는 옮 겨 다 니 고 중간 순 서 는 옮 겨 다 니 며 뒤 순 서 는 옮 겨 다 니 는 것 입 니 다.
과정 요구: 나무의 기본 조작 완성    1. 나무의 생 성과 소각    2. 나무 에 맺 힌 점 의 검색    3. 트 리 의 노드 추가 및 삭제    4. 나무 에 맺 힌 점 의 옮 겨 다 니 기    Tree();                                                                //트 리 만 들 기    ~Tree();                                                            //나 무 를 소각 하 다    Node* SearchNode(int nodeindex);                                    //색인 에 근거 하여 결점 을 찾다    bool AddNode(int nodeindex, int direction, Node* pNode);            //노드 추가    bool DeleteNode(int nodeindex, Node* pNode);                        //노드 삭제    void PreorderTraversal();                                            //앞 순 서 를 편력 하 다.    void InorderTraversal();                                            //중간 순서 로 옮 겨 다 닌 다.    void PostorderTraversal();                                            //뒤 순 서 를 옮 겨 다 닌 다.         결점 요소: 인덱스  데이터  왼쪽 아이 지침 오른쪽 아이 지침 아버지 결점 지침         이전 순서: 0, 1, 3, 4, 2, 5, 6        (위 에서 아래로)                a e b c h q     역순: 3, 1, 4, 0, 5, 2, 6        (왼쪽 에서 오른쪽으로)              e a b   h c q     후 순 옮 겨 다 니 기: 3, 4, 1, 5, 6, 20        (좌우 근)              e b a h q c                (0)                      a(1)    c(2)              e(3)  b(4)  h(5)  q(6)   
프로그램 구현:
node.h

#ifndef _NODE_H
#define _NODE_H

class Node {
public:
	Node();
	Node* SearchNode(int nodeindex);
	void DeleteNode();
	void PreorderTraversal();										//    
	void InorderTraversal();										//    
	void PostorderTraversal();										//    
	int index;
	char data;
	Node* pLChild;
	Node* pRChild;
	Node* pParent;
};

#endif

node.cpp

#include "node.h"
#include 

using namespace std;

Node::Node()
{
	index = 0;
	data = ' ';
	pLChild = NULL;
	pRChild = NULL;
	pParent = NULL;
}

Node* Node::SearchNode(int nodeindex)
{
	if(this->index == nodeindex)
	{
		return this;
	}
	
	Node *temp;
	if(this->pLChild != NULL)
	{
		if(this->pLChild->index == nodeindex)
		{
			return this->pLChild;
		}
		else 
		{
			temp = this->pLChild->SearchNode(nodeindex);
			if(temp != NULL)
			{
				return temp;					
			}
		}
	}
	
	if(this->pRChild != NULL)
	{
		if(this->pRChild->index == nodeindex)
		{
			return this->pRChild;
		}
		else 
		{
			temp = this->pRChild->SearchNode(nodeindex);
			if(temp != NULL)
			{
				return temp;					
			}
		}
	}
	
	return NULL;
}

void Node::DeleteNode()
{
	if(this->pLChild != NULL)
	{
		this->pLChild->DeleteNode();
	}
	if(this->pRChild != NULL)
	{
		this->pRChild->DeleteNode();
	}
	if(this->pParent != NULL)
	{
		if(this->pParent->pLChild == this)
		{
			this->pParent->pLChild = NULL;
		}
		if(this->pParent->pRChild == this)
		{
			this->pParent->pRChild = NULL;
		}
	}
	delete this;
}

void Node::PreorderTraversal()
{
	cout<index<data<pLChild != NULL)
	{
		this->pLChild->PreorderTraversal();
	}
	if(this->pRChild != NULL)
	{
		this->pRChild->PreorderTraversal();
	}
}

void Node::InorderTraversal()
{
	if(this->pLChild != NULL)
	{
		this->pLChild->InorderTraversal();
	}
	cout<index<data<pRChild != NULL)
	{
		this->pRChild->InorderTraversal();
	}	
}	

void Node::PostorderTraversal()
{
	if(this->pLChild != NULL)
	{
		this->pLChild->PostorderTraversal();
	}
	if(this->pRChild != NULL)
	{
		this->pRChild->PostorderTraversal();
	}		
	cout<index<data<

linktree.h

/*****************       *********************/
#ifndef _LINKTREE_H
#define _LINKTREE_H

#include "node.h"

class Tree
{
	Node* m_pRoot;
public:
	Tree();																//   
	~Tree();															//   
	Node* SearchNode(int nodeindex);									//        
	bool AddNode(int nodeindex, int direction, Node* pNode);			//    
	bool DeleteNode(int nodeindex, Node* pNode);						//    
	void PreorderTraversal();											//    
	void InorderTraversal();											//    
	void PostorderTraversal();											//    
};

#endif

linktree.cpp

/*****************       *********************/
#include "linktree.h"
#include 

using namespace std;

Tree::Tree()		//      
{
	m_pRoot = new Node();
}

Tree::~Tree()
{
	//DeleteNode(0, NULL);
	m_pRoot->DeleteNode();
}

Node* Tree::SearchNode(int nodeIndex)
{
	return m_pRoot->SearchNode(nodeIndex);
}

bool Tree::AddNode(int nodeIndex, int direction, Node* pNode)
{
	Node* temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}
	
	Node* node = new Node();
	if(node == NULL)
	{
		return false;
	}
	node->index = pNode->index;
	node->data = pNode->data;
	node->pParent = temp;
	
	if(direction == 0)
	{
		temp->pLChild = node;
	}
	else if(direction == 1)
	{
		temp->pRChild = node;
	}
	return true;
}

bool Tree::DeleteNode(int nodeIndex, Node* pNode)
{	
	Node* temp = SearchNode(nodeIndex);
	if(temp == NULL)
	{
		return false;
	}
	
	if(pNode != NULL)
	{
		pNode->data = temp->data;
	}
	
	temp->DeleteNode();
	return true;
}

void Tree::PreorderTraversal()
{
	m_pRoot->PreorderTraversal();
}

void Tree::InorderTraversal()
{
	m_pRoot->InorderTraversal();
}	

void Tree::PostorderTraversal()
{
	m_pRoot->PostorderTraversal();
}		

main.cpp

#include "linktree.h"
#include 

using namespace std;

int main()
{
	Tree *tree = new Tree();
	Node* node1 = new Node;
	node1->index = 1;
	node1->data = 'a';
	
	Node* node2 = new Node;
	node2->index = 2;
	node2->data = 'c';
	
	Node* node3 = new Node;
	node3->index = 3;
	node3->data = 'e';
	
	Node* node4 = new Node;
	node4->index = 4;
	node4->data = 'b';
	
	Node* node5 = new Node;
	node5->index = 5;
	node5->data = 'h';
	
	Node* node6 = new Node;
	node6->index = 6;
	node6->data = 'q';
	
	tree->AddNode(0, 0, node1);
	tree->AddNode(0, 1, node2);
	tree->AddNode(1, 0, node3);
	tree->AddNode(1, 1, node4);
	tree->AddNode(2, 0, node5);
	tree->AddNode(2, 1, node6);
	
	tree->DeleteNode(2, NULL);
	//tree->PreorderTraversal();
	//tree->InorderTraversal();		
	tree->PostorderTraversal();
		
	delete tree;
	
	return 0;
}