二叉树的实现

二叉树的递归实现(链表)

常规遍历方式

实现了二叉树的生成以及三种遍历方式

#include <iostream>
#include <stdio.h>
using namespace std;
#define OK true;
#define ERROR false;

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

}BiTNode , *BiTree;

//构造树
bool CreatBiTree(BiTree &T){
    char ch;
    cin>>ch;
    if(ch == '#') T = NULL;
    else{
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T) return ERROR;
        T->data = ch;   // 生成根节点
        CreatBiTree(T->lchild); //生成左子树
        CreatBiTree(T->rchild); //生成右子树
    }
    return OK;
}

//前序遍历
void PreOrder(BiTree T){
    if(T){
       cout<<T->data<<' ';
       PreOrder(T->lchild);
       PreOrder(T->rchild);
    }

}

//中序遍历
void InOrder(BiTree T){
    if(T){
        InOrder(T->lchild);
        cout<<T->data<<' ';
        InOrder(T->rchild);
    }

}
//后序遍历
void PostOrder(BiTree T){
    if(T){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data<<' ';
    }

}

//层序遍历
queue<BiTree> q;
void level_order(BiTree t){
    q.push(t);
    while(!q.empty()){
        if(t->lchild){
            q.push(t->lchild);
        }
        if(t->rchild){
            q.push(t->rchild);
        }
        cout<<q.front()->data<<' ';
        q.pop();
        t = q.front();
    }
}

int main()
{
    BiTree T;
    CreatBiTree(T);
    PreOrder(T);
    cout<<endl;
    InOrder(T);
    cout<<endl;
    PostOrder(T);
}

已知后序、中序遍历，求层序遍历

#include<bits/stdc++.h>

using namespace std;

typedef struct BiNode{
    int data;
    BiNode *left , *right;
}BiNode , *BiTree;

void order(vector<int> post_v , vector<int> in_v , BiTree &tree){
    if(!in_v.size()) {
        tree = NULL;
        return;
    }
    vector<int>::iterator iter = find(in_v.begin() , in_v.end() , *(post_v.end() - 1));
    int position = iter - in_v.begin();

    tree = (BiTree)malloc(sizeof(BiNode));
    tree->data = *iter;

    vector<int> v1(post_v.begin() , post_v.begin() + position);
    vector<int> v2(in_v.begin() , in_v.begin() + position);
    vector<int> v3(post_v.begin() + position , post_v.end() - 1);
    vector<int> v4(in_v.begin() + position + 1 , in_v.end());
    order(v1 , v2 , tree->left);
    order(v3 , v4 , tree->right);
}

queue<BiTree> q;
void level_order(BiTree t){
    q.push(t);
    while(!q.empty()){
        if(t->left){
            q.push(t->left);
        }
        if(t->right){
            q.push(t->right);
        }
        cout<<q.front()->data;
        q.pop();
        if(!q.empty()){
            cout<<' ';
        }
        t = q.front();
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    vector<int> post_v , in_v;
    for(int i = 0 ; i<n ; ++i){
        int a;
        cin>>a;
        post_v.push_back(a);
    }
    for(int i = 0 ; i<n ; ++i){
        int a;
        cin>>a;
        in_v.push_back(a);
    }
    BiTree tree;
    order(post_v , in_v , tree);
    level_order(tree);
}

二叉树的非递归算法(链表)

实现了二叉树的三种遍历方式

#include <iostream>
#include <stdio.h>
using namespace std;
#define OK true;
#define ERROR false;

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

}BiTNode , *BiTree;

typedef struct Stack{
    BiTree data;
    Stack *Next;
}Stack , *StackList;

typedef struct{
    StackList base;
    StackList top;
}ListStack;

bool InitStack(ListStack &s){
    s.base = (StackList)malloc(sizeof(Stack));
    if(!s.base) return ERROR;
    s.top = s.base;
    s.top->Next = NULL;
    return OK;
}

