顺序二叉树

常量定义和声明

1
2
3
#define  MAX_TREE_SIZE 100     // 二叉树的最大结点数  
typedef char TElemType;
typedef  TElemType   SqBiTree  [MAX_TREE_SIZE+1];    //假设根结点数据元素存储在数组1下标。

构建

1
2
3
4
5
6
7
8
9
10
Status CreateBiTree(SqBiTree & T,int n)
{
    TElemType x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        T[i]=x;
    }
    return OK;
}

先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void PreOrderTraverse(SqBiTree T,int num,int n)
{
    if(n==0)
    {
        cout<<"NULL";
        return ;
    }
    if(num>n || T[num]=='#')
        return ;
    else
    {
        cout<<T[num];
        PreOrderTraverse(T,2*num,n);
        PreOrderTraverse(T,2*num+1,n);
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InOrderTraverse(SqBiTree T,int root_num,int n)
{
    if(n==0)
    {
        cout<<"NULL";
        return ;
    }
    if(root_num>n || T[root_num]=='#')
            return ;
    else
    {
        InOrderTraverse(T,2*root_num,n);
        cout<<T[root_num];
        InOrderTraverse(T,2*root_num+1,n);
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void PostOrderTraverse(SqBiTree T,int root_num,int n)
{
    if(n==0)
    {
        cout<<"NULL";
        return ;
    }
    if(root_num>n || T[root_num]=='#')
        return ;
    else
    {
        PostOrderTraverse(T,2*root_num,n);
        PostOrderTraverse(T,2*root_num+1,n);
        cout<<T[root_num];
    }
    return ;
}

二叉链表

声明

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

构建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InitBiTree(BiTree &T)
{
    T = new BiTNode;
    T->lchild = T->rchild = NULL;
}
Status CreateBiTree(BiTree & T)
{
    char ch;
    cin>>ch;
    if(ch=='#') T=NULL;
    else
    {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

先序遍历

1
2
3
4
5
6
7
8
9
void PreOrderTraverse(BiTree T)
{
    if(T)
    {
        cout<<T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
void InOrderTraverse(BiTree T)
{
    if(T)
    {
        InOrderTraverse(T->lchild);
        cout<<T->data;
        InOrderTraverse(T->rchild);
    }
}

后序遍历

1
2
3
4
5
6
7
8
9
void PostOrderTraverse(BiTree T)
{
    if(T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout<<T->data;
    }
}

中序遍历输出叶子节点并统计其个数

1
2
3
4
5
6
7
8
9
10
11
12
13
void InOrderTraverse(BiTree T, int & n)
{
    if(T)
    {
        InOrderTraverse(T->lchild, n);
        if(T->lchild == NULL && T->rchild == NULL)
        {
            cout<<T->data;
            n++;
        }
        InOrderTraverse(T->rchild, n);
    }
}