Binary tree

Definition of binary tree

A binary tree is a finite set of nodes (recursively defined)
① This set is either empty;
② Or it is composed of a root node and two disjoint binary trees called left subtree and right subtree.

Five basic forms of binary tree

Difference between binary tree and quadratic tree

① Different degrees

A tree with degree 2 requires that each node can only have two subtrees at most, and at least one node has two subtrees. The requirement of binary tree is that the degree is no more than 2, and the node can have at most two forks, which can be 1 or 0.

② Different branches

A tree with degree 2 has two branches, but the branches are not divided into left and right; A binary tree also has two branches, but there are left and right branches. The order of the left and right subtrees cannot be reversed at will.

③ Different order

A tree with degree 2 is similar to a binary tree in form, but its subtrees are disordered and the binary tree is ordered. That is, in a general tree, if a node has only one child, there is no need to distinguish its left and right order, while in a binary tree, even a child can be divided into left and right.

Two special binary trees

Full binary tree

In a binary tree:
① If all branch nodes have branch nodes;
② And the leaf nodes are concentrated in the lowest layer of the binary tree.

Complete binary tree

The complete binary tree is actually obtained by deleting several nodes on the rightmost side of the leaf node layer of the corresponding full binary tree.

Properties of binary tree

Nature 1

There are at most 2^(i-1) nodes (I > = 1) on the i-th layer of the binary tree.

Property 2

A binary tree with depth K has at most 2^k-1 nodes (k > = 1).

Property 3

For any binary tree T, if the number of terminal nodes is n0 and the number of nodes with degree 2 is n2, then n0=n2+1.

Nature 4

The depth of a complete binary tree with n nodes is

Nature 5

Storage structure of binary tree

Sequential storage structure of binary tree

① For a complete binary tree, period sequential storage is very suitable.
② For general binary trees, especially those with more single branch nodes, it is very inappropriate, because only a few storage units may be used, especially for degenerate binary trees (that is, each node is single branch), the waste of space is even more amazing.
③ In the sequential storage structure, it is easy to find the parents and children of a node.

Chain storage structure of binary tree

Learn from the child chain storage structure of tree → chain storage structure of binary tree

typedef struct{
	TElemType data;
	struct BiTNode * lchild,* rchild;
}BiTNode,*BiTree;

Characteristics of binary chain storage structure

① In addition to pointers, binary chains save storage space. The storage space occupied has nothing to do with the tree shape, only with the number of nodes in the tree.
② In a binary chain, it is easy to find a child at a node, but it is not convenient to find his parents.
A tree is represented by a child brother chain storage structure → binary chain.

Traversal of binary tree

The concept of binary tree traversal

Traversal of binary tree refers to the process of accessing all nodes in the tree in a certain order, and each node is accessed only once.
Traversal is the most basic operation of binary tree and the basis of other operations of binary tree.
Composition of binary tree:

1. Preorder traversal process

The process of traversing NLR binary tree in sequence is as follows:
① Access the root node;
② Traversing the left subtree first;
③ First traverse the right subtree.

2. Middle order traversal process

The process of traversing LNR binary tree in middle order is as follows:
① Traversing the left subtree in middle order;
② Access the root node;
③ Traverse the right subtree in middle order.

3. Post order traversal process

The process of traversing LNR binary tree in middle order is as follows:
① Traversing the left subtree in sequence;
② Traversing the right subtree in order;
③ Access the root node.

Binary tree establishment and traversal complete code

#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0
typedef char TElemType;

typedef struct BiTNode {
	TElemType data;
	struct BiTNode* lchild;//Left child pointer
	struct BiTNode* rchild;//Right child pointer
}BiTNode,*BiTree;

//Binary tree generated by preorder traversal
void CreateBiTree(BiTree* T) {
	TElemType ch;
	scanf_s("%c", &ch,1);
	if (ch == '#')
		*T = NULL;
	else {
		*T = (BiTree)malloc(sizeof(BiTNode));
		if (!*T)
			cout<<"memory allocation failed!"<<endl;
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);//Left subtree
		CreateBiTree(&(*T)->rchild);//Right subtree
	}
}

//Preorder traversal binary tree
void PreOrderTraverse(BiTree T) {
	if (T == NULL)
		return;
	printf("%c ", T->data);
	PreOrderTraverse(T->lchild);
	PreOrderTraverse(T->rchild);
}

//Middle order traversal binary tree
void InOrderTraverse(BiTree T) {
	if (T == NULL)
		return;
	InOrderTraverse(T->lchild);
	printf("%c ", T->data);
	InOrderTraverse(T->rchild);
}

//Postorder traversal binary tree
void PostOrderTraverse(BiTree T) {
	if (T == NULL)
		return;
	PostOrderTraverse(T->lchild);
	PostOrderTraverse(T->rchild);
	printf("%c ", T->data);
}

//Find the depth of the tree
int BiTreeDeep(BiTree T) {
	if (T == NULL)
		return 0;
	else {
		int m = BiTreeDeep(T->lchild);
		int n = BiTreeDeep(T->rchild);
		if (m > n)
			return (m + 1);
		else
			return (n + 1);
	}
}

//Find the node number of the tree
int BiTreeNodeCount(BiTree T) {
	if (T == NULL)
		return 0;
	else
		return BiTreeNodeCount(T->lchild) + BiTreeNodeCount(T->rchild) + 1;
}

//Find the number of leaves of the tree
int BiTreeLeafCount(BiTree T) {
	if (!T)
		return 0;
	if (!T->lchild && !T->rchild)
		return 1;
	else
		return BiTreeLeafCount(T->lchild) + BiTreeLeafCount(T->rchild);
}

int main() {
	BiTree T = NULL;
	cout<<"Binary tree generated by preorder traversal:"<<endl;
	CreateBiTree(&T);
	cout<<"Preorder traversal :"<<endl;
	PreOrderTraverse(T);
	cout << endl;
	cout<<"Middle order traversal:"<<endl;
	InOrderTraverse(T);
	cout<<endl;
	cout<<"Postorder traversal:"<<endl;
	PostOrderTraverse(T);
	cout<<endl;
	int m = BiTreeDeep(T);
	cout<<"The depth of the tree is:"<<m<<endl;
	int n = BiTreeNodeCount(T);
	cout<<"The number of nodes in the tree is:"<<n<<endl;
	int k = BiTreeLeafCount(T);
	cout<<"The number of leaves of the tree is:"<<k<<endl;
	return 0;
}