树的表示与术语
节点的度、树的度、叶子节点、父亲节点、兄弟节点、堂兄节点、祖先节点、子孙节点、节点层次、树的深度、路径、路径长度、分支...
二叉树
二叉树的性质
- 第n层的节点数\(2^n+1\)
- 前n曾节点数\(2^{n-1}\)
- n个节点的深度\([log_2n]+1\)
- \(n_0=n_2+1\)
二叉树的定义
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
二叉树的遍历
- 递归中序遍历
void InorderTraversal( BinTree BT ) {
if (BT) {
InorderTraversal(BT->Left);
printf(" %c", BT->Data);
InorderTraversal(BT->Right);
}
}
- 递归先序遍历
void PreorderTraversal( BinTree BT ) {
if (BT) {
printf(" %c", BT->Data);
PreorderTraversal(BT->Left);
PreorderTraversal(BT->Right);
}
}
- 递归后序遍历
void PostorderTraversal( BinTree BT ) {
if (BT) {
PostorderTraversal(BT->Left);
PostorderTraversal(BT->Right);
printf(" %c", BT->Data);
}
}
- 非递归中序遍历
void InorderTraversal(BinTree BT) {
Position T = BT;
Stack S = CreateStack();
while (T || !S.IsEmpty()) {
while (T) {
Push(S, T);
T = T->Next;
}
T = Pop(S, T);
Visit(T);
T = T->Right;
}
}
- 非递归先序遍历
void PreorderTraversal(BinTree BT) {
Position T = BT;
Stack S = CreateStack();
while (T || !S.IsEmpty()) {
while (T) {
Push(S, T);
Visit(T);
T = T->Next;
}
T = Pop(S, T);
T = T->Right;
}
}
- 层序遍历
void LevelorderTraversal( BinTree BT ) {
BinTree T;
BinTree Q[20];
int front = 0, rear = 0;
if (!BT) return ;
Q[rear ++] = BT;
while (front != rear) {
T = Q[front ++];
printf(" %c", T->Data);
if (T->Left) Q[rear ++] = T->Left;
if (T->Right) Q[rear ++] = T->Right;
}
}