二叉树的各种操作

第一步，先定义链表的链式结构：

typedef struct BiTNode {
    char data ;
    struct BiTNode *lchild , *rchild;
}BiTNode, *BiTree;

第二部，再定义栈的链式结构结构，和栈的基本操作：

typedef struct Snode{
    BiTree  data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , BiTree e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , BiTree &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
BiTree GetTop(LinkStack s){
    return s->data;
}

第三步，用树的先序序列创建二叉树：

void CreateBiTree(BiTree &T){
    char ch;
    cin >> ch;
    if(ch == '#') {
        T = NULL;
    }
    else {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

第四部：中序遍历：

非递归的算法，就是一种用递归的思想，来代替较为浪费时间的递归，本质还是递归
仔细看看课本算法5.2 下面的图，好好理解下，先序和中序都不难，这里就不给大家细讲

void InOrderTraverse (BiTree T) {
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s,p);
            p = p ->lchild;
        }
        else {
            Pop(s,q);

            cout << q->data;
            p = q->rchild;
        }
    }  
}

第五步，先序遍历：

void PriorityTraverse(BiTree T){
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s, p);
            cout << p->data;
            p = p ->lchild;

        }
        else {
            Pop(s,q);
            p = q->rchild;
        }
    }
}

第六步，难点：

二叉树的后序遍历：
我的思路是：
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
所以代码如下：

void RearTraverse(BiTree T) {
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
    BiTree q1 = new BiTNode;
    Push(s, p);
    while (!Empty(s)){
        p = GetTop(s);
        if ((p->lchild == NULL&&p->rchild == NULL) ||
                    ((q == p->lchild || q == p->rchild) && q != NULL))
                {
                    cout << p->data;
                    Pop(s, q1);
                    q = p;
                }
        else
                {
                    if (p->rchild != NULL)
                        Push(s,p->rchild);
                    if (p->lchild != NULL)
                        Push(s, p->lchild);
                }
    }
}

当然了，还有一种比较常见的思路，在网上可以找到大家可以看看：

第七步：二叉树的深度；

递归算法，很好理解

int Depth (BiTree T){
    int n=0,m=0;
    if(T == NULL) return 0;
    else{
        m = Depth(T->lchild);
        n = Depth(T->rchild);
    }
    if(m > n)  return m+1;
    else return n+1;
}

第八步：求节点的总度数：

int NodeCount(BiTree T) {
    if(T == NULL) return 0;
    else return NodeCount(T->lchild) + NodeCount(T->rchild)+1;
}

第九步： 求一度节点度数

int one(BiTree bt)
{
    if(bt)
    {
        int ret=0;
        if(bt->lchild)
        {
            ret++;
        }
        if(bt->rchild)
        {
            ret++;
        }

        if(ret==1)
            return one(bt->lchild) + one(bt->rchild) + ret;
        else
            return one(bt->lchild) + one(bt->rchild);
    }
    else
        return 0;
}

第十步：完工main（）函数：

int main()
{
    BiTree T = new BiTNode;
    CreateBiTree(T);
    cout << "请输入操作序号："<<"\n";
    cout << "输入1,先序遍历"<<"\n";
    cout << "输入2，后序遍历" << "\n";
    cout << "输入3，中序遍历"  << "\n";
    cout << "输入4，求树高" <<"\n";
    cout << "输入5，输出，度为1，2，3的个数" << "\n";
    int n ;
    int count = NodeCount(T);
    int on = one(T);
    while(cin>>n && n){
        switch (n) {
            case 1:
                PriorityTraverse(T);
                cout << "\n";
                break;
            case 2:
                RearTraverse(T);
                cout << "\n";
                break;
            case 3:
                InOrderTraverse(T);
                cout << "\n";
                break;
            case 4:
                cout << Depth(T) <<"\n";
                break;
            case 5:
                cout <<(count-on+1)/2-1<<" "<< on<<" " << (count-on+1)/2<<endl;
            default:
                break;
        }
    }
     //
//    PriorityTraverse( T);

//    P(T);
}

//abc##de#g##f###

完整代码：

//
//  main.cpp
//  数据结构实验五
//
//  Created by 宋玉良 on 2020/11/28.
//

#include<bits/stdc++.h>
using namespace std ;
typedef struct BiTNode {
    char data ;
    struct BiTNode *lchild , *rchild;
}BiTNode, *BiTree;

