Implementation and traversal of binary tree and binary tree sorting tree

   Before learning binary tree, you must learn 【 Leading knowledge 】 The concept and representation of tree

Catalog

1、 Binary tree

2、 Traversal of binary tree

3、 Binary sort 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 storage structure of binary tree 、 Traversal of binary tree and implementation of binary sort tree , Lay the foundation for the subsequent balanced tree and high-order search tree .

1、 Binary tree

Binary tree （binary tree） It's a tree. Each node can only have a tree with two children at most （ Degree is 2）, When a tree has only left or right children The worst case is called skew tree ;

When the degree of a tree is only 0 perhaps 2, We call this kind of tree Full binary tree ; When the nodes of a tree are strictly from top to bottom 、 From left to right , We call this kind of tree Perfect binary tree , According to the definition , Full binary tree is a special case of complete binary tree ; If we use NULL Or other impossible keywords to fill all empty nodes , Then this kind of tree is called extended binary tree .

At the same time, some properties of binary tree are often tested in the exam , Here's a summary ：

1. In the  i  There are at most  2^(i-1)  Nodes ;
2. Depth is k The binary tree of has 2^k-1 Nodes ; 
3. Suppose the degree is 0、1、2 The nodes of are n0、n1、n2, Because the number of nodes in a tree is T, therefore T = n0 + n2 + n2, And branches （ Connections between nodes ） The number is T - 1, therefore T - 1 = 2 * n2 + n1, From these two relations, we can get ：n0=n2+1;
4. have n The depth of a complete binary tree of nodes is （ log2n）+1 Rounding down ;
5. By nature 4 Available ： have n The nodes of a complete binary tree of nodes are numbered hierarchically （ From top to bottom 、 From left to right ）, If i = 1 Root node , Then for any node, its parent node number is i / 2（i > 1） Rounding down , If so 2 * i > n that node i There must be no left child （ There are no right children ）,2 * i + 1 > n  No right child ;

For the implementation of binary tree , We can also consider using sequential structure or chain structure . Use the order structure , Because the search is fast, it can be used in the game , According to the above properties 5, Calculate the subscript relationship between the parent node and its children ;

And because a binary tree has at most two children , So when we use the chain structure, we can directly point to them with a pointer .

/* Binary tree node declaration */
typedef struct TreeNode
{
	int data;
	struct TreeNode* left, *right;
}Node;

As for the implementation of binary tree, it is very simple , Plug in wherever you have time ;

Node* root = NULL;

void init(int key)
{
	root = (Node*)malloc(sizeof(Node));
	root->data = key;
	root->left = NULL;
	root->right = NULL;
}

Node* findNode(Node* node ,int parent)
{
	static Node* temp = NULL;
	if (node->data == parent)
	{
		temp = node;
	}
	if(node->left)
	{
		findNode(node->left, parent);
	}
	if (node->right)
	{
		findNode(node->right, parent);
	}
	return temp;
}

void createNode(int key, int parent)
{
	Node* temp = findNode(root, parent);
	if (temp == NULL)
	{
		printf("NOT FIND\n");
		return;
	}
	else
	{
		if (temp->left == NULL)
		{
			Node* newnode = (Node*)malloc(sizeof(Node));
			newnode->data = key;
			newnode->left = NULL;
			newnode->right = NULL;
			temp->left = newnode;
		}
		else if (temp->right == NULL)
		{
			Node* newnode = (Node*)malloc(sizeof(Node));
			newnode->data = key;
			newnode->left = NULL;
			newnode->right = NULL;
			temp->right = newnode;
		}
		else
		{
			// There are both left and right subtrees 
			printf("FULL\n");
			return;
		}
	}
}

2、 Traversal of binary tree

Next, we focus on the traversal of binary trees .

The traversal of binary tree is divided into ： The former sequence traversal 、 In the sequence traversal 、 Post sequence traversal and sequence traversal ;

• The former sequence traversal ： First access the root node, then the left subtree, and then the right subtree ;

In the binary tree as shown above , The order of preorder traversal is ：1 ->2 -> 4 -> 5 -> 3 -> 6 ;

