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; }