树结构（java版）

朴灿烈づ我的快乐病毒、 2022-05-21 10:27 198阅读 0赞

今天实现下面的树结构  
![这里写图片描述][70]

创建节点：

public class Node { 
        private char data;
        private Node lchild;
        private Node rchild;
    
        public char getData() {
            return data;
        }
    
        public void setData(char data) {
            this.data = data;
        }
    
        public Node getLchild() {
            return lchild;
        }
    
        public void setLchild(Node lchild) {
            this.lchild = lchild;
        }
    
        public Node getRchild() {
            return rchild;
        }
    
        public void setRchild(Node rchild) {
            this.rchild = rchild;
        }
    
        public Node(char data, Node lchild, Node rchild) {
            super();
            this.data = data;
            this.lchild = lchild;
            this.rchild = rchild;
        }
    
        @Override
        public String toString() {
            return " " + getData() ;
        }
    }

创建树结构，并添加先序，中序，后序方法：

public class Tree {
        //创建树
        public Node createTree(String exp){
            Node[] nodes = new Node[3];
            Node b =null, p = null;
            int  top = -1,k =0,j = 0;
            char[] exps = exp.toCharArray();
            char data = exps[j];
            while (j < exps.length-1){
                switch (data){
                    case '(':
                        top ++;
                        nodes[top] = p;
                        k = 1;
                        break;
                    case ')':
                        top --;
                        break;
                    case ',':
                        k = 2;
                        break;
                    default:
                        p=new Node(data, null, null);
                        if(b==null){
                            b=p;
                        }else{
                            switch (k) {
                                case 1:
                                    nodes[top].setLchild(p);
                                    break;
                                case 2:
                                    nodes[top].setRchild(p);
                                    break;
                            }
                        }
                }
                j++;
                data=exps[j];
            }
            return b;
        }
    
        //先序
        public void PreOrder(Node node){
            if(node==null){
                return;
            }else{
                System.out.print(node.getData()+" ");
                PreOrder(node.getLchild());
                PreOrder(node.getRchild());
            }
        }
    
        //中序
        public void InOrder(Node node){
            if(node==null){
                return;
            }else{
                InOrder(node.getLchild());
                System.out.print(node.getData()+" ");
                InOrder(node.getRchild());
            }
        }
    
        //后序
        public void PostOrder(Node node){
            if(node==null){
                return;
            }else{
                PostOrder(node.getLchild());
                PostOrder(node.getRchild());
                System.out.print(node.getData()+" ");
            }
        }
    
    
    }

Test：

public class Test {
        public static void main(String[] args) {
            String str="A(B(D(,G)),C(E,F))";
            Tree tree=new Tree();
            Node node=tree.createTree(str);
            System.out.println("先序：");
            tree.PreOrder(node);
            System.out.println();
            System.out.println("中序：");
            tree.InOrder(node);
            System.out.println();
            System.out.println("后序：");
            tree.PostOrder(node);
        }
    }

结果：  
![这里写图片描述][70 1]

[70]: /images/20220521/0f39e5df301f444a9bd2514857d119a3.png
[70 1]: /images/20220521/c37b4c69f44a4f08b3c179ceee0d4543.png