机试常用算法和题型-树专题

静态创建新结点、构造二叉树实现前序中序遍历还原

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

//复原二叉树，。想出算法，

//静态版，递归的边界条件和递归式由str1的s1,e1,str2的s2,e2联合确定，缩小开头和结尾划分子问题

struct Node{
    char data;
    Node *rchild;
    Node *lchild;
}Tree[50];

//静态如何创建新节点，就是loc游标移动
int loc;
Node *create(){
    Tree[loc].lchild=Tree[loc].rchild=NULL;
    //返回的是指针
    return &Tree[loc++];
}
string str1,str2;
//在函数当中就要用到，提前定义
Node *build(int s1,int e1,int s2,int e2){
    //直接每个都要创建新节点的！！我傻了
    Node *ret=create();
    ret->data=str1[s1];
    int rootIdx=str2.find(str1[s1]);
    //找到根节点在str2中的位置
    //递归边界+递归式
    if(rootIdx!=s2){
        //左子树不为空
        ret->lchild=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
        //边界的确定最难了
    }
    if(rootIdx!=e2){
        ret->rchild=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
    }
    return ret;
}
//动态创建的办法，以及带出口边界的写法
node * create(int preL,int preR,int inL,int inR)
{
    if(preL>preR)
        return NULL;
    node * p=new node;
    p->data=pre[preL];
    int k;
    for(k=inL;k<inR;++k)
        if(in[k]==pre[preL])
            break;
    int numleft=k-inL;
    p->lchild=create(preL+1,preL+numleft,inL,k-1);
    p->rchild=create(preL+numleft+1,preR,k+1,inR);
    return p;
}


void postOrder(Node *r){
    //遍历出口
    if(r==NULL){
        return;
    }
    postOrder(r->lchild);
    postOrder(r->rchild);
    printf("%c",r->data);
}
int main()
{
    while(cin>>str1>>str2){
        Node *T;
        int e1=str1.size()-1;
        int e2=str2.size()-1;
        T=build(0,e1,0,e2);
        postOrder(T);
        printf("\n");
    }
    return 0;
}

二叉排序树查找、插入、构造科学方法

7
8 6 5 7 10 8 11

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

struct node{
    int data;
    node *rchild;
    node *lchild;
};

//创建新结点还是要写一个，这样的话，才可以创建空结点，类似于链表知道到了链表尾部
node *newNode(int x){
    node *Node=new node;
    Node->data=x;
    Node->rchild=Node->lchild=NULL;
    return Node;
}

//如何构造二叉排序树
//有无到有，其实就是n次插入,而插入其实是查找的更进一步，找到空的位置！！

void insL(node *&root,int x)
{
    //次数一定要加上引用，因为root结构发生了变化
    if(root==NULL) {
            //定义出口，空结点的位置创建新点
        root=newNode(x);
        return;
    }
    //原因在这里，相等时也可以插
 /*   if(x==root->data){
        return;
        //查找结点，如果发现这个结点被插入，就不用二次插入
    }else if(x<root->data){
        insL(root->lchild,x);
    }else {
        insL(root->rchild,x);
    }*/
    if(x<root->data) insL(root->lchild,x);
    else insL(root->rchild,x);
}
//数组参数如何处理



//换成高级写法
void preOrder(node *T,vector<int> &vi){
    if(T==NULL) return;
    vi.push_back(T->data);
    preOrder(T->lchild,vi);
    preOrder(T->rchild,vi);
}

void postOrder(node *T,vector<int> &vi){
    if(T==NULL) return;

    postOrder(T->lchild,vi);
    postOrder(T->rchild,vi);
    vi.push_back(T->data);
}

void mirOrderPre(node *T,vector<int> &vi){
    if(T==NULL) return;
    vi.push_back(T->data);

    mirOrderPre(T->rchild,vi);
    mirOrderPre(T->lchild,vi);
}

void mirOrderPost(node *T,vector<int> &vi){
    if(T==NULL) return;

    mirOrderPost(T->rchild,vi);
    mirOrderPost(T->lchild,vi);
    vi.push_back(T->data);
}


vector<int> origin,pre,preM,post,postM;
int main()
{

    int n;
    while(cin>>n){

        node *T=NULL;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            origin.push_back(x);
            //循环插入即可
            insL(T,x);
        }

        preOrder(T,pre);
        postOrder(T,post);
        mirOrderPre(T,preM);
        mirOrderPost(T,postM);
        //容器vector可以直接相等！！！
        if(origin==pre){
            cout<<"YES"<<endl;
            for(int i=0;i<post.size();i++){
                cout<<post[i]<<" ";
            }
        }else if(origin==preM){
             cout<<"YES"<<endl;
            for(int i=0;i<postM.size();i++){
                cout<<postM[i]<<" ";
            }
        }else{
        cout<<"NO"<<endl;
        }
        cout<<endl;
    }
    return 0;
}

二叉排序树建立，非递归遍历方法

/*第三题：输入一个字符串，建立一个二叉排序树，并中序遍历输出；*/
 
