二叉树的遍历+基础练习

前面完全二叉树适合存放数据，又因为它在内存中连续存储，因此用顺序表来实现它，并介绍了堆排序及TOP-K问题。

今天我们了解一下二叉树的遍历问题，并完成几道二叉树基础练习

二叉树的遍历

二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

以下面二叉树为例，进行先序，中序，后序遍历：

先序

分析：从根节点开始，先访问根，再访问左子树（左子树中先访问根节点，在访问左子树和右子 树），最后访问右子树（先访问根节点，在访问左子树和右子树）

访问顺序：

先访问树tree根1，再访问tree左子树L1:

访问L1根2，再访问其左子树Ll2:

访问Ll2根3，再访问其左子树：左子树为空，访问其右子树，右子树为空，返回上一个子树L1；

此时L1左子树访问完毕，访问L1右子树NULL，为空返回上一个树tree;

此时tree根和左子树访问完毕，访问tree右子树R1:

访问R1根4，再访问R1左子树Rl1:

访问Rl1根5，再访问Rl1左子树和右子树NULL，返回上一个树R1；

此时，R1左子树Rl1访问完毕，接着访问R1右子树Rr1：

访问Rr1根6，再访问Rr1左右子树NULL，返回上一个树R1；

此时R1根和左右子树访问完毕，返回上一个树tree；

此时tree的根和左子树访问完毕，及整个树访问完毕。

图示：

中序

分析：即先访问左子树，左子树访问完毕后再访问根节点，根节点访问完后，最后访问右子树。左子树和右子树中也是先访问左子树，再根，最后右子树。

访问顺序：

从tree根开始，先访问其左子树L1：

左子树L1不为空，访问L1左子树Ll2：

左子树Ll2不为空，访问Ll2左子树：

左子树为空，访问Ll2根3，再访问Ll2的右节点，右节点为空，返回子树L1；

子树L1的左子树访问完毕，访问L1的根2，再访问L1的右子树，为空，返回树tree；

tree的左子树访问完毕，访问tree根1，接着访问tree右子树R1：

右子树R1不为空，访问R1左子树Rl1：

Rl1不为空，访问Rl1左子树，左子树为空，访问Rl1根5，再访问其右子树：

右子树为空，返回上一个树R1；

R1左子树访问完毕，访问其根4，接着访问其右子树Rr1：

Rr1不为空，访问其左子树，左子树为空，访问Rr1根6，再访问其右子树为空，返回R1；

此时tree的左子树，根，和右子树都访问完毕。

图示：

后序

分析：先访问左子树（左子树中也是左子树，右子树，根），再访问右子树（右子树中也是左子树，右子树，根），最后访问根节点。

访问顺序：

先访问tree，不为空，访问其左子树L1，L1不为空，访问其左子树Ll2；

Ll2不为空，访问其左子树，为空；访问其右子树，为空；访问其根3，返回上一个树L1；

L1左子树访问完毕，访问其右子树，为空；访问其根2，返回上一个树tree；

tree的左子树访问完毕，访问其右子树R1，R1不为空，访问其左子树Rl1；

Rl1不为空，访问其左子树，为空；访问其右子树，为空，访问其根5，返回上一个树R1；

R1左子树访问完毕，访问其右子树Rr1，Rr1不为空，访问其左子树；

Rr1左子树为空，访问其右子树，为空，访问其根6，返回上一个树R1；

此时R1左子树右子树访问完毕，访问其根4，放回上一个树tree；

此时tree的左右子树访问完毕，访问其根1；整个树访问完毕。

图示：

手动构建链式二叉树

不难发现，上述遍历时中途总会返回上一层树，已经用到了递归思想，这里我们手动实现一个简单的链式二叉树，完成我们的前序，中序，后序的遍历。

定义

定义每个节点由数据，左子树地址和右子树地址组成

typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;  //数据
    struct BinaryTreeNode* left;   //左子树地址
    struct BinaryTreeNode* right;  //右子树地址
}BTNode;

创建节点

将固定的数据放入创建的节点中，左右子树指针置空

BTNode* BuyNode(BTDataType x)
{
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = x;
    root->left = NULL;
    root->right = NULL;
    return root;
}

创建二叉树

手动创建节点，并将左右子树指针指向固定的位置，以上述二叉树为例：

//手动创建
BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}

前序遍历

依照我们对前序遍历的顺序分析：根，左子树，右子树，编写前序代码：

// 二叉树前序遍历
void PreOrder(BTNode* root)
{
    if (root==NULL)
    {
        return;
    }
    printf("%d ",root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

中序遍历

// 二叉树中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

后序遍历

// 二叉树后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

练习

求二叉树节点树

方法一：前序中序后序时添加一个计数变量（变量为全局或者静态，防止递归时计数重置）

缺点：重复调用时计数会累加，每次调用时须将count重新置0；

//定义全局或者静态变量
//多次调用会累加
int count = 0;
int BTreeSize(BTNode* root)
{
    if (root == NULL)
        return;
    ++count;
    BTreeSize(root->left);
    BTreeSize(root->right);
    return  count;
}

方法二：遍历+计数（遍历时将遍历地址传过去）

//遍历+计数
//将变量地址传过去，计数---思想最优
void BTreeSize(BTNode* root,int* count)
{
    if (root == NULL)
        return;
    ++(*count);
    BTreeSize(root->left,count);
    BTreeSize(root->right,count);
}

方法三：递归--分治思想

当根为空时，返回0，左子树节点个数+右子树节点个数+1（根节点本身）

//递归--分治思想--节点个数
int BTreeSize(BTNode* root)
{
    return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

求二叉树叶子节点个数

二叉树叶子节点数 = 左子树叶子节点数 + 右子树节点数

叶子节点：左子树和右子树为空的节点

//叶子节点个数
int BTreeLeafSize(BTNode* root)
{
    if (root==NULL)
    {
        return 0;
    }
    if (root->left == NULL&&root->right==NULL)
    {
        return 1;
    }
    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

第k层节点数

求tree的第三层节点数

即L1和R1的第二层节点数之和

即Ll1、Rl1和Rr1第一层节点数之和

当k=1时，返回1即可

//第k层节点个数
int BTreeLeveSize(BTNode* root,int k)
{
    assert(k>=1);
    if (root==NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return BTreeLeveSize(root->left, k - 1) + BTreeLeveSize(root->right, k - 1);

二叉树深度

二叉树的深度 = 左子树和右子树中最大深度度+1

需要比较左右子树高度，判断返回哪一个

//二叉树深度
int BTreeDepth(BTNode* root)
{
    if (root==NULL)
    {
        return 0;
    }
    int leftdepth = BTreeDepth(root->left);
    int rightdepth = BTreeDepth(root->right);
    return leftdepth >rightdepth ? leftdepth + 1 : rightdepth + 1;
}

二叉树查找值为x的节点

判断根是否为要找的节点，是则返回节点地址

不是则进左子树中去找，找到返回节点地址，找不到返回空

再进右子树取找，找到返回节点地址，找不到返回空

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root==NULL)
    {
        return NULL;
    }
    if (root->data == x)
        return root;
    if (BinaryTreeFind(root->left, x))
        return BinaryTreeFind(root->left,x);
    if (BinaryTreeFind(root->right, x))
        return BinaryTreeFind(root->right, x);
    return NULL;
}