The specific steps are shown in the figure below , Order of access （ From first to last ）   green  、  red  、  blue  

• In the sequence traversal ： Visit the left subtree first , Access the root node again , Visit the right subtree ;

In the binary tree as shown above , The order of middle order traversal is ：4 ->2 -> 5 -> 1 -> 6 -> 3

 

• After the sequence traversal ： Visit the left subtree first , Visit the right subtree , Access the root node again ;

In the binary tree as shown above , The order of postorder traversal is ：4 ->5 -> 2 -> 6 -> 3 -> 1

Through the above case , We can get an important property ： The first of the preorder traversals must be the root , The last one of the postorder traversals must be the root , Then we can deduce the abstract model of the tree through the pre order and middle order or the post order and middle order ;

And use code to realize the pre -, middle -, and post sequence traversal , Recursive implementation is the simplest ：

// Before the order 
void prev_order(Node* node)
{
	if (node == NULL)
	{
		return;
	}
	printf("%d", node->data);
	prev_order(node->left);
	prev_order(node->right);
}

// Middle preface 
void in_order(Node* node)
{
	if (node == NULL)
	{
		return;
	}
	in_order(node->left);
	printf("%d", node->data);
	in_order(node->right);
}

// In the following order 
void past_order(Node* node)
{
	if (node == NULL)
	{
		return;
	}
	past_order(node->left);
	past_order(node->right);
	printf("%d", node->data);
}

As for sequence traversal , It can intuitively output each layer of the tree , Of course, if you want to do this, you can't use simple recursion , Here we use queues to implement ：

  First step ： Let's put the root node into the team first ; The second step ： Determines if the queue is empty , If it's not empty , Just get out of the team , Join its children in the team , So circular , Until the queue is empty and jumps out ;

  Code, I'll steal a little lazy here , use C++ Medium STL Implemented queue , If you can't, just write the queue normally , The idea is the same ;

// sequence 
void level_order(Node* node)
{
    // Create a queue 
	std::queue<int> q;
	if (node != NULL)
	{
		q.push(node->data);
	}
	while(!q.empty())
	{
		int temp = q.front();
		printf("%d ", temp);
		Node* tempNode = findNode(root, temp);
		q.pop();
		if (tempNode->left)
		{
			q.push(tempNode->left->data);
		}
		if (tempNode->right)
		{
			q.push(tempNode->right->data);
		}
	}
}

3、 Binary sort tree

Binary sort tree is also called binary search tree ： If a binary tree's left subtree is not empty , Then all values of the left subtree are less than the root node ; If the right subtree is not empty , Then the value of all right subtrees is greater than the root node , This is the binary sort tree （binary search tree）.

As shown above, it is a binary sort tree . Binary sort tree is created to make our search more convenient （ Two points search ）, Due to the particularity of binary sort tree , So that the value on the left is always smaller than the root node , The value on the right is always greater than the root node , We can find that when we traverse this tree in middle order , The result is an ordered sequence ：1 3 4 6 7 8 10 13 14;

Its node structure is the same as that of a general binary tree ;

typedef struct TreeNode
{
	int data;
	struct TreeNode* left, * right;
}Node;

And building a binary sort tree is also very simple , Insert according to its nature ;

// There is no repetition by default key The situation of 
void insert(Node** root, int key)
{
	Node* prev = NULL;// The parent node used to point to the correct insertion location 
	Node* temp = *root;
	while (temp != NULL)
	{
		// follow root The last position of 
		prev = temp;
		// If the inserted value is less than this node   Look to the left 
		if (key < temp->data)
		{
			temp = temp->left;
		}
		// If the inserted value is greater than this node   Look to the right 
		else if (key > temp->data)
		{
			temp = temp->right;
		}
	}
	// Found the location to insert 
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (newnode == NULL)
	{
		printf("ERR\n");
		return;
	}
	else
	{
		newnode->data = key;
		newnode->left = NULL;
		newnode->right = NULL;
		if (*root == NULL)// If the root node is not initialized 
		{
			*root = newnode;
		}
		else if (key < prev->data)
		{
			prev->left = newnode;
		}
		else if (key > prev->data)
		{
			prev->right = newnode;
		}
	}
}

