树状图的输出(递归转循环)

ゝ一纸荒年。 2022-10-07 07:00 172阅读 0赞

# 树状图的输出(递归转循环) #

> 解析树状图的时候，递归算是比较好理解的方式，但是递归在遍历大量的树状图数据时，反而会引起`栈溢出`，此时就需要转循环了。

## 模拟一个数据 ##

{
        "name":"1",
        "child":[
            {
                "name":"2",
                "child":[
                    {
                        "name":"4",
                        "child":[
                            {
                                "name":"9",
                                "child":[
    
                                ]
                            }
                        ]
                    },
                    {
                        "name":"5",
                        "child":[
    
                        ]
                    }
                ]
            },
            {
                "name":"3",
                "child":[
                    {
                        "name":"6",
                        "child":[
    
                        ]
                    },
                    {
                        "name":"7",
                        "child":[
    
                        ]
                    },
                    {
                        "name":"8",
                        "child":[
    
                        ]
                    }
                ]
            }
        ]
    }

## 用不同的方式输出 ##

package com.demo.myapplication;
    
    import android.support.v7.app.AppCompatActivity;
    import android.os.Bundle;
    import android.util.Log;
    
    import com.google.gson.Gson;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class MainActivity extends AppCompatActivity {
    
        private final String TAG = "MainActivity";
    
        @Override
        protected void onCreate(Bundle savedInstanceState) {
            super.onCreate(savedInstanceState);
            setContentView(R.layout.activity_main);
    
            String json = "{\n" +
                    "    \"name\":\"1\",\n" +
                    "    \"child\":[\n" +
                    "        {\n" +
                    "            \"name\":\"2\",\n" +
                    "            \"child\":[\n" +
                    "                {\n" +
                    "                    \"name\":\"4\",\n" +
                    "                    \"child\":[\n" +
                    "                        {\n" +
                    "                            \"name\":\"9\",\n" +
                    "                            \"child\":[\n" +
                    "\n" +
                    "                            ]\n" +
                    "                        }\n" +
                    "                    ]\n" +
                    "                },\n" +
                    "                {\n" +
                    "                    \"name\":\"5\",\n" +
                    "                    \"child\":[\n" +
                    "\n" +
                    "                    ]\n" +
                    "                }\n" +
                    "            ]\n" +
                    "        },\n" +
                    "        {\n" +
                    "            \"name\":\"3\",\n" +
                    "            \"child\":[\n" +
                    "                {\n" +
                    "                    \"name\":\"6\",\n" +
                    "                    \"child\":[\n" +
                    "\n" +
                    "                    ]\n" +
                    "                },\n" +
                    "                {\n" +
                    "                    \"name\":\"7\",\n" +
                    "                    \"child\":[\n" +
                    "\n" +
                    "                    ]\n" +
                    "                },\n" +
                    "                {\n" +
                    "                    \"name\":\"8\",\n" +
                    "                    \"child\":[\n" +
                    "\n" +
                    "                    ]\n" +
                    "                }\n" +
                    "            ]\n" +
                    "        }\n" +
                    "    ]\n" +
                    "}";
    
    
            Person person = new Gson().fromJson(json, Person.class);
    
            // 常规的递归
            Log.d(TAG, "------------------------------ 常用递归");
            printPerson(person);
    
            // 递归改循环（广度优先）（避免爆栈）
            Log.d(TAG, "------------------------------ 递归改循环（广度优先）");
            printPerson2(person);
    
            // 递归改循环（深度优先）（避免爆栈）
            Log.d(TAG, "------------------------------ 递归改循环（深度优先）");
            printPerson3(person);
    
            // 生成新的树状图对象（递归）
            Log.d(TAG, "------------------------------ 生成新的树状图对象（递归） ");
            Human human = printPerson4(person);
            Log.d(TAG, "human json: " + new Gson().toJson(human));
    
            // 生成新的树状图对象（循环）
            Log.e(TAG, "------------------------------ 生成新的树状图对象（循环） ");
            Human human2 = printPerson5(person);
            Log.e(TAG, "human2 json: " + new Gson().toJson(human2));
    
            // 递归改循环（广度优先）（避免爆栈）(加入深度)
            Log.d(TAG, "------------------------------ 归改循环（广度优先）（避免爆栈）(加入深度) ");
            printPerson6(person);
        }
    
        private void printPerson(Person person) {
            Log.d(TAG, person.getName());
            if (person.getChild() != null && person.getChild().size() != 0) {
                for (int i = 0; i < person.getChild().size(); i++) {
                    printPerson(person.getChild().get(i));
                }
            }
        }
    
        private void printPerson2(Person rooPerson) {
            List<Person> personList = new ArrayList<>();
    
            personList.add(rooPerson);
    
            while (personList.size() != 0) {
                Person person = personList.remove(0);
                if (person == null) continue;
                Log.d(TAG, person.getName());
                if (person.getChild() != null && person.getChild().size() != 0) {
                    personList.addAll(person.getChild());
                }
            }
        }
    
        private void printPerson3(Person rooPerson) {
    
            Stack<Person> stack = new Stack<>();
            stack.push(rooPerson);
    
            while (!stack.isEmpty()) {
                Person person = stack.pop();
                Log.d(TAG, person.getName());
                if (person.getChild() != null && person.getChild().size() != 0) {
                    for (int i = person.getChild().size() - 1; i >= 0; i--) {
                        stack.push(person.getChild().get(i));
                    }
                }
            }
        }
    
        private Human printPerson4(Person rooPerson) {
    
            Human rootHuman = new Human();
            rootHuman.setName(rooPerson.getName());
    
            if (rooPerson.getChild() != null && rooPerson.getChild().size() != 0) {
                List<Human> humanList = new ArrayList<>();
                for (int i = 0; i < rooPerson.getChild().size(); i++) {
                    humanList.add(printPerson4(rooPerson.getChild().get(i)));
                }
                rootHuman.setChild(humanList);
            }
    
            return rootHuman;
        }
    
        private static Human printPerson5(Person rooPerson) {
            List<Person> personList = new ArrayList<>();
            List<Human> humanList = new ArrayList<>();
            Human rootHuman = new Human();
            personList.add(rooPerson);
            humanList.add(rootHuman);
            while (personList.size() != 0) {
                Person person = personList.remove(0);
                Human human = humanList.remove(0);
                if (person == null) continue;
                human.setName(person.getName());
                //System.out.println(person.getName());
                if (person.getChild() != null && person.getChild().size() != 0) {
                    personList.addAll(person.getChild());
                    List<Human> list = new ArrayList<>();
                    for (int i = 0; i < person.getChild().size(); i++) {
                        Human h = new Human();
                        list.add(h);
                    }
                    humanList.addAll(list);
                    human.setChild(list);
                }
            }
            return rootHuman;
        }
    
        private void printPerson6(Person rooPerson) {
            DepthPerson rootDepthPerson = new DepthPerson();
            rootDepthPerson.setChild(rooPerson.getChild());
            rootDepthPerson.setIndex(rooPerson.getIndex());
            rootDepthPerson.setName(rooPerson.getName());
            rootDepthPerson.setDepth(1); // 初始 1
    
            List<DepthPerson> depthPersonList = new ArrayList<>();
    
            depthPersonList.add(rootDepthPerson);
    
            while (depthPersonList.size() != 0) {
                DepthPerson depthPerson = depthPersonList.remove(0);
                if (depthPerson == null) continue;
                Log.d(TAG, depthPerson.getName() + "  深度：" + depthPerson.getDepth());
                if (depthPerson.getChild() != null && depthPerson.getChild().size() != 0) {
                    for (int i = 0; i < depthPerson.getChild().size(); i++) {
                        Person person = depthPerson.getChild().get(i);
                        DepthPerson temp = new DepthPerson();
                        temp.setChild(person.getChild());
                        temp.setIndex(person.getIndex());
                        temp.setName(person.getName());
                        temp.setDepth(depthPerson.getDepth() + 1); 
                        depthPersonList.add(temp);
                    }
                }
            }
        }
    
        // ---------------------------------------------------------------------------------------------
        //
        // Person 、 Human 两个实体类
        //
        // ---------------------------------------------------------------------------------------------
    
        public static class Person {
            private int index;
            private String name;
            private List<Person> child;
    
            public int getIndex() {
                return index;
            }
    
            public void setIndex(int index) {
                this.index = index;
            }
    
            public String getName() {
                return name;
            }
    
            public void setName(String name) {
                this.name = name;
            }
    
            public List<Person> getChild() {
                return child;
            }
    
            public void setChild(List<Person> child) {
                this.child = child;
            }
        }
    
        public static class DepthPerson extends Person {
    
            private int depth;
    
    
            public int getDepth() {
                return depth;
            }
    
            public void setDepth(int depth) {
                this.depth = depth;
            }
        }
    
        public static class Human {
            private String name;
            private int depth;
            private List<Human> child;
    
            public Human() {
            }
    
            public String getName() {
                return name;
            }
    
            public void setName(String name) {
                this.name = name;
            }
    
            public int getDepth() {
                return depth;
            }
    
            public void setDepth(int depth) {
                this.depth = depth;
            }
    
            public List<Human> getChild() {
                return child;
            }
    
            public void setChild(List<Human> child) {
                this.child = child;
            }
        }
    
    
    }