typedef struct Node{
    BiTree btnode;
    bool isfirst;
}Node , *node;

typedef struct Snode{
    BiTree  data;
    struct Snode *next;
}Snode , *LinkStack;
//初始化
bool InitStack(LinkStack &s){
    s = NULL;
    return true;
}
//判断是否为空
bool Empty(LinkStack s){
    if(s == NULL) return true;
    return false;
}
//入栈
bool Push(LinkStack &s , BiTree e){
    LinkStack p = new Snode;
    p -> data = e;
    p -> next = s;
    s = p;
    return true;
}
//出栈
bool Pop(LinkStack &s , BiTree &e){
    if(Empty(s)) return false;
    e = s->data;
    LinkStack p = s;
    s = s->next;
    delete p;
    return true;
}
//取栈顶元素
BiTree GetTop(LinkStack s){
    return s->data;
}
LinkStack s,s1,s2;
void InOrderTraverse (BiTree T) {
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s,p);
            p = p ->lchild;
        }
        else {
            Pop(s,q);

            cout << q->data;
            p = q->rchild;
        }
    }

}
void CreateBiTree(BiTree &T){
    char ch;
    cin >> ch;
    if(ch == '#') {
        T = NULL;
    }
    else {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

void PriorityTraverse(BiTree T){
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
//    BiTree q1 = new BiTNode;
    while(p || !Empty(s)){
        if(p) {
            Push(s, p);
            cout << p->data;
            p = p ->lchild;

        }
        else {
            Pop(s,q);
            p = q->rchild;
        }
    }
}
void RearTraverse(BiTree T) {
    InitStack(s);
    BiTree p = new BiTNode;
    p = T;
    BiTree q = new BiTNode;
    BiTree q1 = new BiTNode;
    Push(s, p);
    while (!Empty(s)){
        p = GetTop(s);
        if ((p->lchild == NULL&&p->rchild == NULL) ||
                    ((q == p->lchild || q == p->rchild) && q != NULL))
                {
                    cout << p->data;
                    Pop(s, q1);
                    q = p;
                }
        else
                {
                    if (p->rchild != NULL)
                        Push(s,p->rchild);
                    if (p->lchild != NULL)
                        Push(s, p->lchild);
                }
    }
}

int NodeCount(BiTree T) {
    if(T == NULL) return 0;
    else return NodeCount(T->lchild) + NodeCount(T->rchild)+1;
}

int Depth (BiTree T){
    int n=0,m=0;
    if(T == NULL) return 0;
    else{
        m = Depth(T->lchild);
        n = Depth(T->rchild);
    }
    if(m > n)  return m+1;
    else return n+1;
}

int one(BiTree bt)
{
    if(bt)
    {
        int ret=0;
        if(bt->lchild)
        {
            ret++;
        }
        if(bt->rchild)
        {
            ret++;
        }

        if(ret==1)
            return one(bt->lchild) + one(bt->rchild) + ret;
        else
            return one(bt->lchild) + one(bt->rchild);
    }
    else
        return 0;
}


int main()
{
    BiTree T = new BiTNode;
    cout << "请输入您要创建二叉树的先序序列（空指针用#代替）"<< endl;
    CreateBiTree(T);
    cout << "请输入操作序号："<<"\n";
    cout << "输入1,先序遍历"<<"\n";
    cout << "输入2，后序遍历" << "\n";
    cout << "输入3，中序遍历"  << "\n";
    cout << "输入4，求树高" <<"\n";
    cout << "输入5，输出，度为0，1，2的个数" << "\n";
    int n ;
    int count = NodeCount(T);
    int on = one(T);
    while(cin>>n && n){
        switch (n) {
            case 1:
                PriorityTraverse(T);
                cout << "\n";
                break;
            case 2:
                RearTraverse(T);
                cout << "\n";
                break;
            case 3:
                InOrderTraverse(T);
                cout << "\n";
                break;
            case 4:
                cout << Depth(T) <<"\n";
                break;
            case 5:
                cout <<(count-on+1)/2<<" "<< on<<" " << (count-on+1)/2-1<<endl;
            default:
                break;
        }
    }
     //
//    PriorityTraverse( T);

//    P(T);
}

//输入样例：abc##de#g##f###
//按一棵树的先序序列来输入，空指针用#代替