Elementary notes of binary tree

Catalog

One . The concept and structure of tree

Two . Concept and structure of binary tree

1. Basic concepts and properties

2. Construction and application of heap

3. The chain structure

---

One . The concept and structure of tree

Degree of node ： The number of subtrees a node contains is called the degree of the node ; Pictured above ：A For the 6
Leaf node or terminal node ： Degree is 0 A node of is called a leaf node ; Pictured above ：B、C、H、I... Equal nodes are leaf nodes
Non terminal node or branch node ： The degree is not for 0 The node of ; Pictured above ：D、E、F、G... Such nodes are branch nodes
Parent node or parent node ： If a node has child nodes , This node is called the parent of its child ; Pictured above ：A yes B Parent node
Child node or child node ： The root node of the subtree that a node contains is called the child node of the node ; Pictured above ：B yes A The child node of
Brother node ： Nodes with the same parent are called siblings ; Pictured above ：B、C It's a brother node
The degree of a tree ： In a tree , The degree of the largest node is called the degree of the tree ; Pictured above ： The degree of the tree is 6
Hierarchy of nodes ： Starting from the root , The root for the first 1 layer , The child node of the root is the 2 layer , And so on ;
The height or depth of a tree ： The maximum level of nodes in the tree ; Pictured above ： The height of the tree is 4
Cousin node ： The nodes of both parents on the same layer are cousins to each other ; Pictured above ：H、I Be brothers to each other
The ancestor of node ： From the root to all nodes on the branch through which the node passes ; Pictured above ：A Is the ancestor of all nodes
descendants ： Any node in a subtree with a node as its root is called the descendant of the node . Pictured above ： All nodes are A The descendants of
The forest ： from m（m>0） A collection of trees that do not intersect each other is called a forest ;

The representation of trees ： Child brother notation

typedef int DataType;
struct Node
{
struct Node* _firstChild1; //  The first child node 
struct Node* _pNextBrother; //  Point to its next sibling node 
DataType _data; //  Data fields in nodes 
};

---

Two . Concept and structure of binary tree

1. Concept （ Here's the picture ）

（1）. The degree of nonexistence of binary trees is greater than 2 The node of
（2）. The subtree of a binary tree has left and right branches , The order cannot be reversed , So a binary tree is an ordered tree

notes ： Special binary tree ： 

（1）. Full binary tree ： A binary tree , If the number of nodes in each layer reaches the maximum , Then this binary tree is full of binary trees .
（2). Perfect binary tree ： A complete binary tree is an efficient data structure , A complete binary tree is derived from a full binary tree . For a depth of K
Of , Yes n A binary tree of nodes , If and only if each of its nodes has a depth of K From the full binary tree of 1 to n The nodes are paired one by one
It should be called a complete binary tree . It should be noted that a full binary tree is a special kind of complete binary tree .

nature

1. If the specified number of layers of the root node is 1, Then the second of a non empty binary tree i There is a maximum of Nodes .
2. If the specified number of layers of the root node is 1, Then the depth is h The number of nodes in a binary tree is the largest .
3. Any binary tree , If the degree is 0 The number of leaf nodes is , Degree is 2 The number of branch nodes is , Then there are ＝ ＋1
4. If the specified number of layers of the root node is 1, have n The depth of a full binary tree of nodes ,h= . (ps： yes log With 2
Bottom ,n+1 For logarithm )

---

2. The sequential structure of binary trees （ Pile up ）

Heap down adjustment algorithm

int array[] = {27,15,19,18,28,34,65,49,25,37};

 

  Team building method （ Adjust the way down to build a team ） Time complexity o（N）;

Pile insertion ： Adjust the algorithm up

Heap delete ： Adjust the algorithm down

---

a key （ Heap sort ）

1. First build a heap on the original array

2. In ascending order , Build small piles in descending order

3. Swap the top of the heap elements with the end of the heap , Then adjust down

The code implementation is as follows ：

#include<stdio.h>