The key of binary sort tree is Delete operation . For the deletion of binary sort tree , We generally fall into three situations ：

• Case one ： Delete the leaf node , At this time, just delete it directly , Because deleting it will not affect the whole tree ;
• The second case ： The deleted node has a child （ No matter left or right ）, At this time, you need to move its children to the location of the deleted node ;
• The third case ： The deleted node has two children , At this time, you need to find the direct predecessor or direct successor of the node to replace and delete the node ;

The first two situations are easy to understand , Let's talk about the third situation in detail . The ordered sequence in the above article 1 3 4 6 7 8 10 13 14 For example , Suppose we want to delete a value of 8 The node of , In order not to affect the whole ordered sequence , The result after deletion should be 1 3 4 6 7 10 13 14, That is, we need to find the value is 7 Or the value is 10 Node replacement of 8 node , Then according to situation one 、 2. Delete the original 7 perhaps 10,. This 7 Node is the direct precursor of deleting node , Homomorphic node 10 It is the direct successor of deleting nodes ;

It's also easy to find this direct precursor or direct successor ： As we can see from the picture below , The direct precursor node must be the maximum value in the left subtree of the deleted node , The direct successor node must be the minimum value in the right subtree of the deleted node ;

Take the direct precursor node 7 For example , If the left subtree of the node to be deleted exists , We just need to visit the left subtree first , Then keep visiting its right subtree .

/* The real delete operation */
void del(Node* node, Node* prev)
{
	Node* temp = NULL;
	// If there are only left subtrees or only right subtrees   Delete the node to be deleted   And replace the child 
	if (node->left == NULL && node->right != NULL)
	{
		temp = node;
		temp = temp->right;
		node->data = temp->data;
		node->left = temp->left;
		node->right = temp->right;
		free(temp);
	}
	else if (node->right == NULL && node->left != NULL)
	{
		temp = node;
		temp = temp->left;
		node->data = temp->data;
		node->left = temp->left;
		node->right = temp->right;
		free(temp);
	}
	// Leaf nodes 
	else if (node->right == NULL && node->left == NULL)
	{
		// The situation of the left leaf 
		if (node->data < prev->data)
		{
			prev->left = NULL;
		}
		else
		{
			prev->right = NULL;
		}
		free(node);
	}
	// When the left and right subtrees are not empty 
	else
	{
		temp = node;
		Node* s = node;// Pointer to the maximum value of the left subtree 
		// Find the maximum value of the left subtree 
		s = s->left;
		while (s->right != NULL)
		{
			temp = s;// there temp Point to s Parent node 
			s = s->right;
		}
		// Replace data 
		node->data = s->data;
		// Also delete s node   There are two more cases 
		// But in either case, at this time s Either no children or only left children 
		if (temp!= node)
		{
			// explain s Many steps down   This is the time s It must be temp To the right of 
			temp->right = s->left;
		}
		else
		{
			// This is the time s It must be temp Left side 
			temp->left = s->left;
		}
	}
}

/* Encapsulate delete operation */
void deleteNode(Node* root, int key)
{
	if(root == NULL)
	{
		return;
	}
	else
	{
		static Node* prev = NULL;//prev Delete the parent node of the node 
		// Recursively find the point to delete 
		if (key < root->data)
		{
			prev = root;
			deleteNode(root->left, key);
		}
		else if (key > root->data)
		{
			prev = root;
			deleteNode(root->right, key);
		}
		else
		{
			// Delete 
			del(root, prev);
		}
	}
}

Traverse the test results in middle order  

The latter

Normally , The complexity of a binary sort tree depends on the height of the tree h, But if the value I insert is 12345... Well ？ Does it become what we call complexity O（N） The worst-case scenario —— Oblique tree , To ensure search efficiency , The first self balancing tree in human history —— Binary balanced tree was born ！ Next time, we will explain in detail the addition, deletion, search and modification of binary balanced tree .