/*这里采用了两种遍历，此处是非递归。下面注释的是递归*/
/*测试数据: poiuyt    输出数据;i o p t u y   
  测试数据: 621345     输出数据: 1 2 3 4 5 6*/
/*程序：*************************爱X的味道 07级华中农业大学计算机系*****************************/
 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 50
typedef struct Node
{
    char data;
    struct Node *Lchild;
    struct Node *Rchild;
}Node,*BiTree;
 
typedef struct 
{
    BiTree elem[MAX];
    int top;
}Stack;  
void InitStack(Stack *s)
{
    s->top=-1;
}
int Push(Stack *s,BiTree *T)
{
    if(s->top>MAX-1) return 0;
    s->top++;
    s->elem[s->top]=(*T);
    return 1;
}
int Pop(Stack *s,BiTree *T)
{
    if(s->top<-1) return 0;
    *T=s->elem[s->top];   
    s->top--;
    return 1;
}
int IsEmpty(Stack s)
{
    if(-1==s.top)
        return 1;
    else
        return 0;
}
void InsertSortTree(BiTree *tree, char key)
{
    BiTree T;
    if(*tree == NULL)
    {
        T=(BiTree)malloc(sizeof(Node));
        T->data=key;
        T->Lchild=NULL;
        T->Rchild=NULL;
        *tree=T;
    }
    else
        if((*tree)->data>key)
            InsertSortTree(&((*tree)->Lchild),key);
        else
            if((*tree)->data<key)
                InsertSortTree(&((*tree)->Rchild),key);
}
void CreateSortTree(BiTree  *tree,char *str )
{
    *tree=NULL;
    int i=0;
    while(str[i]!='\0')
    {
        InsertSortTree(&(*tree),str[i]);
        i++;
    }
}
 
void InOrdTree(BiTree T)    
{
    Stack s;
    BiTree p=T;
    InitStack(&s);
    while(p!=NULL || !IsEmpty(s))
    {
        if(p!=NULL)
        {
            Push(&s,&p);
            p=p->Lchild;
        }
        else
        {
            Pop(&s,&p);
            printf(" %c ",p->data);
            p=p->Rchild;
        }
    }
    printf("\n\n");
}
int main()
{
    char str[100]="\0";
    BiTree tree;
    printf("请输入一个字符串:\n\n");
    gets(str);
    CreateSortTree(&tree,str);
    printf("中序遍历的结果是:\n\n");
    InOrdTree(tree);
    printf("\n\n");
    return 0;
}
 
/*
/*输入一个字符串，建立一个二叉排序树，并中序遍历输出；
要考虑字符串，好难

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

typedef struct Node{
    int data;
    Node *lchild,*rchild;
}Node,*BiTree;

Node * creatNode(int data){
    Node *T=(Node*)malloc(sizeof(Node));
    if(T==NULL){
        exit(0);
    }
    T->data=data;
    T->lchild=NULL;
    T->rchild=NULL;
    return T;
}

//只有返回值时树节点才node *好不好
int InsertNode(BiTree &T,int key){
    if(T==NULL){
        T=creatNode(key);
        return 1;
    }

    //应当要检查要插入的是否已经存在的，如果查找失败直接插入，则p指向遍历最后一个节点
    //主要是根据key找位置
    else if(key==T->data){
        return 0;
    }else if(key<T->data){
    return InsertNode(T->lchild,key);
    }else return InsertNode(T->rchild,key);
}

void inOrder(Node *T){
    if(T!=NULL){
        inOrder(T->lchild);
        printf("%c ",T->data);
        inOrder(T->rchild);
    }

}

int main(){
    Node *T=NULL;
    string str;
    cin>>str;
    for(int i=0;i<str.size();i++){
            //我错了，strcpy(c,s.c_str()); 用在一整个串
        char c=str[i];
        InsertNode(T,c);

    }
    //这个怎么能在循环内部呢.想看一下传值里面是怎么变化的！！
    //刚才使用返回return，每次都返回当前节点~~
    inOrder(T);
}
*/

无冗余字符串数组加建立二叉排序树

#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct BiNode
{
    char *s;
    struct BiNode *lchild;
    struct BiNode *rchild;
}BiNode,*BiTree;

