二叉树
1.每个节点度最多2
2.每个节点一个父亲
3.度为0的节点比度为2的节点多一个
证明：
二叉树的节点比连线多1，度为1的节点有1条边，度为2的节点有2条边，度为0的节点有0条边
N0+N1+N2=N1+2N2+1
N0=N2+1
二叉树遍历
image.png
前序（根左右）124536
中序（左根右）425136
后序（左右根）452631
中+前/后可以还原一棵树
image.png
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Node {
int key;
struct Node *lchild, *rchild;
};
struct Node *getNewNode(int key) {
struct Node *p = (struct Node *) malloc(sizeof(struct Node));
p->key = key;
p->lchild = p->rchild = NULL;
return p;
}
struct Node *randomInsert(struct Node *root, int key) {
if (root == NULL) return getNewNode(key);
if (rand() % 2) {
root->lchild = randomInsert(root->lchild, key);
} else {
root->rchild = randomInsert(root->rchild, key);
}
return root;
}
void pre_order(struct Node *node) {
if (node == NULL) return;
printf("%d ", node->key);
pre_order(node->lchild);
pre_order(node->rchild);
}
void in_order(struct Node *node) {
if (node == NULL) return;
in_order(node->lchild);
printf("%d ", node->key);
in_order(node->rchild);
}
int main(int argc, char *argv[]) {
srand(time(0));
if (argc != 2) return -1;
struct Node *root = NULL;
for (int i = 1; i <= atoi(argv[1]); i++) {
root = randomInsert(root, i);
}
pre_order(root);
printf("\n");
in_order(root);
return 0;
}
完全二叉树
除了最后一层右侧少节点
image.png
下面不是完全二叉树
image.png
满二叉树 （只有度为2和0的二叉树）
image.png
完美二叉树
image.png
完全二叉树可以用数组来存储
image.png
image.png
