【考研复习】二叉树的特殊存储|三叉链表存储二叉树、一维数组存储二叉树、线索二叉树

这篇具有很好参考价值的文章主要介绍了【考研复习】二叉树的特殊存储|三叉链表存储二叉树、一维数组存储二叉树、线索二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

三叉链表存储二叉树

三叉链表结构体表示如下图所示:

三叉链表,考研,链表,数据结构

构造三叉链表方式:

typedef struct node{
    char data;
    struct node*parent,*lchild,*rchild;
}BTNode,*BiTree;
BTNode * creattree(BiTree &t){ // 易错点:树的引用
    char ch;
    cin>>ch;
    if(ch=='#'){
        t=NULL;
    }else{
        t=(BTNode*)malloc(sizeof(BTNode));// 易错点:忘记重新创建新结点
        t->data=ch;
        t->parent=NULL;
        t->lchild=NULL;
        t->rchild=NULL;
        if(t->lchild) t->lchild->parent=t;
        if(t->rchild) t->rchild->parent=t;
        creattree(t->lchild);
        creattree(t->rchild);
    }
    return t;
}

另外设计一个填充函数,函数功能是将所有结点的parent结点填充正确。

void FillParent(BiTree &root){
    if(root==NULL) return;
    if(root->lchild) {
        root->lchild->parent=root;
        FillParent(root->lchild);
    }
    if(root->rchild){
        root->rchild->parent=root;
        FillParent(root->rchild);
    }
}

三叉链表的前序遍历(不使用栈)法一

void PreOrder(BiTree t){   //访问顺序:根左右
    BTNode *p;
    while(t){
        visit(t);//访问根
        if(t->lchild) t=t->lchild;//找到左下结点,下一次就循环访问左
        else if(t->rchild) t=t->rchild;//下一次循环访问右
        else{//如果当前结点既没有左孩子也没有有孩子
            while(1){//一直往上回溯到有非空的父亲结点、同时找到二叉树的那个“叉”
                p=t;//p指向根t
                t=t->parent;//t指向父亲结点
                if(!t) break;//如果t为空,则说明该节点是空结点,排除这种情况
                if(t->lchild==p&&t->rchild) break;//如果t的左孩子是p且t的右孩子不为空,跳出while之后到右结点
            }
            if(t)t=t->rchild;//往右边访问
        }
    }
}

三叉链表的前序遍历(不使用栈)法二

// 【题目】二叉树采用三叉链表的存储结构,试编写
// 不借助栈的非递归中序遍历算法。
// 三叉链表类型定义:
typedef struct TriTNode
{
    char data;
    struct TriTNode *parent, *lchild, *rchild;
} TriTNode, *TriTree;

void InOrder(TriTree PT, void (*visit)(char))
/* 不使用栈,非递归中序遍历二叉树PT,  */
/* 对每个结点的元素域data调用函数visit */
{
    TriTree p = PT, pr;
    while (p)
    {
        if (p->lchild)
            p = p->lchild; // 寻找最左下结点
        else
        {
            visit(p->data); // 找到最左下结点并访问
            if (p->rchild)
            {
                p = p->rchild; // 若有右子树,转到该子树,继续寻找最左下结点
            }
            else
            {
                pr = p; // 否则返回其父亲
                p = p->parent;
                while (p && (p->lchild != pr || !p->rchild))
                {                        // 若其不是从左子树回溯来的,或左结点的父亲并没有右孩子
                    if (p->lchild == pr) // 若最左结点的父亲并没有右孩子
                        visit(p->data);  // 直接访问父亲(不用转到右孩子)
                    pr = p;              // 父亲已被访问,故返回上一级
                    p = p->parent;       // 该while循环沿双亲链一直查找,若无右孩子则访问,直至找到第一个有右孩子的结点为止(但不访问该结点,留给下步if语句访问)
                }
                if (p)
                { // 访问父亲,并转到右孩子(经上步while处理,可以确定此时p有右孩子)
                    visit(p->data);
                    p = p->rchild;
                }
            }
        }
    }
}

一维数组存储二叉树

// 动态输入
void CreateTreeArray(int a[], int n)
{
    char ch;
    for (int i = 0; i < n; i++)
    {
        cin >> ch;
        a[i] = ch;
    }
}

一维数组存储二叉树的先序遍历

// 前序遍历
#define Maxsize 50
typedef struct BTNodeArray
{
    int data[Maxsize];
    int length;
} BTNodeArray;
void PreOrderArray(BTNodeArray t, int i)
{
    if (i >= t.length)
        return;
    printf("%d", t.data[i]);
    PreOrderArray(t, i * 2);     // 遍历左子树
    PreOrderArray(t, i * 2 + 1); // 遍历右子树
}

线索二叉树的建立

线索二叉的的基本结构:

三叉链表,考研,链表,数据结构
三叉链表,考研,链表,数据结构

使用中序遍历的顺序进行线索化。代码中有一个难以理解的点,为什么不用p直接找后继,而是使用了前驱结点找后继。实际上,不是不用p找后继,而是从p找不到后继,所以只能间接地找前驱的后继,这样的方式找后继,明白了这点,代码就不难懂了。

