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

三叉链表存储二叉树

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

构造三叉链表方式：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

另外设计一个填充函数，函数功能是将所有结点的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);
    }
}
1
2
3
4
5
6
7
8
9
10
11

三叉链表的前序遍历（不使用栈）法一

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;//往右边访问
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三叉链表的前序遍历（不使用栈）法二

// 【题目】二叉树采用三叉链表的存储结构，试编写
// 不借助栈的非递归中序遍历算法。
// 三叉链表类型定义：
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;
                }
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

一维数组存储二叉树

// 动态输入
void CreateTreeArray(int a[], int n)
{
    char ch;
    for (int i = 0; i < n; i++)
    {
        cin >> ch;
        a[i] = ch;
    }
}
1
2
3
4
5
6
7
8
9
10

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

// 前序遍历
#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); // 遍历右子树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

线索二叉树的建立

线索二叉的的基本结构：

使用中序遍历的顺序进行线索化。代码中有一个难以理解的点，为什么不用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->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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

真题演练

//建立三叉链表，
//删除每一个元素为x的结点，以及以他为根的子树且释放相应存储空间
#include
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35