数据结构:二叉树的遍历和存储结构

在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继,而二叉树(Binary Tree)的每个节点可以有两个后继。比如这样定义二叉树的节点:

typedef struct node *link;

struct node { 

unsigned char item; 

link l, r;

};

这样的节点可以组织成下图所示的形态。

二叉树可以这样递归地定义: 1. 就像链表有头指针一样,每个二叉树都有一个根指针(上图中的root指针)指向它。根指针可以是NULL,表示空二叉树,或者 2. 根指针可以指向一个节点,这个节点除了有数据成员之外还有两个指针域,这两个指针域又分别是另外两个二叉树(左子树和右子树)的根指针。

链表的遍历方法是显而易见的:从前到后遍历即可。二叉树是一种树状结构,如何做到把所有节点都走一遍不重不漏呢?有以下几种方法,如下图(来自《linux c 编程一站式学习》)所示:

前序(Pre-order Traversal)(深度优先搜索)、中序(In-order Traversal)、后序遍历(Post-order Traversal)、层序遍历(Level-order Traversal)(广度优先搜索)。如何分辨三种次序的遍历方法呢?《data structrue and algorithm analysis in c》中有一句:We can evaluate an expression tree, T, by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.

个人总结就是:前序 (root->left->right) ; 中序(left->root->right); 后序(left->right->root)

举例上图来说,前序遍历,首先root是4,接着要Left,就是指左边子树,在左边子树中又先是root即2,然后是left的1,接着说right的3,现在左边子树递归完毕了,接着右边子树,同样先root即5,没有left,最后是right的6,所以最后排列是421356。

注意:已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

但已知前序和后序遍历序列,是不能确定一棵二叉树的。

如果我们要在内存中建立一个如图6-9-1左图这样的树,为了能让每个结点确认是否有左右孩子,可以对它进行扩展,如右图那样,也就是将二叉树的每个结点的空指针引出一个虚结点,其值为一特定值,比如'#'。我们称这种处理后的二叉树为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树了。比如图6-9-1的前序遍历序列就为AB#D##C##。

示例程序如下:(改变自《大话数据结构》)

#include<iostream>
using namespace std;

#define MAXSIZE 50

typedef char ElemType;
typedef char String[MAXSIZE + 1]; //以'\0’结尾
String str; /* 用于构造二叉树*/
ElemType NoChar = ' '; /* 字符型以空格符为空 */

/* 结点结构 */
typedef struct BTNode
{
    ElemType data;/* 结点数据 */
    struct BTNode *LChild;/* 左右孩子指针 */
    struct BTNode *RChild;
} BTNode, *BTNodePtr;

/* 构造一个字符串 */
bool StrAssign(String Dest, char *ptr)
{
    cout << "Assign Str ..." << endl;
    int i;
    for (i = 0; ptr[i] != '\0' && i < MAXSIZE; i++)
        Dest[i] = ptr[i];
    Dest[i] = '\0';
    return true;
}
/* 构造空二叉树 */
bool InitBTree(BTNodePtr *Tpp)
{
    *Tpp = NULL;
    return true;
}
/* 销毁二叉树 */
void DestroyBTree(BTNodePtr *Tpp)
{
    if (*Tpp)
    {
        if ((*Tpp)->LChild)/* 有左孩子 */
            DestroyBTree(&(*Tpp)->LChild);/* 销毁左孩子子树 */
        if ((*Tpp)->RChild)/* 有右孩子 */
            DestroyBTree(&(*Tpp)->RChild); /* 销毁右孩子子树 */
        free(*Tpp);/* 释放根结点 */
        *Tpp = NULL;/* 空指针赋0 */
    }
}
/* 按前序输入二叉树中结点的值(一个字符) */
/* #表示空树,构造二叉链表表示二叉树。 */
void CreateBTree(BTNodePtr *Tpp)
{
    ElemType ch;
    static int i = 0;
    if (str[i] != '\0')
        ch = str[i++];
    if (ch == '#')
        *Tpp = NULL;
    else
    {
        *Tpp = (BTNodePtr)malloc(sizeof(BTNode));
        if (!*Tpp)
            exit(1);
        (*Tpp)->data = ch;/* 生成根结点 */
        CreateBTree(&(*Tpp)->LChild);/* 构造左子树 */
        CreateBTree(&(*Tpp)->RChild);/* 构造右子树 */
    }
}

