作者：dante

视频链接

构造一个二叉树，如图

使用递归的方式遍历此二叉树。

C语言实现代码：

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

typedef int DataType;

typedef struct Node
{
    DataType data;                  //数据域
    struct Node * lchild;           //指向左孩子
    struct Node * rchild;           //指向右孩子
}BtNode;


//访问节点的函数
void visit(BtNode * node)
{
    printf("data = %d\n",node->data);
}

//先序遍历二叉树  根 - 左 - 右
void PreOrder(BtNode * root)
{
    if(root)
    {
       //访问根
       visit(root);
       PreOrder(root->lchild);          //先序遍历左子树
       PreOrder(root->rchild);          //先序遍历右子树
    }
}

int main()
{
    
    //构造一个二叉树

    BtNode * tree = (BtNode *)malloc(sizeof(BtNode));          //从内存中分配空间
    tree->data = 1;

    BtNode * node2 = (BtNode *)malloc(sizeof(BtNode));
    node2->data = 2;

    BtNode * node3 = (BtNode *)malloc(sizeof(BtNode));
    node3->data = 3;

    BtNode * node4 = (BtNode *)malloc(sizeof(BtNode));
    node4->data = 4;

    BtNode * node5 = (BtNode *)malloc(sizeof(BtNode));
    node5->data = 5;

    BtNode * node6 = (BtNode *)malloc(sizeof(BtNode));
    node6->data = 6;

    BtNode * node7 = (BtNode *)malloc(sizeof(BtNode));
    node7->data = 7;

    tree->lchild = node2;
    tree->rchild = node3;
    node2->lchild = node4;
    node2->rchild = node5;
    node3->lchild = NULL;
    node3->rchild = node6;
    node4->lchild = NULL;
    node4->rchild = NULL;
    node5->lchild = node7;
    node5->rchild = NULL;
    node6->lchild = NULL;
    node6->rchild = NULL;
    node7->lchild = NULL;
    node7->rchild = NULL;

    PreOrder(tree);

    return 0;
}

以上代码可在Linux中使用Gcc编译。

视频链接

二叉树的链式存储之二叉链表。

在单链表中，节点包含两部分，数据域（data）与指针域（next），如图：

数据域用来保存数据（可以是任意类型），指针域用来保存后继节点的地址，所有节点通过指针连在一起。

在二叉链表中，每个节点由三部分组成： 左指针（指向左孩子）、右指针（指向右孩子）、数据域（保存数据），如图：

二叉树的遍历：

• 先序遍历（根-左-右）
• 中序遍历（左-根-右）
• 后序遍历（左-右-根）
• 层次遍历（有多少层）

二叉树的定义中包含了递归的意思，再继续解读，其实左子树和右子树的左右子树其实也还是二叉树，所以可以使用递归进行遍历。

对于先序遍历，遍历的顺序为：访问根节点->先序遍历左子树->先序遍历右子树；
同理，中序遍历：中序遍历左子树->访问根节点->中序遍历右子树；
后序遍历：后续遍历左子树->后序遍历右子树->访问根节点。

视频链接

二叉树的性质：

• 1、二叉树第 i 层上最多有 个节点
• 2、深度为k的二叉树至多有 个节点
• 3、对任何一个二叉树，若度数为0的节点个数为 ,度数为2的节点个数为 ,则
• 4、含有n个节点的完全二叉树的深度为 ，（ 的值向下取整，即舍去小数点）
• 5、将一个含有n个节点的完全二叉树按层编号（从上到下，从左到右），则对任一编号i节点A：①若i=1,则A节点是根；若i>1,则A的双亲Parent(A)编号为 i/2(向下取整)；②若2*i>n,则A既无左孩子也无右孩子，否则A的左孩子Lchild(A)=2*i；③若2*i+1>n,则节点A无右孩子；否则，A的右孩子Rchild(A)的编号为2*i+1；

满二叉树：深度为k(k≥1)且有 个节点的二叉树（节点数已达最大值）

完全二叉树：对满二叉树从上到下，从左到右的顺序编号，并在最下一层删去部分节点，如果删除的这些节点的编号是连续的且删除的节点中含有最大编号的节点，那么这棵树就是完全二叉树。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

观看视频

视频内容：

• 二叉树（Binary Tree）的基本概念

二叉树的定义：

是n（n≥0）个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。

二叉树中的“二”如何理解？

• 二就是2，二就是two
• 有左右（有序）

二叉树的五种形态：

• 空二叉树
• 只有一个根节点的二叉树（左右子树为空）
• 右子树为空的二叉树
• 左子树为空的二叉树
• 左右子树都非空的的二叉树（既有左子树又有右子树）

子树也是二叉树，满足二叉树的五种形态

二叉树的基本运算:

• 初始化
• 求双亲
• 求左孩子、求右孩子
• 建二叉树
• 先序遍历
• 中序遍历
• 后续遍历
• 层次遍历