Day5: three pointers describe a tree

One 、 The basic concept of tree

        1. Tree structure

Three pointers describe a tree 、 Unordered binary tree 、 Ordered binary tree 、 Binary search tree 、 Perfect binary tree 、 Pile up 、 Balanced binary trees 、23 Trees  、B B+、 Red and black binary tree

        2. The basic concept of tree .

     Trees   subtree   node  

     Parent node Child node Grandfather node Uncle node Brother node

     root ： The first node of the tree          The root
     leaf ： No children's nodes          Leaf
     Branches ： Not a root nor a leaf      Branches

     Binary tree Trident tree quadtree Octree
     fork ： Maximum number of branches allowed
         Before releasing the third tire     Binary tree

     Height The layer number ： Generations ( Shortest path +1)

 

Linked list ：
    next  prev 
Binary tree ：
    left  right
3、 ... and ：
    p1 p2 p3
Four ：
    p1 p2 p3 p4

Genealogy ：N Fork tree

Two 、 Design : Every node 3 Pointers realize disorder N Add, delete, modify and check the fork tree

3 A pointer to the , A pointer to the parent node , A pointer points to the sibling node , A pointer points to the first child node . Where the sibling node pointer Is the key to this design , It clearly describes the same level relationship .

  As shown in the figure above , have 3 A pointer node Then the description is clear All relations of an arbitrary fork tree .

#include <iostream>
using namespace std;
// Three pointers describe a N Check tree 


template<class T>
class MyTree
{
	// The node type of the tree 
	struct Node
	{
		T			data;		
		Node*		pParent;
		Node*		pBrother;
		Node*		pChild;
	};

private:
	Node*		pRoot;// Members of the tree    Pointer to the root node 

public:
	MyTree();
	~MyTree();

	// Create a node and return 
	Node* createNode(const T& data);
	/*
		 Insert node into tree 
		insertData： Data of the node to be inserted 
		findData：   The node to be inserted wants to be  findData Children or brothers of nodes 
		isBrother： true  Become brothers  false  Be a child 
	*/
	bool insertNode(const T& findData, const T& insertData, bool isBrother = true);

	// Find the data from the tree as findData The node of   Found the return node address , Otherwise return to NULL
	Node* findNode(const T& findData);

	// The first data deleted from the tree is delData The node of 
	bool deleteNode(const T& delData);

};
template<class T>
MyTree<T>::MyTree()
{pRoot = NULL;}
template<class T>
MyTree<T>::~MyTree()
{}

3、 ... and 、 Specific code implementation ：

        1.createNode（memset initialization ）

typename MyTree<T>::Node* MyTree<T>::createNode(const T& data)
{
	Node* pNew = new Node;
	if (NULL == pNew) return NULL;// Guard against stupidity 
	memset(pNew, 0, sizeof(Node));
	pNew->data = data;
	return pNew;
}
/*

         2.findNode

Traversal ideas ： First Set two arrows , An arrow is used to traverse down , An arrow is used to traverse to the right , First traverse one layer to the right , Then traverse down a .

template<class T>
// Find the data from the tree as findData The node of   Found the return node address , Otherwise return to NULL
typename MyTree<T>::Node* MyTree<T>::findNode(const T& findData)
{
	if (NULL == pRoot) return NULL;

	Node* pCurrent = pRoot;// Current layer 
	Node* pTemp = NULL;// The current node of the current layer 

	while (pCurrent)
	{// Switch between layers 
		pTemp = pCurrent;//
		while (pTemp)
		{// The current floor is to the right 
			if (findData == pTemp->data)return pTemp;
			pTemp = pTemp->pBrother;
		}

		pCurrent = pCurrent->pChild;// Switch between layers 
	}

	return NULL;
}

        3.insertNode

Make your own rules ：( Only the eldest son here child)

   /*Args: explain

         Insert node into tree
        insertData： Data of the node to be inserted
        findData：   The node to be inserted wants to be findData Children or brothers of nodes
        isBrother： true Become brothers false Be a child */

         If the tree is empty ： Become the root node directly
         If the tree is not empty ：
            - Become brothers (is_brother)：
                 -- eureka ：
                    --- There were brothers ： Become the youngest brother
                    --- There was no brother ： Become brothers

                -- Did not find ： Become the smallest brother of the root node
            - Be a child (is_child)：
                -- eureka ：
                    --- There were children ： Be the youngest child
                    --- There were no children ： Be a child
                -- Did not find ： Become the youngest child of the root node

