树与二叉树

树

• 非线性结构
• 与现实的树倒过来，自上而下
• 不能向下伸展的节点叫叶子节点
• 第一个节点叫头节点也叫（全集）
• 树由边与节点组成
• 节点：代表集合
• 边：代表关系

树形结构和栈方便解决具有完全包含关系的问题

树的性质

树的深度

• 从根节点向下走的最长路径的节点个数

节点的高度

• 从该节点向下走的最长路径的节点个数

节点的深度

• 从头节点开始到该节点的路径的节点数

度

• 图的数据结构度又分为出度和入度
• 在树形结构的度指节点的出度
• 出度：该节点指向别的节点的边的数量
• 入度：指向该节点边的数量

节点的数量

• 节点数量等于边的数量加一

例如

• 节点29的深度度为2，出度为2，入读为1，高度为3

三叉树

结构定义

typedef struct Node {
    int data;
    struct Node *next[3];
} Node, *Tree;

结构操作

N叉树

• N叉树怎么转换为二叉树

左孩子右兄弟法，也叫十字链表法

二叉树

二叉树的性质

• 每个节点的度最多为2
• 度为0的节点 比 度为2的节点多一个, 证明如下

度为2的节点个数为n2, 同理，n1, n0.
节点个数 = 边数 + 1 =》 n2 + n1 + n0 = 1 +  2*n2 + n1 + 0*n0     =》     n2 + 1  = n0.

二叉树的遍历

前序遍历	中序遍历	后序遍历
根 左 右	左 根 右	左 右 根

• 前序遍历 ： 【1】、【2、4、5】、【3、6】
• 中序遍历 ： 【4、2、5】、【1】、【3、6】
• 后序遍历 ： 【4、5、2】、【6、3】、【1】

二叉树的分类

• 完全二叉树：该二叉树只有度为2和度为0的节点，也可以存在唯一 一个度为1的节点，且该节点只能有左孩子，不能有右孩子。

• 满二叉树（完美二叉树）：没有度为1的节点

完全二叉树

性质

• 可以用连续空间存储 ( 数组 )
• 编号为i的字节点：
• 左孩子编号：2 * i
• 右孩子编号：2 * i + 1

结构定义

//结构定义 
typedef struct Node {
    int data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree; 

前序遍历

void pre_order_Node(Node *n) {
    if (n == NULL) return ;
    printf("%d ", n->data);
    pre_order_Node(n->lchild);
    pre_order_Node(n->rchild);
    return ;
}

void pre_order(Tree *t) {
    if (t == NULL) return ;
    printf("前序遍历：");
    pre_order_Node(t->root);
    printf("\n");
}

中序遍历

void in_order_Node(Node *n) {
    if (n == NULL) return ;
    in_order_Node(n->lchild);
    printf("%d ", n->data);
    in_order_Node(n->rchild);
    return ;
}

void in_order(Tree *t) {
    if (t == NULL) return ;
    printf("中序遍历：");
    in_order_Node(t->root);
    printf("\n");
}

后序遍历

void post_order_Node(Node *n) {
    if (n == NULL) return ;
    post_order_Node(n->lchild);
    post_order_Node(n->rchild);
    printf("%d ", n->data);
    return ;
}

void post_order(Tree *t) {
    if (t == NULL) return ;
    printf("前序遍历：");
    post_order_Node(t->root);
    printf("\n");
}

代码演示

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//结构定义 
typedef struct Node {
    int data;
    struct Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree; 


//结构操作
 
Node *getNewNode(int val) { 
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    node->lchild = node->rchild = NULL;
    return node;
} 

Tree *getNewTree() {
    Tree *t = (Tree *)malloc(sizeof(Tree));
    t->root = NULL;
    t->length = 0;
    return t;
}

Node *insert_Node(Node *root, int val, int *flag) {
    if (root == NULL) {
        *flag = 1;
        return getNewNode(val);
    }
    if (root->data == val) return root; //返回当前节点，不进行插入操作 
    else if (root->data > val) root->lchild = insert_Node(root->lchild, val, flag);
    else root->rchild = insert_Node(root->rchild, val, flag);
    return root;
}

void insert(Tree *t, int val) {
    if (t == NULL) return ;
    int flag = 0;
    t->root = insert_Node(t->root, val, &flag);
    t->length += flag;
    return ; 
}

void pre_order_Node(Node *n) {
    if (n == NULL) return ;
    printf("%d ", n->data);
    pre_order_Node(n->lchild);
    pre_order_Node(n->rchild);
    return ;
}

void pre_order(Tree *t) {
    if (t == NULL) return ;
    printf("前序遍历：");
    pre_order_Node(t->root);
    printf("\n");
}

void in_order_Node(Node *n) {
    if (n == NULL) return ;
    in_order_Node(n->lchild);
    printf("%d ", n->data);
    in_order_Node(n->rchild);
    return ;
}

void in_order(Tree *t) {
    if (t == NULL) return ;
    printf("中序遍历：");
    in_order_Node(t->root);
    printf("\n");
}

void post_order_Node(Node *n) {
    if (n == NULL) return ;
    post_order_Node(n->lchild);
    post_order_Node(n->rchild);
    printf("%d ", n->data);
    return ;
}

void post_order(Tree *t) {
    if (t == NULL) return ;
    printf("前序遍历：");
    post_order_Node(t->root);
    printf("\n");
}

void clear_Node(Node *n) {
    if (n == NULL) return ;
    clear_Node(n->lchild);
    clear_Node(n->rchild);
    free(n);
    return ;
}

void clear_Tree(Tree *t) {
    if (t == NULL) return ;
    clear_Node(t->root);
    free(t);
    return ;
}

//广义表二叉树输出
void output_Node(Node *n) {
    if (n == NULL) return ;
    printf("%d", n->data);
    if (n->lchild == NULL && n->rchild == NULL) return ;
    printf("(");
    output_Node(n->lchild);
    printf(",");
    output_Node(n->rchild);
    printf(")");
    return ;
}

void output(Tree *t) {
    if (t == NULL) return ;
    printf("Tree(%d): ", t->length);
    output_Node(t->root);
    printf("\n");
    return ; 
}

int main() {
    srand(time(0));
    #define n 30
    Tree *t = getNewTree();
    for (int i = 0; i < n; i++) {
        int val = rand() % 100;
        insert(t, val);
        printf("插入: %d\n", val); 
        output(t);
    }
    pre_order(t);
    in_order(t);
    post_order(t);
    #undef n
    clear_Tree(t);
    return 0;
}