目录

 一、二叉树的遍历（递归算法）

1.1 DLR先序遍历

1.2 LDR中序遍历

1.3 LRD中序遍历

二、遍历算法的应用

2.1 输出二叉树中的结点

2.2 输出二叉树中的叶结点 

2.3 统计叶结点数目

2.4 二叉树的创建

2.4.1 介绍：先序定位串

2.4.2 算法实现

2.5 二叉树的销毁

2.6 求二叉树的高度

1.1 DLR先序遍历

若二叉树为空，则为空操作，否则依次执行如下三个操作：

1、访问根结点；

2、按先序遍历左子树；

3、按先序遍历右子树。

void PreOrder(BiTree root) {
    if (root == NULL) return;

    Visit(root->data);
    PreOrder(root->LChild);
    PreOrder(root->RChild);
}

1.2 LDR中序遍历

若二叉树为空，则为空操作，否则依次执行如下三个操作：

1、按中序遍历左子树；

2、访问根结点；

3、按中序遍历右子树。

void InOrder(BiTree root) {
    if (root == NULL) return;

    InOrder(root->LChild);
    Visit(root->data);
    InOrder(root->RChild);
}

1.3 LRD中序遍历

若二叉树为空，则为空操作，否则依次执行如下三个操作：

1、按后序遍历左子树；

2、按后序遍历右子树；

3、访问根结点。

void PostOrder(BiTree root) {
    if (root == NULL) return;

    PostOrder(root->LChild);
    PostOrder(root->RChild);
    Visit(root->data);
}

---

二、遍历算法的应用

2.1 输出二叉树中的结点

先序遍历输出二叉树中的结点。

void PreOrder(BiTree root) {
    if (root == NULL) return;

    print(root->data);
    PreOrder(root->LChild);
    PreOrder(root->RChild);
}

2.2 输出二叉树中的叶结点 

先序遍历输出二叉树中的叶结点。

void PreOrder(BiTree root) {
    if (root == NULL) return;

    if (root->LChild == NULL && root->RChild == NULL)
        print(root->data);
    PreOrder(root->LChild);
    PreOrder(root->RChild);
}

2.3 统计叶结点数目

先序遍历统计叶结点数目。

void GetLeavesNum(BiTree root, int *num) {
    if (root == NULL) return;

    if (root->LChild == NULL && root->RChild == NULL)
        ++ *num; 

    GetleavesNum(root->LChild, num);
    GetleavesNum(root->RChild, num);
}

---

2.4 二叉树的创建

2.4.1 介绍：先序定位串

给定一棵二叉树，可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，也就可以创建相应的二叉链表。

这里所说的遍历序列是一种扩展的遍历序列。在通常的遍历序列中均忽略空子树，而在扩展的遍历序列中，必须用特定的元素表示空子树，如小圆点 “.” 。

示例：

2.4.2 算法实现

利用扩展的先序遍历序列创建二叉链表。

BiTree _CreateByStr(char *nodes, int *i) {
    
    if (nodes[*i] == '') return NULL;

    
    if (nodes[*i] == '.') {
        ++ *i; 
        return NULL;
    }

    
    BiTree root = (BiTree)malloc(sizeof(BiTNode));
    root->data = *find_ref_entry(nodes[*i]);
    
    ++ *i;
    
    root->LChild = _CreateByStr(nodes, i); 
    root->RChild = _CreateByStr(nodes, i); 

    return root;
}

递归过程示意图： 

---

2.5 二叉树的销毁

后序遍历销毁二叉树。

void DestroyBiTree(BiTree root) {
    
    if (root == NULL) return;

    DestroyBiTree(root->LChild);
    DestroyBiTree(root->RChild);
    free(root);
}

2.6 求二叉树的高度

二叉树的高度为二叉树中结点层次的最大值，也可视为其左、右子树高度的最大值加1。

分治法求二叉树的高度。

int TreeHeight(BiTree root) {
    if(root == NULL) return 0;

    int hl = TreeHeight(root->LChild); 
    int hr = TreeHeight(root->RChild); 
    return (hl > hr ? hl : hr) + 1;
}