The concept and representation of a tree

Preface

For a large amount of data , Linear access time of linked list is too slow , Do not use . This chapter will introduce a simple data structure ： Trees （tree）, The average running time of most operations is O（logN）. Trees are very useful abstract concepts in data structures , In this article, we will discuss the basic concepts and representation of trees , Lay the foundation for the subsequent binary tree and high-order search tree .

One 、 The concept of tree

The biggest difference between tree structure and linear structure is ： Linear structure is a one-to-one relationship , The tree is a one to many relationship .

The shape is shown in the above figure , It's just an ordinary tree ; And obviously we can see ：

1. A tree is n A collection of nodes , This set can be empty ;
2. If not empty , Then a tree is called root （root） The node of r and 0 One or more non empty subtrees T1、T2... form ;
3. Every root in these subtrees is The root node r One of the directed sides of （edge） Connected ;
4. For each sub tree, the node connected by the root is called root children （child）, And the root is the child's father （parent）;
5. Nodes without children are called leaf （leaf）.

Use a similar definition , We can call nodes with the same parent nodes as brothers （sibling）, For father's brother can be called Uncle （uncle）, Similarly, we can also define grandpa （grandparent） And grandson （grandchild）.

  At the same time, we also need to understand some important concepts ：

1. The number of subtrees a node has , It is called the degree of nodes （degree） As shown in the above figure A The degree is 3 And node B The degree is 0;
2. The degree of the largest node , Is the degree of the tree ;
3. The depth and height of the tree ： The depth is counted from top to bottom 、 The height is counted from bottom to top , They represent the layers of the tree , As shown in the figure above, the depth of the tree is 3.

Two 、 The representation of trees

1、 Basic storage structure

The representation of trees （ Storage structure ） diverse , Each method is used to solve problems in certain specific situations , There is no absolute method ！

① Parenting

As shown in the figure , Parental expression is Each node points to the parent node through storage to find the parent node ; Any algorithm cannot be separated from two ways of writing , One is sequential storage , One is chain storage , It is very simple for us to use sequential storage to realize this structure （ But chain storage can also , As long as the complexity of function implementation is about the same ）

  Code operation and linked list 、 Sequence table operation is the same , I won't go into details ：

#include<stdio.h>
#include<stdlib.h>
// Parenting 
typedef struct TreeNode
{
	int data;
	int parent;
}Node;

typedef struct TreeStruct
{
	Node* node[5];// Sequential structure 
	int size;// Current size 
	int capacity;// The maximum capacity 
}Tree;

// initialization 
void init(Tree* tree)
{
	tree->size = 0;
	tree->capacity = 5;
}

// Add root node 
void addRoot(Tree* tree, int key)
{
	Node* newnode = (Node*)malloc(sizeof(Node));// Create a new node 
	newnode->data = key;
	newnode->parent = -1;
	tree->node[tree->size] = newnode;
	tree->size++;
}

int findFatherNode(Tree* tree, int parentNode)
{
	for (int i = 0; i < tree->size; i++)
	{
		if (tree->node[i]->data == parentNode)
		{
			return i;
		}
		else
		{
			return -1;
		}
	}
}

// Add children 
void addChild(Tree* tree, int key, int parentNode)
{
	if (tree->size == tree->capacity)
	{
		// Prompt or expand the capacity when it is full 
		printf("FULL\n");
	}
	else
	{
		// First find out whether there is this parent node 
		int parentIndex = findFatherNode(tree, parentNode);
		if (parentIndex == -1)
		{
			printf("NOT FIND\n");
		}
		else
		{
			Node* newnode = (Node*)malloc(sizeof(Node));// Create a new node 
			newnode->data = key;
			newnode->parent = parentIndex;
			tree->node[tree->size] = newnode;
			tree->size++;
		}
	}
}

obvious , It is very easy for us to find the parent node through parental representation , But there is no way to find brothers and children . Now, if we want to know the relationship between a node and its father , At the same time, I also want to know the relationship with my brothers , How can we do it ？ At this time, we can add a pointer to the subscript of the nearest brother of the node ;

（ Or that sentence ： The design of storage structure , Focus on what to add , Very flexible ）

② Child representation

Because we don't know how many children a node may have , Obviously, a single chain structure or sequential structure is not convenient to realize , So we can use Array + Linked list In the form of （ This method is very common in later data structures ）

  It's also very easy to implement ：

#include<stdio.h>
#include<stdlib.h>
// Child representation 

