数据结构树与二叉树的实现

目录

一、普通树的存储结构

1、双亲表示法

2.孩子表示法

二、二叉树

1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

1）结构体

2.二叉树的链式存储

1）结构体

2）操作

1.创建一颗二叉树

2.创建一个结点

3.二叉树的前序遍历

a.递归实现

b.非递归，使用栈

4.二叉树的中序遍历

a.递归实现

b.非递归实现

5.二叉树的后序遍历

a.递归实现

b.非递归实现

6.二叉树的层次遍历：使用队列

三、线索二叉树

1.先序线索化

2.中序线索化

3.后序线索化

4.拓展，中序线索二叉树中

1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

2）找到p的后继

3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

5）找到p的前驱

6）逆序中序遍历

5.拓展，先序二叉树中

1)寻找后继

2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

6.拓展，后续二叉树中

1）寻找前驱

2）找不到后继，除非能找到父节点，再讨论

四、二叉排序树

1.结构体

2.操作函数

1）创建一颗二叉排序树

2）创建一颗二叉排序结点

3）查找关键值所对应结点

a.递归

b.非递归

4）插入关键值

5）构造一颗二叉排序树，其实就是不断插入的过程

---

一、普通树的存储结构

1、双亲表示法

typedef  struct{
    ElemType data;
    int parent;
}PTNode;
 
typedef  struct{
    PTNode nodes[MAXSIZE];
    int n;  //结点数
}PTree;

2.孩子表示法

struct CTNode{
    int child; //孩子在数组中的下标
    CTNode *next;
};
 
typedef  struct {
    ElemType data;
    CTNode *firstChild;
}CTBox;
 
typedef  struct{
    CTBox nodes[MAXSIZE];
    int n,r;//结点数、根的下标
}CTree;

二、二叉树

1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

1）结构体

struct TreeNode{
    ElemType value;
    bool isEmpty;
};
 
TreeNode t[MAXSIZE]; //一般从下标为1开始存储，为了和下标对应起来，方便查找孩子
 
//顺序存储初始化将所有的isEmpty变为TRUE
 
//左孩子为2i 右孩子为2i+1  父节点为i/2
 
//i>n/2就是叶子结点

2.二叉树的链式存储

1）结构体

//二叉树的链式存储
typedef  struct BiTNode{
    ElemType data;
    BiTNode *lchild,*rchild;
}BiTNode,*BTree;

2）操作

1.创建一颗二叉树

BTree CreatBTree(ElemType rootdata)
{
    BiTNode *root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data=rootdata;
    root->lchild=NULL;
    root->rchild=NULL;
    return  root;
}

2.创建一个结点

BiTNode *CreatBiTNode(ElemType data)
{
    BiTNode* NewNode = (BiTNode*)malloc(sizeof(BiTNode));
    NewNode->data=data;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

3.二叉树的前序遍历

a.递归实现

void PreOrder(BTree T)
{
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

b.非递归，使用栈

//会使用栈
void PreOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p =T;
    while (p||!StackEmpty(s)) {
        if(p){
            visit(p);
            push(s,p);
            p=p->lchild;
        }
        else {
            pop(s,p);
            p=p->rchild;
        }
    }
}

4.二叉树的中序遍历

a.递归实现

void InOrder(BTree T)
{
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

b.非递归实现

void InOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p = T;
    while (p||!StackEmpty(s)) {
        if(p){
            push(s,p);
            p=p->lchild;
        }
        else {
            pop(s,p);
            visit(p);
            p=p->rchild;
        }
    }
}

5.二叉树的后序遍历

a.递归实现

void PostOrder(BTree T)
{
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

b.非递归实现

void PostOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p = T;
    BTree r=NULL;
    while (p||!StackEmpty(s)) {
        if(p){
            push(s,p);
            p=p->lchild;
        }
        else {
          GetTop(s,p);
          if(p->rchild!=r&&p->rchild)
              p=p->rchild;
          else {
              pop(s,p);
              visit(p);
              r=p;
              p=NULL;
          }
        }
    }
}

6.二叉树的层次遍历：使用队列

 
void LevelOrder(BTree T)
{
    LinkQueue Q;
    InitLinkQueue(Q);
    BTree p;
    EnLinkQueue(Q,T);
    while (!LinkQueueEmpty(Q)) {
        DeLinkQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnLinkQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnLinkQueue(Q,p->rchild);
    }
}

三、线索二叉树

1.先序线索化

void PreThread(ThreadTree T, ThreadTree &pre)
{
    if(T!=NULL){
        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
        if(T->ltag==0)
            PreThread(T->lchild,pre);
        PreThread(T->rchild,pre);
 
    }
}
 
void CreatPreThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        PreThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

2.中序线索化

void InThread(ThreadTree T,ThreadTree &pre)
{
    if(T!=NULL){
        InThread(T->lchild,pre);
 
        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
 
        InThread(T->rchild,pre);
    }
 
}
 
void CreatInThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        InThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

3.后序线索化

void PostThread(ThreadTree T, ThreadTree &pre)
{
    if(T!=NULL){
    PostThread(T->lchild,pre);
    PostThread(T->rchild,pre);
 
        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
    }
}
 
void CreatPostThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        PostThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

4.拓展，中序线索二叉树中

1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

ThreadNode *FirstNode(ThreadNode *p)
{
    //找到最左边叶节点
    while (p->ltag==0) {
        p=p->lchild;
    }
    return  p;
}

2）找到p的后继

ThreadNode *NextNode(ThreadNode *p)
{
    if(p->rtag==0)
        return FirstNode(p->rchild);
    else {
        return p->rchild;
    }
}

3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

void InOrder1(ThreadTree T)
{
    for(ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p)){
        visit_Thread(p);
    }
}