bool push(ListStack &s , BiTree T){
    StackList p = (StackList)malloc(sizeof(Stack));
    if(!p) return ERROR;
    p->data = T;
    p->Next = s.top;
    s.top = p;
    return OK;
}

bool pop(ListStack &s){
    if(s.top == s.base) return ERROR;
    StackList p = s.top;
    s.top = p->Next;
    free(p);
    return OK;
}

BiTree getTop(ListStack &s){
    return s.top->data;
}

bool isEmpty(ListStack &s){
    if(s.base == s.top) return true;
    else return false;
}

//构造树
bool CreatBiTree(BiTree &T){
    char ch;
    cin>>ch;
    if(ch == '#') T = NULL;
    else{
        T = (BiTree)malloc(sizeof(BiTNode));
        if(!T) return ERROR;
        T->data = ch;   // 生成根节点
        CreatBiTree(T->lchild); //生成左子树
        CreatBiTree(T->rchild); //生成右子树
    }
    return OK;
}

void PreOrder(BiTree T){
    ListStack s;
    InitStack(s);
    while(T || !isEmpty(s)){
        while(T){
            cout<<T->data<<' ';
            push(s , T);
            T = T->lchild;
        }
        if(!isEmpty(s)){
            T = getTop(s);
            pop(s);
            T = T->rchild;
        }
    }
    cout<<endl;
}

void InOrder(BiTree T){
    ListStack s;
    InitStack(s);
    while(T || !isEmpty(s)){
        while(T){
            push(s , T);
            T = T->lchild;
        }
        if(!isEmpty(s)){
            T = getTop(s);
            pop(s);
            cout<<T->data<<' ';
            T = T->rchild;
        }
    }
    cout<<endl;
}

void PostOrder(BiTree T){
    ListStack s;
    InitStack(s);
    int flag = 1;   // 用来判断是否进入右子树
    BiTree p;
    if(T){
        do{
            while(T){
                push(s , T);
                T = T->lchild;
            }
            flag = 1;
            p = NULL;
            while(!isEmpty(s) && flag == 1){
                T = getTop(s);  // 因为经过第一个while循环，T = NULL,所以要把他变回来
                if(T->rchild == p){
                    cout<<T->data<<' ';
                    p = T;    //用于判断此节点的右孩子是否已经被访问，或者是没有右孩子
                    pop(s);
                }
                else {
                    T = T->rchild;
                    flag = 0;
                }
            }

        }while(!isEmpty(s));
    }
    cout<<endl;
}

int main()
{
    BiTree T;
    CreatBiTree(T);
    PreOrder(T);
    InOrder(T);
    PostOrder(T);
}

线索二叉树中序遍历的实现

线索二叉树的初始化

与普通二叉树相比，多了一个指示域：LTag和RTag，如果值是Link，那么有左孩子或右孩子，如果是Thread，那么有前驱或后继。

#include <iostream>
#include <stdio.h>
using namespace std;
#define OK true;
#define ERROR false;

typedef enum PointerTag{  // 声明PointTag为枚举类型
    Link,
    Thread
};

typedef struct BiThrNode{
    char data;
    BiThrNode *lchild , *rchild;
    PointerTag LTag , RTag;
}BiThrNode , *BiThrTree;


bool CreatBiTree(BiThrTree &T){
    char ch;
    cin>>ch;
    if(ch == '#') T = NULL;
    else{
        T = (BiThrTree)malloc(sizeof(BiThrNode));
        if(!T) return ERROR;
        T->data = ch;   // 生成根节点
        T->LTag = Link;
        T->RTag = Link;
        CreatBiTree(T->lchild); //生成左子树
        CreatBiTree(T->rchild); //生成右子树
    }
    return OK;
}

遍历

在线索树上遍历，只需找到要遍历的第一个节点，然后依次按照三种遍历方式的规定找后继就可以了。要遍历线索树，就要把普通的二叉树线索化，就是按照规定把空指针改为前驱或后继，所以三种遍历方式的线索化操作是不同的。