typedef struct LinkList
{
	int data;// Data fields 
	struct LinkList* next;// Pointer to the next 
}ListNode;

typedef struct Child
{
	int data;// Data fields 
	struct LinkList* first;// Pointer to the next 
}Node;

Node* array[20];
int size;
int capacity;

// The process of creating the root node 
void init(int key)
{
	size = 0;
	capacity = 20;
	array[size] = (Node*)malloc(sizeof(Node));
	array[size]->data = key;
	array[size]->first = NULL;
	size++;
}

int findParent(int parent)
{
	for (int i = 0; i < size; i++)
	{
		if (array[i]->data == parent)
		{
			return i;
		}
	}
	return -1;
}

void creatTree(int parent, int key)
{
	// First find whether there is a parent node 
	int parentIndex = findParent(parent);
	if (parentIndex == -1)
	{
		printf("NOT FIND\n");
	}
	else
	{
		// First insert the new node into the array 
		if (size == capacity)
		{
			printf("ERR\n");
		}
		else
		{
			array[size] = (Node*)malloc(sizeof(Node));
			array[size]->data = key;
			array[size]->first = NULL;

			// Then create linked list nodes 
			ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
			newnode->data = parentIndex;
			newnode->next = array[parentIndex]->first;
			array[parentIndex]->first = newnode;
			size++;
		}
	}
}

③ Child brother notation

The idea of the child brother expression is actually the same as that of the father brother expression above ;

Its convenience is that it is very simple to traverse children , Just start from the first child and visit the child's brother according to the linked list . 

#include<stdio.h>
#include<stdlib.h>
// Child brother notation 
typedef struct ChildBro
{
	int key;// Data fields 
	struct ChildBro* child;// Child paper pointer 
	struct ChildBro* sibling;// Brother 
}Node;

void init(Node** root, int key)
{
	*root = (Node*)malloc(sizeof(Node));
	(*root)->key = key;
	(*root)->child = NULL;
	(*root)->sibling = NULL;
}

Node* findNode(Node* node, int key)
{
	static Node* temp = NULL;
	if (node->key == key)
	{
		temp = node;
	}
	if (node->sibling)
	{
		findNode(node->sibling, key);
	}
	if(node->child)
	{
		findNode(node->child, key);
	}
	return temp;
}

void insert(Node** root, int key, int parent)
{
	// Positioning nodes   recursive 
	Node* temp = findNode(*root, parent);
	if (temp == NULL)
	{
		// Without this node 
		printf(" Without this node \n");
	}
	else
	{
		if (temp->child == NULL)
		{
			Node* node = (Node*)malloc(sizeof(Node));
			node->key = key;
			node->child = NULL;
			node->sibling = NULL;
			temp->child = node;
		}
		else
		{
			temp = temp->child;
			Node* node = (Node*)malloc(sizeof(Node));
			node->key = key;
			node->child = NULL;
			node->sibling = temp->sibling;
			temp->sibling = node;
		}
	}
}

int main()
{
	Node* root = NULL;
	init(&root, 0);
	insert(&root, 1, 0);
	insert(&root, 2, 0);
	insert(&root, 3, 2);
	insert(&root, 4, 0);
	printf("%d %d %d %d %d", root->key, root->child->key, root->child->sibling->sibling->key, root->child->sibling->sibling->child->key, root->child->sibling->key);
	return 0;
}

2、 recursive

In addition, we also need to learn recursion ：

Recursion is to call your own function , Usually, recursion can be used to split big problems into repeated small problems ;

It is worth noting that ： We must strictly define the boundary condition of recursion, that is Recursive function exit , Otherwise the code will run to death ;

Here we implement one 1+2+3+4+5 Recursive computation of ：

int add(int n)
{
    if(n == 1)
        return n;
    else
        return n + add(n - 1);
}

The specific implementation process is as follows ：

The main reason why recursion takes up a lot of memory is when running a function and entering the next function , This running function doesn't end , Just hang up as a waiting state , In order to optimize the problem that recursion takes up a large amount of memory , There are tail recursion optimization recursive operations

int add(int n,int sum)
{
    if(n == 1) 
        return sum;
    else 
        add(n - 1,sum + n);
}

Tail recursion is a special form of recursion , Due to the call at the end , There is no need to wait （ return ） The process of , So when we go to the next function , The running function will end , Then there will be no suspended functions occupying memory .

Be careful ！ The optimization of tail recursion depends on the compiler , Not all compilers can optimize tail recursion , Some old compilers cannot optimize tail recursion .