4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

ThreadNode *LastNode(ThreadNode *p)
{
    while (p->rtag==0) {
        p=p->rchild;
    }
    return  p;
}

5）找到p的前驱

ThreadNode *preNode(ThreadNode *p){
    if (p->ltag==0) {
        return LastNode(p->lchild);
    }
    else {
        return p->lchild;
    }
}

6）逆序中序遍历

void RevInOrder(ThreadTree T)
{
    for(ThreadNode *p = LastNode(T);p!=NULL;p=preNode(p)){
        visit_Thread(p);
    }
}

5.拓展，先序二叉树中

1)寻找后继

ThreadNode *NextNode_pre(ThreadNode *p)
{
    if(p->rtag==0){
        if(p->lchild!=NULL)
            return p->lchild;
        if(p->rchild!=NULL)
            return p->rchild;
    }
    else {
        return p->rchild;
    }
}

2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

6.拓展，后续二叉树中

1）寻找前驱

ThreadNode *preNode_post(ThreadNode *p)
{
    if(p->ltag==1){
        return p->lchild;
    }
    else {
        if(p->rchild!=NULL)
            return p->rchild;
        else {
            return p->lchild;
        }
    }
}

2）找不到后继，除非能找到父节点，再讨论

四、二叉排序树

1.结构体

typedef  struct BSTNode{
    ElemType data;
    BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

2.操作函数

1）创建一颗二叉排序树

BSTree CreatBSTree(ElemType rootdata)
{
    BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    NewNode->data=rootdata;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

2）创建一颗二叉排序结点

BSTNode *CreatBSTNode(ElemType data)
{
    BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    NewNode->data=data;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

3）查找关键值所对应结点

a.递归

BSTNode *BSTSearch(BSTree bt, ElemTpye key)
{
    if(bt==NULL)
        return  NULL;
    if(bt->data==key)
        return bt;
    else if (bt->data>key) {
        return BSTSearch(bt->lchild,key);
    }
    else {
        return  BSTSearch(bt->rchild,key);
    }
}

b.非递归

BSTNode *BSTSearch(BSTree bt, ElemType key)
{
    while(bt!=NULL and key!=bt->data){
        if(keydata)
            bt=bt->lchild;
        else {
            bt=bt->rchild;
        }
    }
    return bt;
}

4）插入关键值

bool BSTInsert(BSTree &bt, ElemType key)
{
    if(bt==NULL){
        BSTNode *Newnode = CreatBSTNode(key);
        bt=Newnode;
        return true;
    }
    if(bt->data==key){
        return false;
    }
    else if(bt->data>key){
        return BSTInsert(bt->lchild,key);
    }
    else {
        return BSTInsert(bt->rchild,key);
    }
 
}

5）构造一颗二叉排序树，其实就是不断插入的过程

void CreatBST(BSTree &bt, int key[], int n)//key[] 关键字数组，n 关键字数组长度
{
    bt = NULL;
    for (int i=0;i
        BSTInsert(bt,key[i]);
    }
}