中序遍历

BiThrTree pre;
//中序遍历线索化
void InThreading(BiThrTree p){
    if(p){
        InThreading(p->lchild);  // 左子树进行线索化

        //基本操作
        if(!p->lchild) {  // 左子树为空
            p->LTag = Thread; // 修改左指示为前驱
            p->lchild = pre;  // 修改左孩子为前驱
        }
        if(!pre->rchild){
            pre->RTag = Thread;
            pre->rchild = p;
        }
        pre = p;

        InThreading(p->rchild); // 右子树线索化
    }
}


bool InOrderThreading(BiThrTree &Thrt , BiThrTree T){
    //中序遍历T, 将其线索化，Thrt指向头结点
    Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt) return ERROR;
    Thrt->LTag = Link;  //建立头结点
    Thrt->RTag = Thread;
    Thrt->rchild = Thrt;
    if(!T) Thrt->lchild = Thrt; // 如果是空树
    else {
        Thrt->lchild = T;
        pre = Thrt;  //pre 为p 的前驱
        InThreading(T); // 线索化
        pre->rchild = Thrt;
        pre->RTag = Thread;
        Thrt->rchild = pre;
    }
    return OK;
}

// 非递归
void InOrderPrint(BiThrTree Thrt){
    BiThrTree p = Thrt->lchild; // Thrt 是头结点，没有值
    while(p != Thrt){ // 如果是空树或遍历完毕时， p== Thrt
        while(p->LTag == Link) p = p->lchild;  // 先找到遍历每个子树的第一个节点
        cout<<p->data;
        while(p->RTag == Thread && p->rchild != Thrt){ // 如果有后继，并且不是最后一个节点
            p = p->rchild;  // 指向他的后继
            cout<<p->data;  //输出后继
        }
        p = p->rchild;  // 没有后继时，指向他的右孩子，然后继续执行到右子树的要遍历的第一个节点
    }
    cout<<endl;
}

int main()
{
    BiThrTree T , Thrt;
    CreatBiTree(T);
    InOrderThreading(Thrt , T);
    InOrderPrint(Thrt);
}

前序遍历

BiThrTree pre;

void PreThreading(BiThrTree p){
    if(p){
            
        if(!p->lchild){
            p->lchild = pre;
            p->LTag = Thread;
        }
        if(!pre->rchild){
            pre->rchild = p;
            pre->RTag = Thread;
        }
        pre = p;
    
        if(p->LTag == Link){ //这个判断条件必须加，不然会死循环
            PreThreading(p->lchild);
        }
        if(p->RTag == Link){
            PreThreading(p->rchild);
        }

    }
}

// 与中序遍历相同
bool PreOrderThreading(BiThrTree &Thrt , BiThrTree T){
    //中序遍历T, 将其线索化，Thrt指向头结点
    Thrt = (BiThrTree)malloc(sizeof(BiThrNode));
    if(!Thrt) return ERROR;
    Thrt->LTag = Link;  //建立头结点
    Thrt->RTag = Thread;
    Thrt->rchild = Thrt;
    if(!T) Thrt->lchild = Thrt; // 如果是空树
    else {
        Thrt->lchild = T;
        pre = Thrt;  //pre 为p 的前驱
        PreThreading(T); // 线索化
        pre->rchild = Thrt;
        pre->RTag = Thread;
        Thrt->rchild = pre;
    }
    return OK;
}

void PreOrderprint(BiThrTree T){
    BiThrTree p = T->lchild;
    while(p != T){
        cout<<p->data;
        if(p->LTag == Link){
            p = p->lchild;
        }
        else {
            p = p->rchild;  
        }
    }
}


int main()
{
    BiThrTree T , Thrt;
    CreatBiTree(T);
    PreOrderThreading(Thrt , T);
    PreOrderprint(Thrt);
}

后序遍历