void swap(int*a, int*b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void AdjustDown(int*arr, int sz, int parent)
{
	int child = parent * 2 + 1;
	while (child < sz)
	{
		if (child+1<sz&&arr[child + 1]>arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}

}


void heap_sort(int*arr, int sz)
{
	// Heap the original array 
	// Ascending ： Build a pile 
	int i = 0;
	for (i = (sz - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, sz, i);
	}

	// Ascending the heap 
	int end = sz - 1;// Heap tail subscript 
	while (end > 0)
	{
		// Exchange reactor top and tail 
		swap(&arr[0], &arr[end]);
		// Downward adjustments , Adjust the next largest tree to the top of the heap 
		AdjustDown(arr, end, 0);
		end--;
	}
}

int main()
{
	int arr[] = { 2,3,1,4,0,6,5,7,8,9 };
	heap_sort(arr, sizeof(arr) / sizeof(int));
	int sz = sizeof(arr) / sizeof(int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

 

---

TOP-K problem

That is, before data combination K The largest element or the smallest element , Generally, the amount of data is relatively large .

1. Use the first... In the data set K Elements to build the heap
front k The biggest element , Then build a small pile
front k The smallest element , Then build a lot of
2. With the rest of N-K The elements are compared with the top elements in turn , If not, replace the heap top element
Bit employment course
Will remain N-K After the elements are compared with the top elements in turn , The rest of the heap K The first element is the front K The smallest or largest element .

The code is as follows ：

int* heap_topk(int*arr, int sz, int k)
{

	// For the first K Elements build teams 
	
	// Open up a heap space 
	int*heap_space = (int*)malloc(sizeof(int)*k);

	// Put the first four elements of the array into the heap 
	int i = 0;
	for (i = 0; i < k; i++)
	{
		heap_space[i] = arr[i];
	}

	// Build a small pile 
	i = 0;
	for (i = (k - 2) / 2; i >= 0; i--)
	{
		AdjustDown(heap_space, k, i);
	}

	// Compare the top element of the heap with other elements of the array 
	int j = 0;
	for (j = k; j < sz;j++)
	{
		if (heap_space[0] < arr[j])
		{
			heap_space[0] = arr[j];
			AdjustDown(heap_space, k, 0);
		}
	}
	return heap_space;
}

---

3. Implementation of chain structure  

// Create nodes 

TreeNode* BuyNewnode(SLTDataType x)
{
	TreeNode*newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);
	newnode->data = x;
	newnode->left =NULL;
	newnode->right = NULL;
}

// Building a binary tree 

TreeNode*Creat_Binary()
{
	TreeNode*node1 = BuyNewnode(1);
	TreeNode*node2 = BuyNewnode(2);
	TreeNode*node3 = BuyNewnode(3);
	TreeNode*node4 = BuyNewnode(4);
	TreeNode*node5 = BuyNewnode(5);
	TreeNode*node6 = BuyNewnode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	return node1;
}

//  Binary tree preorder traversal 
void PreOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

//  Order traversal in binary tree 
void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}


//  Number of nodes in binary tree 
int BinaryTreeSize(TreeNode* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}


//  Number of leaf nodes of binary tree 
int BinaryTreeLeafSize(TreeNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL&&root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
	
}


//  The second fork is the tree k The number of layer nodes 
int BinaryTreeLevelKSize(TreeNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}



//  The binary tree lookup value is x The node of 
TreeNode* BinaryTreeFind(TreeNode* root, SLTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	TreeNode*leftret = BinaryTreeFind(root->left, x);
	if (leftret)
		return leftret;
	TreeNode*rightret = BinaryTreeFind(root->right, x);
	if (rightret)
		return rightret;

	return NULL;
}


// The height of the binary tree 
int BinaryTreeHight(TreeNode*root)
{
	if (root == NULL)
	{
		return 0;
	}

	int lefthigh = BinaryTreeHight(root->left);
	int righthigh = BinaryTreeHight(root->right);

	return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;
}

void DestBinaryTree(TreeNode*root)
{
	if (root == NULL)
	{
		return;
	}

	DestBinaryTree(root->left);
	DestBinaryTree(root->right);
	free(root);






}