数据结构题目：树

题目：二叉排序树的构建与遍历

image

c++:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

typedef char keytype;

typedef struct{                 //keyÃèÊö 
    keytype key[105];         
}Retype;

typedef struct Bsnode{          //¶þ²æÊ÷ÅÅÐò½Úµã 
    Retype data;
    struct Bsnode *Lchild, *Rchild; 
} BSN, *BSP;  
              
typedef struct node{            //Õ»½ÚµãÀàÐÍ 
    BSP q;                     //´æ´¢Ò»¸öÕ»ÔªËØ 
    struct node *next;          //ºó¼ÌÖ¸Õë 
}snode,*slink;     

int Emptystack(slink top){      //ÅжÏÕ»ÊÇ·ñΪ¿Õ 
    if(top==NULL)
        return 1;
    else
        return 0;
} 

void Push(slink *top,BSP qi){       //½øÕ» 
    slink p;
    p=(slink)malloc(sizeof(snode));
    p->q=qi;
    p->next=*top;
    *top=p;
}

int Pop(slink *top,BSP *qi){                //³öÕ» 
    slink p;
    if(Emptystack(*top))
        return -1;
    else
    {
        p=*top;
        *top=(*top)->next;
        *qi=p->q;
        free(p);
        return 0;
    }
}
              
/*void Clearstack(slink *top){              //ÖÿÕÕ» 
    slink p;
    while(*top!=NULL){
        p=(*top)->next;
        Pop(top,qi);                    
        *top=p;
    }
    *top=NULL;
}*/

              
BSP BSTinsert(BSP T, BSP S)             //¶þ²æÅÅÐòÊ÷ÖÖ½ÚµãµÄ²åÈ루µÝ¹éËã·¨£© 
{ 
    if  (T == NULL) return S; 
    if (!strcmp(S->data.key,T->data.key)) {         
            free(S); return T;  
    }
    if (strcmp(S->data.key,T->data.key)<0) 
        T->Lchild = BSTinsert(T->Lchild, S);  
    else  T->Rchild = BSTinsert(T->Rchild, S); 
    return T;
} 

void Inorder(BSP T){                            //ÖÐÐò±éÀú£¨·ÇµÝ¹éËã·¨£© 
    slink top=(slink)malloc(sizeof(snode));
    top=NULL;
    
    BSP p = T,qi=NULL;
    while (1) {
        while (p) {
            Push(&top, p); 
            p = p->Lchild;
        }
        if (Emptystack(top)) 
            break;
        Pop(&top,&qi);
        p=qi;
        cout<<p->data.key<<" ";
        p = p->Rchild; 
    } 
}

int main(){
    cout<<"ÇëÊäÈëÒ»¸öÓ¢Îľä×Ó"<<endl;
    BSP T=(BSP)malloc(sizeof(BSN));
        T->Lchild=T->Rchild=NULL;
    char a[105];
    cin>>a;
    strcpy(T->data.key,a);
    while(strcmp(a,"."))
    { 
        BSP S=(BSP)malloc(sizeof(BSN));
            S->Lchild=S->Rchild=NULL;
        strcpy(S->data.key,a);
        T=BSTinsert(T,S);
        cin>>a;
    }
    cout<<"¶þ²æÅÅÐòÊ÷ÖÐÐò±éÀú£º"<<endl; 
    Inorder(T); 
    return 0;   
}

转码似乎有点问题，用utf-8就行了

java:

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

/**
 *@author movis
 */
public class Main {

    public static void main(String[] args) throws IOException {
        InputStreamReader in = new InputStreamReader(System.in);
        List<String> list = new ArrayList<String>();
        StringBuffer a = new StringBuffer("");
        boolean flag = false;
         
        //将输入句子以空格分隔存入一个字符串类型的顺序表
        System.out.println("请输入英文句子："); 
        int i = in.read();
        while(i != 46) {
            if(flag) {
                i = in.read();
            }
            while((i != 46) && (i != 32) && (i != 10) && (i != 13)) {
                a.append((char)i);
                i = in.read();
            }
            if(a != null) {
                list.add(a.toString());
                a = new StringBuffer("");
            }
            flag = true;
        }
        
        //根据顺序表建立二叉排序树
        BinarySortedTree tree = new BinarySortedTree();
        for(int j=0; j<list.size(); j++) {
            tree.add(list.get(j));
        }
        
        //二叉排序树的中序遍历
        tree.ergodic();
        
        in.close();
    }

}


import java.util.Stack;

/**
 *@author movis
 */
public class BinarySortedTree {

    /*
     * 二叉排序树的结点
     */
    public class Node{
        String data;
        Node lchild;
        Node rchild;
        Node parent;
        
        public Node(String data, Node lchild, Node rchild, Node parent) {
            this.data = data;
            this.lchild = lchild;
            this.rchild = rchild;
            this.parent = parent;
        }
    }
    
    private Node root;
    
    /**
     * 构造方法
     */
    public BinarySortedTree() {
        
    }
    
    public boolean add(String word, Node root) {
        if(root == null) {
            this.root = new Node(word, null, null, null);
            return true;
        }else if(root.data.compareTo(word) > 0){
            if(root.lchild != null) {
                return add(word, root.lchild);
            }else {
                root.lchild = new Node(word, null, null, root);
                return true;
            }
        }else if(root.data.compareTo(word) < 0) {
            if(root.rchild != null) {
                return add(word, root.rchild);
            }else {
                root.rchild = new Node(word, null, null, root);
                return true;
            }
        }else {
            return true;
        }
    }
    
    public void add(String word) {
        add(word, this.root);
    }
    
    //非递归遍历
    public void ergodic() {
        System.out.print("LDR:");
        Stack<Node> temp = new Stack<>();
        Node current = root;
        while(true) {
            while(current != null) {
                temp.push(current);
                current = current.lchild;
            }
            if(temp.isEmpty())
                break;
            current = temp.pop();
            System.out.print(" "+current.data);
            current = current.rchild;
        }
    }

}