bool BTreeEmpty(BTNodePtr Tp)
{
    if (Tp)
        return false;
    else
        return true;
}
/*返回二叉树的深度 */
int BTreeDepth(BTNodePtr Tp)
{
    int i, j;
    if (!Tp)
        return 0;
    if (Tp->LChild)
        i = BTreeDepth(Tp->LChild);
    else
        i = 0;
    if (Tp->RChild)
        j = BTreeDepth(Tp->RChild);
    else
        j = 0;
    return i > j ? i + 1 : j + 1;
}
/* 返回根节点的数值 */
ElemType Root(BTNodePtr Tp)
{
    if (BTreeEmpty(Tp))
        return NoChar;
    else
        return Tp->data;
}
/* 前序递归遍历*/
void PreOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    cout << Tp->data << ' ';
    PreOrderTraverse(Tp->LChild);
    PreOrderTraverse(Tp->RChild);
}
/* 中序递归遍历*/
void InOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    InOrderTraverse(Tp->LChild);
    cout << Tp->data << ' ';
    InOrderTraverse(Tp->RChild);

}
/* 后序递归遍历*/
void PostOrderTraverse(BTNodePtr Tp)
{
    if (Tp == NULL)
        return;
    PostOrderTraverse(Tp->LChild);
    PostOrderTraverse(Tp->RChild);
    cout << Tp->data << ' ';
}

int main(void)
{
    BTNodePtr Tp;
    InitBTree(&Tp);
    StrAssign(str, "ABDH#K###E##CFI###G#J##");
    cout << "输入字符序列(前序遍历)为:" << endl;
    cout << str << endl;
    CreateBTree(&Tp);

    cout << "前序遍历二叉树:" << endl;
    PreOrderTraverse(Tp);
    cout << endl;
    cout << "中序遍历二叉树:" << endl;
    InOrderTraverse(Tp);
    cout << endl;
    cout << "后序遍历二叉树:" << endl;
    PostOrderTraverse(Tp);
    cout << endl;

    cout << "二叉树的根节点为:" << Root(Tp) << endl;
    cout << "二叉树的深度为:" << BTreeDepth(Tp) << endl;

    cout << "销毁二叉树 ..." << endl;
    DestroyBTree(&Tp);
    if (BTreeEmpty(Tp))
        cout << "二叉树现已为空..." << endl << endl;

    return 0;
}

输出为:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 二叉树的镜像

通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们可以得出求一棵树的镜像的过程:先前序遍历这棵树的每个节点...

1452
来自专栏Java Web

数据结构与算法(3)——树(二叉、二叉搜索树)树LeetCode相关题目整理

树是一种类似于链表的数据结构,不过链表的结点是以线性方式简单地指向其后继结点,而树的一个结点可以指向许多个结点;数是一种典型的非线性结构;树结构是以表达具有层次...

2232
来自专栏我的技术专栏

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

1324
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

1872
来自专栏王硕

原 B树C语言代码实现

72910
来自专栏JavaEdge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

7812
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

3242
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

52110
来自专栏老马说编程

(42) 排序二叉树 / 计算机程序的思维逻辑

40节介绍了HashMap,41节介绍了HashSet,它们的共同实现机制是哈希表,一个共同的限制是没有顺序,我们提到,它们都有一个能保持顺序的对应类TreeM...

2026
来自专栏拭心的安卓进阶之路

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二叉树。 ? 什么是二叉树 Binary Tree 先来个定义: 二叉树是有限个节点的集合,这个集合...

3036

扫码关注云+社区

领取腾讯云代金券