二叉树的存储与基本操作

发表于   |   分类于

主要是二叉树的链式存储和初始化等操作.

一. 二叉树的顺序存储

1. 含义

用一个数组依次存放二叉树的结点, 如果是满二叉树或者完全二叉树还可以, 如果是其他的二叉树, 为了确定元素在树中的位置, 需要将其转换为完全二叉树, 存储结点的时候, 如果原本没有这个结点, 那么就用 0 来表示.

二. 二叉树的链式存储

1. 含义(二叉链表存储)

用结构体表示一个结点, 每个结点有数据域存放数据, 还有两个指针分别指向左右子树.

2. 代码

1
2
3
4
5
typedef struct BiTNode
{
    DataType data;
    struct TNode * lchild, * rchild;
}BiTNode, * BiTree;

3. 改进

如果希望方便的找到结点的双亲, 可以在结点结构体里添加一个双亲域.

三. 二叉树的基本操作

1. 建立一棵空二叉树

1
2
3
4
5
6
7
int Initate(BiTree bt)
{
    if(bt=(BiTree)malloc(sizeof(BiTNode))==NULL)  return 0;
    bt->lchild = NULL;
    bt->rchild = NULL;
    return 1;
}

(???主函数是什么样的?传个指针过来是否可行)

2. 生成一棵树

这个函数可以通过画图理解, 注意这样生成一棵树是通过多次调用函数, 从下往上生成的.

1
2
3
4
5
6
7
8
9
BiTree Create(elemtype x, BiTree lbt, BiTree rbt)
{
    BiTree p;
    if(p=(BiTree)malloc(sizeof(BiTNode))==NULL)  return 0;
    p->data = x;
    p->lchild = lbt;
    p->rchild = rbt;
    return p;
}

3. 将 x 插入二叉树, 并作为 parent 的左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
BiTree InsertL(BiTree bt, elemtype x, BiTree parent)
{
    BiTree p;
    if(parent==NULL)
    {
        printf("插入出错!\n");
        return NULL;
    }
    if(p=(BiTree)malloc(sizeof(BiTNode))==NULL)  return NULL;
    p->data = x;
    p->lchild = NULL;
    p->rchild = NULL;
    if(parent->lchild == NULL)
    {
        parent->lchild = p;
    }
    else
    {
        p->lchild = parent->lchild;
        parent->lchild = p;
    }
    return bt;
}

4. 将 x 插入二叉树, 并作为 parent 的右子树

跟上面的代码类似. (略)

5. 删除二叉树中 parent 的左子树

1
2
3
4
5
6
7
8
9
10
11
12
13
BiTree DeleteL(BiTree bt, BiTree parent)
{
    BiTree p;
    if(parent==NULL || parent->lchild==NULL)
    {
        printf("删除出错!\n");
        return NULL;
    }
    p = parent->lchild;
    free(p);  //实际上还要遍历的释放所有元素
    parent->lchild = NULL;  //避免成为野指针
    return bt;
}

6. 删除二叉树中 parent 的右子树

和上面类似. (略)

7. Search(bt, x) 在二叉树中查找 x

(略)