数据结构==二叉树（链表实现）

红太狼 2022-06-12 14:51 176阅读 0赞

链表实现二叉树的原理其实和数组实现的原理大同小异，但是因为是链表的缘故，所以操作的灵活性要比数组更加好，难度也比数组更高。链表实现二叉树，多了一个很关键的东西，那就是遍历的方法：前序遍历、中序遍历和后序遍历。

课程要求：完成树的基本操作  
    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 2 0        (左右根)  
              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 <iostream>
    
    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<<this->index<<"    "<<this->data<<endl;
    	if(this->pLChild != NULL)
    	{
    		this->pLChild->PreorderTraversal();
    	}
    	if(this->pRChild != NULL)
    	{
    		this->pRChild->PreorderTraversal();
    	}
    }
    
    void Node::InorderTraversal()
    {
    	if(this->pLChild != NULL)
    	{
    		this->pLChild->InorderTraversal();
    	}
    	cout<<this->index<<"    "<<this->data<<endl;
    	if(this->pRChild != NULL)
    	{
    		this->pRChild->InorderTraversal();
    	}	
    }	
    
    void Node::PostorderTraversal()
    {
    	if(this->pLChild != NULL)
    	{
    		this->pLChild->PostorderTraversal();
    	}
    	if(this->pRChild != NULL)
    	{
    		this->pRChild->PostorderTraversal();
    	}		
    	cout<<this->index<<"    "<<this->data<<endl;
    }

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 <iostream>
    
    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 <iostream>
    
    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;
    }