数据结构-树

树的存储结构

1．双亲数组存储结构

用一个一维数组存储树中的各个节点，数组元素是一个记录，包含data和parent两个字段，分别表示节点的数据值和其双亲在数组中的下标。其类型定义如下：

typedef struct
{  
    ElemType data;
    int parent;
} ParType[MaxSize];

在这个一维数组中，树中节点可按任意顺序存放。

例如，图5-1中给出的树，它的双亲数组存储表示如图5-3所示。其中，规定下标为0的位置存储的节点是根节点。

位置	0	1	2	3	4	5	6	7	空闲	Maxsize-1
data	A	B	C	D	E	F	G	H	…
parent	-1	0	0	0	2	2	3	4	…

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　图5-3 树的双亲数组存储结构

在双亲数组中，找某个节点的双亲或祖先是很方便的，但要找某个节点的孩子或兄弟则较麻烦，需要遍历整个数组。

2．孩子链表存储结构

把每个节点的孩子节点排列起来，构成一个单链表，称为孩子链表。n个节点的树有n个这样的孩子链表，其中，树叶的孩子链表为空表。为便于查找，n个链表的表头指针放在一个顺序表中。这个顺序表中的每个元素有两个字段：一个存放节点的值；另一个存放第一个孩子的地址。孩子链表中的每个节点也有两个字段：指示孩子节点的值存放的位置；另一个存放下一个孩子的地址。在顺序表中，各元素可以按任意顺序存放。在每个孩子链表中，各节点也可以按任意顺序链接。

单链表中每个节点的类型定义如下：

typedef struct node1
{  
    int adjvex;                             /*该节点值在顺序表中的位置*/
    struct node1 *next;
} ChildType;

顺序表的类型定义如下：

typedef struct
{  
    ElemType data;
    ChildType *children;
} Child[MaxSize];

图5-4是图5-1所示树的孩子链表存储结构。其中，规定表头中下标为0的位置存储的节点是根节点。

图5-4 树的孩子链表存储结构

显然，在孩子链表中，找某个节点的孩子很容易，但找节点的双亲则较困难。

3．孩子兄弟链表存储结构

孩子兄弟链表存储结构是一种二叉链表，链表中每个节点包含两个指针，分别指向对应节点的第一个孩子和下一个兄弟。每个节点的类型定义如下：

typedef struct node2
{  
    ElemType data;
    struct node2 *child,*brother;
} CBNodeType;

图5-5是图5-1所示树的孩子兄弟链表存储结构，其中，T₁指针指向树的根节点。

出自：http://www.qacn.net/viewchapter.aspx?topicid=147&chapterid=2771

二叉树的存储结构

1、顺序存储结构

　　A(B(D,E(G,H)),C(,F(I)))存储为：

2、链式存储结构

　　利用左右孩子指针。

二叉树的基本运算及四种遍历方式

#include <iostream>
#include <cstdlib>
using namespace std;

#define MaxSize 100

typedef struct Node{
    char data;
    struct Node *lChild, *rChild;
}BTNode;

//先序遍历
void PreOrder(BTNode *bt){
    if(bt != NULL){
        cout << bt->data << " ";
        PreOrder(bt->lChild);
        PreOrder(bt->rChild);
    }

}

//中序遍历
void InOrder(BTNode *bt){
    if(bt != NULL){
        InOrder(bt->lChild);
        cout << bt->data << " ";
        InOrder(bt->rChild);
    }
}

//后序遍历
void LastOrder(BTNode *bt){
    if(bt != NULL){
        LastOrder(bt->lChild);
        LastOrder(bt->rChild);
        cout << bt->data << " ";
    }
}

//层次遍历
//先是根节点进入队列，紧接着是其左右孩子，在用左右孩子循环。
void LeverOrder(BTNode *bt){
    BTNode *p;
    BTNode *qu[MaxSize];
    int front,rear;
    front = rear = -1;
    rear++;
    qu[rear] = bt;
    while(front != rear){
        front = (front+1)%MaxSize;
        p = qu[front];
        cout << p->data << " ";
        if(p->lChild != NULL){
            rear = (rear+1)%MaxSize;
            qu[rear] = p->lChild;
        }
        if(p->rChild != NULL){
            rear = (rear+1)%MaxSize;
            qu[rear] = p->rChild;
        }
    }
}

//以括号表示法输出二叉树
void DispBTree(BTNode *bt)
{
    if(bt!=NULL)
    {
        cout << bt->data;
        if(bt->lChild!=NULL || bt->rChild!=NULL)
        {
            cout<<"(";
            DispBTree(bt->lChild);                      /*递归处理左子树*/
            if(bt->rChild!=NULL)
cout << ",";
            DispBTree(bt->rChild);                      /*递归处理右子树*/
            cout<<")";
        }
    }
}

//叶子节点数
int LeafCount(BTNode *bt){
    int l,r;
    if(bt == NULL){
        return 0;
    }
    else{
        if(bt->lChild == NULL && bt->rChild == NULL){
            return 1;
        }
        else{
            l = LeafCount(bt->lChild);
            r = LeafCount(bt->rChild);
            return l+r;
        }
    }
}

//二叉树节点个数
int NodeCount(BTNode *bt){
    int l,r;
    if(bt == NULL){
        return 0;
    }
    else{
        l = NodeCount(bt->lChild);
        r = NodeCount(bt->rChild);
        return (l+r+1);
    }
}

//二叉树高度运算
int BTHeight(BTNode *bt){
    int l,r;
    if(bt == NULL){
        return 0;
    }
    else{
        char d = bt->data;
        //cout << d << endl;
        l = BTHeight(bt->lChild);
        //cout << "l:  " << l << endl;
        r = BTHeight(bt->rChild);
        //cout << "r:  " << r << endl;
        //cout << (l>r ? (l+1):(r+1)) << endl;
        return l > r ? (l+1):(r+1);
    }
}

//根据二叉树的括号表示法str建立二叉链
void CreateBTree(BTNode* &bt,char* str){
    BTNode* st[MaxSize];
    BTNode* p = NULL;
    bt = NULL;
    int k,top=-1,j=0;
    char ch = str[j];
    while(ch != ''){
        switch(ch){
            case '(':
                top++;
                st[top] = p;
                k = 1;
                break;
            case ')':
                top--;
                break;
            case ',':
                k = 2;
                break;
            default:
                p = new BTNode;
                //p = (BTNode *)malloc(sizeof(BTNode));
                p->data = ch;
                p->lChild = p->rChild = NULL;
                if(bt == NULL){
                    bt = p;
                }
                else{
                    switch(k){
                        case 1:
                            st[top]->lChild = p;
                            break;
                        case 2:
                            st[top]->rChild = p;
                            break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}

int main()
{
    BTNode *bt;
    CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");
    cout << "二叉树：";
    DispBTree(bt);
    int i = BTHeight(bt);
    int j = NodeCount(bt);
    int k = LeafCount(bt);

    //遍历
    cout << endl;
    cout << "先序遍历：";
    PreOrder(bt);
    cout << endl;
    cout << "中序遍历：";
    InOrder(bt);
    cout << endl;
    cout << "后序遍历：";
    LastOrder(bt);
    cout << endl;
    cout << "层次遍历：";
    LeverOrder(bt);

    return 0;
}