void PreOrder(BiTree T)
{
    if(T)
    {
        printf("%s\n",T->s);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
int main()
{
    char **str,e;
    int row=1,col=1;
    int tag,i,len;
    BiTree T,r,t;
    str=(char **)malloc(row*sizeof(char *));
    str[col-1]=(char *)malloc(col*sizeof(char));
    tag=1;
    while((e=getchar())!='\n')
    {
        if(e==' ')
        {
            str[row-1][col-1]='\0';
            tag=0;
            continue;
        }
        else
        {
            if(tag==0)
            {
                row++;
                col=2;
                str=(char **)realloc(str,row*sizeof(char *));
                str[row-1]=(char *)malloc(col*sizeof(char));
                str[row-1][col-2]=e;
                tag=1;
            }
            else
            {
                col++;
                str[row-1]=(char *)realloc(str[row-1],col*sizeof(char));
                str[row-1][col-2]=e;
            }
        }
    }
    str[row-1][col-1]='\0';
    for(i=0;i<row;i++)
        printf("%s\n",str[i]);
    printf("\n");

    len=strlen(str[0]);
    T=(BiTree)malloc(sizeof(BiNode));
    T->s=(char *)malloc((len+1)*sizeof(char));
    strcpy(T->s,str[0]);
    T->lchild=T->rchild=NULL;
    t=T;
    for(i=1;i<row;i++)
    {
        len=strlen(str[i]);
        r=(BiTree)malloc(sizeof(BiNode));
        r->s=(char *)malloc((len+1)*sizeof(char));
        r->lchild=NULL;
        r->rchild=NULL;
        strcpy(r->s,str[i]);
        while(t)
        {
            if(strcmp(t->s,r->s)>0)
            {
                if(t->lchild)
                    t=t->lchild;
                else
                {
                    t->lchild=r;
                    break;
                }
            }
            else
            {
                if(t->rchild)
                    t=t->rchild;
                else
                {
                    t->rchild=r;
                    break;
                }
            }
        }
        t=T;
    }
    PreOrder(T);
    return 0;
}

如何创建树链表，进行逆中序遍历

/*输入一个数列以0结尾，建立二叉遍历数，并对其进行逆中序遍历，释放空间*/
/*(2)输入一个数列以0位结束标志，建立二叉遍历树，并对其进行逆中序遍历，释放空间。*/
/*示例树为 :             1    
                        /   \
                       2      3
                        \      \
                         4       5
                       /  \       \
                      6    7       8       每次输入一个数，按一次回车
   输入的序列为 : 1 2 0 4 6 0 0 7 0 0 3 0 5 0 8 0 0  
   输出的结果应为: 8 5 3 1 7 4 6 2           */
————————————————

#include<stdio.h>
#include<stdlib.h>
typedef struct BiTNode{//二叉树数据结构定义；
    int data;
    BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree CreateTree(){//创建二叉树；
    int value;
    BiTree t;
    scanf("%d",&value);
    if(value==0)return NULL;
    else{
         t=(BiTree)malloc(sizeof(BiTNode));
         t->data=value;
         t->lchild=CreateTree();
         t->rchild=CreateTree();
         return t;
    }
}

void ReInOrder(BiTree t){//逆中序遍历二叉树；
     if(t!=NULL){
          ReInOrder(t->rchild);
          printf("%d ",t->data);
          ReInOrder(t->lchild);
          free(t);
     }
}

int main(){
    BiTree t;
    printf("请按序输入二叉树结点的值(以0为标志结束)：\n");
    t=CreateTree();
    printf("逆中序遍历二叉树：\n");
    ReInOrder(t);
    system("pause");
}

//另一种写法
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *lchild,*rchild;
};

//两种方式，引用或者node *返回！！！
void insertT(node *&root){
    int x;
    cin>>x;
    if(x==0) return;
    if(root==NULL){
        //应当创建新结点
        root=new node;
        root->data=x;
        root->lchild=NULL;
        root->rchild=NULL;
    }
    //每个结点应该都是空的，可以自己往下接s
    insertT(root->lchild);
    insertT(root->rchild);

}

void inOrdedr(node *root){
    if(root!=NULL){
        inOrdedr(root->rchild);
        cout<<root->data<<" ";
        inOrdedr(root->lchild);
    }

}


int main()
{

    node *T=NULL;
    insertT(T);
    inOrdedr(T);

    return 0;
}

后序加中序还原加层序遍历

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

//后序加中序遍历推出

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct node{
    int data;
    node *lchild;
    node *rchild;
};

int a[40],b[40];

node *build(int s1,int e1,int s2,int e2){
    //终于知道了！！没有创建新结点，咋个有空间放数据和指针
    if(s1>e1) return NULL;
    //启示！！写法要配套，不然会出现没有NULL结点无法结束的情况
    node *newNode=new node;

    //后序遍历最后一个结点为根结点
    newNode->data=a[e1];

    int i;
    for(i=s2;i<=e2;i++){
        if(b[i]==a[e1]) break;
    }
    int pos=i;

    int leftNum=pos-s2;

    //左子树非空，构建左子树
    newNode->lchild=build(s1,s1+leftNum-1,s2,pos-1);
    newNode->rchild=build(s1+leftNum,e1-1,pos+1,e2);

    return newNode;
}

void preOrder(node *T){
    if(T==NULL) return;
    cout<<T->data<<" ";
    preOrder(T->lchild);
    preOrder(T->rchild);
}

void floor(node *T){
    queue<node*> q;
    //注意队列当中存放的是地址
    q.push(T);
    //while条件就出口
    while(!q.empty()){
        //取队头，出队，访问
            node *now=q.front();
            q.pop();
            cout<<now->data<<" ";
            if(now->lchild!=NULL) q.push(now->lchild);
            if(now->rchild!=NULL) q.push(now->rchild);
    }
}
int main()
{
    int n;
  while(cin>>n){
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    node *T;
    T=build(0,n-1,0,n-1);
    floor(T);
    cout<<endl;
  }
}