二叉树之C++实现

创建二叉树

//先序创建二叉树
void createBiTree(BiTree &T)
{
    char ch;
    cin >> ch;
    if (ch == '#')//以'#'代表空
    {
        T = NULL;
    }
    else
    {
        T = new BiTNode;
        T->data = ch;//将ch赋到结点数据域
        createBiTree(T->lchild);//递归创建左子树
        createBiTree(T->rchild);//递归创建右子树
    }
    
}

复制二叉树

//复制二叉树，将二叉树T复制给NewT
void copyTree(BiTree T, BiTree &NewT)
{
    if (T == NULL)
    {
        NewT = NULL;
    }
    else
    {
        NewT = new BiTNode;
        NewT->data = T->data;//数据域复制
        copyTree(T->lchild, NewT->lchild);//递归复制左子树
        copyTree(T->rchild, NewT->rchild);//递归复制右子树
        
    }
}

先序遍历

• 递归实现

//先序遍历二叉树
void preOrderTraverse(BiTree T)
{
    if (T)//T不是空树
    {
        cout << T->data<<"   ";
        preOrderTraverse(T->lchild);//递归先序遍历左子树
        preOrderTraverse(T->rchild);//递归先序遍历右子树
    }
}

• 非递归实现

//非递归先序遍历二叉树
void feiDiGuiPreOrderTraverse(BiTree T)
{
    LinkStack S;
    initStack(S);
    BiTree p = T,q;
    q = new BiTNode;
    while (p || !stackEmpty(S))
    {
        if (p)//p非空
        {
            cout << p->data << "   ";
            push(S, p);
            p = p->lchild;
        }
        else
        {
            pop(S, q);
            p = q->rchild;
        }
    }
}

中序遍历

• 递归实现

//中序遍历二叉树
void inOrderTraverse(BiTree T)
{
    if (T)//T不是空树
    {
        inOrderTraverse(T->lchild);//递归中序遍历左子树
        cout << T->data << "   ";
        inOrderTraverse(T->rchild);//递归中序遍历右子树
    }
}

• 非递归实现

//非递归中序遍历二叉树
void feiDiGuiInOrderTraverse(BiTree T)
{
    LinkStack S;
    initStack(S);
    BiTree q;
    q = new BiTNode;
    BiTree p = T;
    while (p || !stackEmpty(S))
    {
        if (p)//p不空
        {
            push(S, p);//p入栈
            p = p->lchild;
        }
        else
        {
            pop(S, q);
            cout << q->data << "   ";
            p = q->rchild;
        }
    }
}

后序遍历

• 递归实现

//后序遍历二叉树
void postOrderTraverse(BiTree T)
{
    if (T)//T不是空树
    {
        postOrderTraverse(T->lchild);//递归后序遍历左子树
        postOrderTraverse(T->rchild);//递归后序遍历右子树
        cout << T->data << "   ";
    }
}

• 非递归实现

//非递归后序遍历二叉树

void feiDiGuiPostOrderTraverse(BiTree T)
{
    LinkStack S;
    initStack(S);
    BiTree p = T,q;
    q = NULL;
    while (p || !stackEmpty(S))
    {
        if (p)
        {
            push(S,p);
            p = p->lchild;
        }
        else
        {
            p = getTop(S);
            if (q != p->rchild)
            {
                p = p->rchild;
                q = p;
            }
            else
            {
                pop(S, p);
                cout << p->data << "   ";
                pop(S, p);
                cout << p->data << "   ";
                p = p->rchild;
            }
        }
        
        
        /*
         if (p)//p非空
         {
         push(S, p);
         p = p->lchild;
         }
         else
         {//p空
         p = getTop(S);
         if (p != q)
         {
         q = p;
         p = p->rchild;
         }
         else
         {
         cout << p->data << "   ";
         pop(S, p);
         p = getTop(S);
         p = p->rchild;
         }
         }*/
    }
    
}

二叉树深度

//计算二叉树的深度
int depth(BiTree T)
{
    if (!T)
    {
        return 0;
    }
    else
    {
        int m = depth(T->lchild);
        int n = depth(T->rchild);
        return (m > n ? m : n) + 1;
    }
}

统计结点个数

//统计二叉树的结点的个数
int nodeCount(BiTree T)
{
    if (!T)
        return 0;
    else
        return nodeCount(T->lchild) + nodeCount(T->rchild) + 1;
}

统计度为1的结点个数

//统计二叉树中度为1的结点的个数
int duYiNodeCount(BiTree T)
{
    if (T)
    {
        int n = 0;
        if ( (T->lchild && !T->rchild) || (!T->lchild && T->rchild) )
        {
            n = 1;
        }
        return duYiNodeCount(T->lchild) + duYiNodeCount(T->rchild) + n;
    }
    return 0;
}

统计度为2的结点个数

//统计二叉树中度为2的结点的个数
int duErNodeCount(BiTree T)
{
    if (T)
    {
        int n = 0;
        if (T->lchild && T->rchild)
        {
            n = 1;
        }
        return duErNodeCount(T->lchild) + duErNodeCount(T->rchild) + n;
    }
    return 0;
}

统计叶子节点

//统计二叉树的叶结点的个数
int leafNodeCount(BiTree T)
{
    if (T)
    {
        if (!T->lchild && !T->rchild)
            return 1;
        return leafNodeCount(T->lchild) + leafNodeCount(T->rchild);
    }
    return 0;
}

交换左右孩子

//交换二叉树每个结点的左孩子和右孩子
void swapChild(BiTree &T)
{
    if (T)
    {
        swapChild(T->lchild);//交换左子树
        swapChild(T->rchild);//交换右子树
        //交换左右孩子
        BiTree p;
        p = T->lchild;
        T->lchild = T->rchild;
        T->rchild = p;
    }
}

注：上述非递归遍历使用栈结构

C实现代码

Java实现代码