Recursive traversal and properties of binary trees

## binary tree 1

typedef struct BiTNode{ ElemType data; Struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; // Binary tree node structureCopy the code

## Properties of binary trees

1. The leaf tree of a nonempty binary tree is equal to the node tree of degree 2 plus 1

The relationship between the node of degree 2 and the leaf node is revealed

2. There are at most k layers in the non-empty binary tree

3. The binary tree of height H has at most

It’s the sum of geometric sequences of property 2

---

4. The height of a complete binary tree with N nodes is

## sequential traversal of a binary tree

void PreOrder(BiTree T){
if(T! =NULL){printf(" %c ",T->data) PreOrder(T->lchild); PreOrder(T->rchild); // Recursively traverse the right subtree}}Copy the code

Backorder traversal is the reverse of middle order. ### sequence traversal

void LevelOrder(BiTree b){ InitQueue(Q); BiTree p; EnQueue(Q,b); // the root is queuedwhile(! IsEmpty(Q)){// Queue not empty loop DeQueue(Q, p) // queue head element out of queueprintf(" % c ", p - > data);if(p->lchild! =NULL) EnQueue(Q,p->lchild);if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
Copy the code

The process of traversing a binary tree in some order to make it a cued binary tree is called cueing pointing to precursor and successor, adding identifiers to identify whether it is pointing to children or to precursor and successor

ypedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree; 
Copy the code