//中序遍历线索化
void InOrder(ThreadTree &p,ThreadTree &pre){
    if(p!=NULL){
        InOrder(p->lchild,pre);
        if(p->lchild==NULL){    //只能通过当前结点找前驱
            p->lchild=pre;
            p->ltag=1;
        }
		if(pre!=NULL&&pre->rchild==NULL){  //只能通过前驱结点找后继
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        InOrder(p->rchild,pre);
    }
    return;
}
void InOrderThread(ThreadTree t){
    ThreadNode *pre=NULL;
    if(t!=NULL){
        InOrder(t,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

中序线索二叉树的遍历

//中序线索二叉树的遍历
//--最左下的结点
ThreadTree FirstNode(ThreadTree p){
    while(p->ltag==0) p=p->lchild;
    return p;
}
//--结点的后继
ThreadTree NextNode(ThreadTree p){
    if(p->rtag==0) p=p->rchild;
    else FirstNode(p->rchild);
}
//--开始遍历
void InOrderThreadCount(ThreadTree t){
    for(ThreadNode *p=FirstNode(t);p!=NULL;p=NextNode(p)) cout<<p->data<<endl;
}

真题演练

三叉链表,考研,链表,数据结构文章来源地址https://www.toymoban.com/news/detail-764338.html

//建立三叉链表,
//删除每一个元素为x的结点,以及以他为根的子树且释放相应存储空间
#include<iostream>
using namespace std;

void BuildTree(BiTree &t){
    char ch;
    cin>>ch;
    if(ch=='#'){
        t=NULL;
    }else{
        t=(BTNode *)malloc(sizeof(BTNode));
        t->data=ch;
        t->parent=NULL;
        t->lchild=NULL;
        t->rchild=NULL;
        if(t->lchild) t->lchild->parent=t;
        if(t->rchild) t->rchild->parent=t;
        BuildTree(t->lchild);
        BuildTree(t->rchild);
    }
}
void Destory(BiTree t){
    if(t==NULL) return;
    if(t->lchild) Destory(t->lchild);
    if(t->rchild) Destory(t->rchild);
    free(t);    //释放根节点
    t=NULL;     //空指针赋值0
}
void DeleteX(BiTree &t,char x){
    if(t==NULL) return;
    if(t->data==x) Destory(t);
    DeleteX(t->lchild,x);
    DeleteX(t->rchild,x);
}

到了这里,关于【考研复习】二叉树的特殊存储|三叉链表存储二叉树、一维数组存储二叉树、线索二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:二叉树:第3关:基于二叉链表的二叉树的遍历

    任务描述 设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写三个递归算法分别实现二叉树的先序、中序和后序遍历。 编程要求 输入 多组数据。每组数据一行,为二叉树的前序序列(序列中元素为‘0’时,表示该结点为空)。当输入只有一个

    2024年02月03日
    浏览(39)
  • 二叉树的链式存储

    2024年02月14日
    浏览(36)
  • 树与二叉树的存储与遍历

    如前面的顺序表,链表,栈和队列都是线性的数据结构,树是非线性的结构。树可以有n个结点,n=0,当n=0是就表示树为空 n0,代表树不为空,不为空的树,它只有一个根结点,然后其余的结点又是构成互不相交的树,然后这些树本身又是一棵树,这些树且为根节点的子树。 任何

    2023年04月16日
    浏览(37)
  • 二叉树的存储方式、遍历、构建、判定

    目录 树的定义 二叉树的定义 二叉树的存储表示 二叉树的创建和前中后序遍历 通过中序遍历和先序遍历来构建树 通过后序遍历加先序遍历构建树 链式存储的树 将其中序遍历 非递归后序遍历 非递归后序遍历第二种方法 非递归中序遍历 非递归前序遍历 层次遍历 求二叉树节

    2024年02月05日
    浏览(38)
  • 二叉树的创建与存储,以及遍历

    树是n个节点的集合,在任何一棵非空树中有且仅有一个被称为根的结点,当n1时,其余结点可以被分为m个互不相交的子集,其中每个子集又是一棵树,称其为根的子树 结点:一个数据元素以及若干指向其子树的分支 结点的度:结点所拥有的子树的棵树 树的度:树中各个结点

    2024年02月05日
    浏览(47)
  • 数据结构-二叉树的链式存储

    二叉树的存储结构有顺序结构和链式结构两种,顺序结构我已经在上篇进行了详细的讲解,地址:数据结构-二叉树的顺序存储与堆(堆排序),本篇我们就主要讲解二叉树的链式存储。 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。

    2024年02月02日
    浏览(49)
  • 二叉树的顺序存储及基本操作

    1、在树中除根结点外,其余结点分成m(m≥0)个(A)的集合T1,T2,T3…Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。 A、互不相交B、可以相交C、叶节点可以相交D、树枝结点可以相交 2、在一棵度为3的树中,度为3的结点数为2个,度为2的结点

    2024年02月06日
    浏览(50)
  • 【数据结构】二叉树的链式存储结构

    前序遍历,又叫先根遍历。 遍历顺序:根 - 左子树 - 右子树 代码: 中序遍历,又叫中根遍历。 遍历顺序:左子树 - 根 - 右子树 代码 : 后序遍历,又叫后根遍历。 遍历顺序:左子树 - 右子树 - 根 代码 : 除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍

    2024年02月09日
    浏览(42)
  • 数据结构——二叉树的链式存储的实现

                             InitBiTree(BiTree T)——初始化二叉树。                         CreateBiTree(BiTree T)——先序遍历的顺序建立二叉链表。                         PreOrderTraverse(BiTree T)——先序遍历。                         

    2024年02月04日
    浏览(51)
  • 【数据结构】二叉树的顺序存储结构 —— 堆

    👑作者主页:@进击的安度因 🏠学习社区:进击的安度因(个人社区) 📖专栏链接:数据结构

    2023年04月08日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包