Tree and binary tree (learning notes)

Trees and binary trees

Trees are n A finite set of nodes .
root —— Root node （ There is no precursor ）
leaf —— Terminal node （ There is no successor ）
The forest —— namely m A collection of disjoint trees
Ordered trees , Disordered trees
The degree of node —— Number of subtrees attached to nodes
The degree of a tree —— The maximum of all node degrees
Can prove that , All trees can be transformed into a unique corresponding binary tree
Basic characteristics of binary tree ：
1. The degree of node ≤2
2. Ordered trees
Properties of binary trees ：
1. On the second of the binary tree i There is at most 2^(i-1) Nodes .
2. Depth is k At most, the binary tree of 2^k-1 Nodes .
Full binary tree , Perfect binary tree
A full binary tree is a special case of a complete binary tree .
3. have n The depth of a complete binary tree of nodes must be [log2(n)]+1.
Binary list ：

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

Traversing the binary tree ：
The first sequence traversal —— First root, then left, then right
In the sequence traversal —— First left, then root, then right
After the sequence traversal —— First left, then right, then root
Preorder traversal implementation ：

Status PreOrderTraverse(BiTree T){
    
	if(T==NULL) return OK;
	else{
    
		cout<<T->data;
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}

Middle order traversal implementation ：

Status PreOrderTraverse(BiTree T){
    
	if(T==NULL) return OK;
	else{
    
		PreOrderTraverse(T->lchild);
		cout<<T->data;
		PreOrderTraverse(T->rchild);
	}
}

Post order traversal implementation ：

Status PreOrderTraverse(BiTree T){
    
	if(T==NULL) return OK;
	else{
    
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
		cout<<T->data;
	}
}

Analysis of traversal algorithm ：
Time efficiency ：O(n)
Space efficiency ：O(n)
The establishment of binary tree ：

void CreateBiTree(BiTree &T){
    
	cin>>ch;
	if(ch=='#') T=NULL;
	else{
    
		T=new BiNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

Calculate the total number of binary tree nodes ：

int NodeCount(BiTree T){
    
	if(T=NULL) return 0;
	else return NodeCount(T->lchild)+NodeCount(T->rchild);
}