template<class T>
bool MyTree<T>::insertNode(const T& findData, const T& insertData, bool isBrother)
{
	Node* pNew = createNode(insertData);
	if (NULL == pNew) return false;
	if (NULL == pRoot){// If the tree is empty ：  Become the root node directly 
		pRoot = pNew;
		return true;
	}
	Node* pInsert = findNode(findData);
	Node* pTemp = NULL;
	if (isBrother)
	{// Become brothers ：
		if (pInsert)
		{// eureka ：
			cout << " eureka " << endl;
			// find pInsert My youngest brother  
			pTemp = pInsert;
			while (pTemp->pBrother)
			{//pTemp Point to the last brother of the root node 
				pTemp = pTemp->pBrother;
			}
			// Insert 
			pTemp->pBrother = pNew;
			pNew->pParent = pTemp->pParent;
		}
		else
		{// Did not find // Become the smallest brother of the root node 
			pTemp = pRoot;// Give Way pTemp Point to the root node 
			while (pTemp->pBrother)
			{//pTemp Point to the last brother of the root node 
				pTemp = pTemp->pBrother;
			}
			// New node to pTemp Of pBrother assignment 
			pTemp->pBrother = pNew;
		}
	}
	else
	{// Be a child ：
		if (pInsert)
		{// eureka ：
			cout << " eureka " << endl;
			// find pInsert My youngest child 
			pTemp = pInsert;
			while (pTemp->pChild)
			{
				pTemp = pTemp->pChild;
			}
			// Insert 
			pTemp->pChild = pNew;
			pNew->pParent = pTemp;
		}
		else
		{// Did not find 
			// Become the youngest child of the root node 
			pTemp = pRoot;// Give Way pTemp Point to the root node 
			while (pTemp->pChild)
			{//pTemp Point to the last child of the root node 
				pTemp = pTemp->pChild;
			}
			// New node to pTemp Of pChild assignment 
			pTemp->pChild = pNew;
		}
	}
	return true;
}

        4.deleteNode

The functionality ： Delete a node in the tree , Delete successful , return true, Otherwise return to false

Realize the idea ( The rules )： First findNode Find node , Can't find false

        If the node is pRoot：

                if pRoot There are brothers ：

                        ① Brothers become pRoot+② The old eldest son pchild Adopt for your brother +③ Cycle to reset the eldest son and his                                   Brother's pParent Node to new parent node ( to update pParent)

                if pRoot No brothers ：

                        ① The eldest son pChild Become the root node +② Cycle reset the eldest son and his brother pParent The pointer to                                         （ to update pParent）

        If the node is not pRoot( Delete branches or leaf )：

                if delNode Not the eldest son ：

                        obtain delNode Parent node -> Get the eldest son node and cycle through this layer to delNode The previous node of                            -> Delete delete that will do .

                if delNode It's the eldest son ：

                        if delNode And brothers ：

                                ① Let his first brother become the eldest son (pChild)+②delNode My son is adopted by my brother +

                                ③ After adoption , Reset sons pParent The pointer .

                        if delNode No brothers ：

                                ①delNode All children of are given to the parent node pParent Adopt +② Cycle reset the child's pParent                                    node

 

template<class T>
// The first data deleted from the tree is delData The node of 
bool MyTree<T>::deleteNode(const T& delData)
{
	Node* pDel = findNode(delData);
	if (NULL == pDel)
	{
		return false;
	}
	Node* pTemp = NULL;
	if (pDel == pRoot)
	{// The node to be deleted is the root node 
		if (pDel->pBrother)
		{// There are brothers 
			// Brothers become roots 
			pRoot = pDel->pBrother;
			//pDel The child of becomes the child of the new root node 
			pTemp = pDel->pChild;

			pRoot->pChild = pTemp;// Up to down 
			while (pTemp)
			{// Point down and up 
				pTemp->pParent = pRoot;
				pTemp = pTemp->pBrother;
			}
		}
		else
		{// No brothers 
			pRoot = pDel->pChild;
			pTemp = pDel->pChild;
			while (pTemp)
			{// Point down and up 
				pTemp->pParent = NULL;//parent Set as NULL
				pTemp = pTemp->pBrother;
			}
		}
		delete pDel;
		return true; 
	}

	// Delete branches or leaves 
	Node* pFather = pDel->pParent;
	if (pDel != pFather->pChild)
	{// The node to be deleted is not the child of its parent node 
		// find pDel Previous node of 
		pTemp = pFather->pChild;
		while (pTemp->pBrother != pDel)// Give Way pTemp Point to pDel Previous node of 
			pTemp = pTemp->pBrother;

		pTemp->pBrother = pDel->pBrother;
		delete pDel;
		return true;
	}

	// The node to be deleted is the child of its parent node 
	if (pDel->pBrother)
	{// There are brothers 
		//pDel The first brother of becomes the child of its parent node 
		pFather->pChild = pDel->pBrother;
		pDel->pBrother->pChild = pDel->pChild;
		//pDel Our children become  pDel->pBrother  The children of 
		pTemp = pDel->pChild;
		while (pTemp)
		{// Give all your children to your brothers for adoption 
			pTemp->pParent = pDel->pBrother;
			pTemp = pTemp->pBrother;
		}
	}
	else
	{// No brothers 
		//pDel The child of becomes the child of its parent node ( Adopted by father )
		pFather->pChild = pDel->pChild;
		//pDel Our children become  pFather  The children of 
		pTemp = pDel->pChild;
		while (pTemp)
		{
			pTemp->pParent = pFather;
			pTemp = pTemp->pBrother;
		}
	}
	delete pDel;
	return true;
}