二叉树实现（链表实现）

た入场券 2022-02-18 11:43 238阅读 0赞

### 二叉树链表实现 ###

node.h

#pragma once
    #ifndef NODE_H_
    #define NODE_H_
    class Node 
    {
    public:
    	Node();
    	Node *SearchNode(int nodeIndex);
    	void DeleteNode();
    	void PreorderTraversal();
    	void InorderTraversal();
    	void PostorderTraversal();  //遍历
    	int index;
    	int data;
    	Node *pLChild;
    	Node *pRChild;
    	Node *pParent;
    };
    #endif // !NODE_H_

node.cpp

#include "Node.h"
    #include <iostream>
    using namespace std;
    Node::Node()
    {
    	index = 0;
    	data = 0;
    	pLChild = nullptr;
    	pRChild = nullptr;
    	pParent = nullptr;
    }
    
    Node * Node::SearchNode(int nodeIndex)
    {
    	if (this->index == nodeIndex)
    	{
    		return this;
    	}
    	Node *temp = NULL;
    	if (this->pLChild)
    	{
    		if (this->pLChild->index == nodeIndex) {
    			return this->pLChild;
    		}
    		else {
    			temp=this->pLChild->SearchNode(nodeIndex);
    			if (temp) //左边找到相应节点后就不继续向下寻找
    			{
    				return temp;
    			}
    		}
    	}
    	if (this->pRChild)
    	{
    		if (this->pRChild->index == nodeIndex) {
    			return this->pRChild;
    		}
    		else {
    			temp=this->pRChild->SearchNode(nodeIndex);
    			return temp;
    		
    		}
    	}
    	return nullptr;
    }
    
    void Node::DeleteNode()
    {
    	//删除自己的左右孩子
    	if (this->pLChild)
    	{
    		this->pLChild->DeleteNode();
    	}
    	if (this->pRChild)
    	{
    		this->pRChild->DeleteNode();
    	}
    	if (this->pParent)
    	{//将父节点指向该节点的指针置为null
    		if (this->pParent->pLChild == this)
    		{
    			this->pParent->pLChild = nullptr;
    		}
    		if (this->pParent->pRChild == this)
    		{
    			this->pParent->pRChild = nullptr;
    		}
    	}
    	delete this;
    }
    
    void Node::PreorderTraversal()
    {
    	cout << this->index<<":" << this->data << endl;
    	if (this->pLChild)
    	{
    		this->pLChild->PreorderTraversal();
    	}
    	if (this->pRChild)
    	{
    		this->pRChild->PreorderTraversal();
    	}
    
    }
    
    void Node::InorderTraversal()
    {
    	if (this->pLChild)
    	{
    		this->pLChild->InorderTraversal();
    	}
    	cout << this->index << ":" << this->data << endl;
    	if (this->pRChild)
    	{
    		this->pRChild->InorderTraversal();
    	}
    }
    
    void Node::PostorderTraversal()
    {
    
    	if (this->pLChild)
    	{
    		this->pLChild->PostorderTraversal();
    	}
    	if (this->pRChild)
    	{
    		this->pRChild->PostorderTraversal();
    	}
    	cout << this->index << ":" << this->data << endl;
    }

Tree.h

#ifndef TREE_H_
    #define TREE_H_
    #include "Node.h"
    class Tree 
    {
    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();  //遍历
    private:
    	Node *m_pRoot;
    };
    
    #endif // !TREE_H_
    #pragma once

tree.cpp

#include "Tree.h"
    
    Tree::Tree()
    {
    	m_pRoot = new Node();
    }
    
    Tree::~Tree()
    {
    	DeleteNode(0, nullptr);
    }
    
    Node * Tree::SearchNode(int nodeIndex)
    {
    	return m_pRoot->SearchNode(nodeIndex);
    }
    
    bool Tree::AddNode(int nodeIndex, int direction, Node * pNode)
    {
    	Node *temp = m_pRoot->SearchNode(nodeIndex);
    	if (!temp) 
    	{
    		return false;
    	}
    	Node *node = new Node();
    	if (!node)
    	{
    		return false;
    	}
    	node->data = pNode->data;
    	node->index = pNode->index;
    	node->pParent = temp;  //指向父节点
    
    	if (direction == 0)
    	{
    		temp->pLChild = node;
    	}
    	else 
    	{
    		temp->pRChild = node;
    	}
    	return true;
    }
    
    bool Tree::DeleteNode(int nodeIndex, Node * pNode)
    {
    	Node *temp = m_pRoot->SearchNode(nodeIndex);
    	if (!temp)
    	{
    		return false;
    	}
    	if (pNode)
    	{
    		temp->data = pNode->data;
    	}
    	temp->DeleteNode();
    	return true;
    }
    
    void Tree::PreorderTraversal()
    {
    	m_pRoot->PreorderTraversal();
    }
    
    void Tree::InorderTraversal()
    {
    	m_pRoot->InorderTraversal();
    }
    
    void Tree::PostorderTraversal()
    {
    	m_pRoot->PostorderTraversal();
    }

demo.cpp

#include <iostream>
    #include <stdlib.h>
    #include "Tree.h"
    #include "Node.h"
    using namespace std;
    /*
    二叉树（链表表示）
    完成树的基本操作
    1.树的创建和销毁
    2.树中节点的搜索
    3.树中节点的添加与删除
    4.树中节点的遍历
    	Tree(int size,int *pRoot);
    	~Tree();
    	int *searchNode(int nodeIndex);  //根据索引寻找节点
    	bool AddNode(int nodeIndex,int direction, int *pNode);  //添加节点
    	bool DeleteNode(int nodeIndex, int *pNode); //删除节点
    	void PreorderTraversal();
    	void InorderTraversal();
    	void PostorderTraversal();  //遍历
     0   5 8  2697      
    
    前序遍历：0134256
    中序遍历：3140526
    后序遍历：3415620
    */
    int main() {
    	Tree *tree = new Tree();
    
    	Node *node1 = new Node();
    	node1->index = 1;
    	node1->data = 5;
    
    	Node *node2 = new Node();
    	node2->index = 2;
    	node2->data = 8;
    
    	Node *node3 = new Node();
    	node3->index = 3;
    	node3->data = 2;
    
    	Node *node4 = new Node();
    	node4->index = 4;
    	node4->data = 6;
    
    	Node *node5 = new Node();
    	node5->index = 5;
    	node5->data = 9;
    
    	Node *node6 = new Node();
    	node6->index = 6;
    	node6->data = 7;
    
    	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(6, NULL);
    	//tree->DeleteNode(5, NULL);
    	tree->DeleteNode(2, NULL);
    
    	tree->PostorderTraversal();
    	system("pause");
    	return 0;
    }