精华内容
下载资源
问答
  • java多叉树层次遍历

    千次阅读 2018-05-28 23:13:55
    java多叉树的层次遍历,我的树好像不太一样,看代码吧。代码中的LLQueue 就是一个单链表实现的队列。 思路与二叉树的层次遍历一样。遍历一层的时候,把下层的节点放到队列中。就是操作有点不同。 /** * 功能 : ...

    java多叉树的层次遍历,我的树好像不太一样大笑,看代码吧。代码中的LLQueue 就是一个单链表实现的队列。

    思路与二叉树的层次遍历一样。遍历一层的时候,把下层的节点放到队列中。就是操作有点不同。

    /**
     * 功能 :
     * date : 2018/5/28
     *
     * @author : zcwang@wisdombud.com
     * @version : 0.0.4-snapshot
     * @since : JDK 1.8
     */
    public class TreeNode<T> {
        T data;
        private TreeNode<T> firstChild;
        private TreeNode<T> nextSibling;
    
        public TreeNode(final T data, final TreeNode<T> firstChild, final TreeNode<T> nextSibling) {
            this.data = data;
            this.firstChild = firstChild;
            this.nextSibling = nextSibling;
        }
    
        public TreeNode(final T data) {
            this(data, null, null);
        }
    
        public static void main(String args[]) {
            TreeNode<Integer> treeNode = new TreeNode<>(1);
            TreeNode<Integer> firstChild = new TreeNode<>(2);
            TreeNode<Integer> nextSibling = new TreeNode<>(3);
            TreeNode<Integer> nextSibling1 = new TreeNode<>(4);
            TreeNode<Integer> nextSibling2 = new TreeNode<>(5);
    
            TreeNode<Integer> firstChild1 = new TreeNode<>(6);
            TreeNode<Integer> nextSibling11 = new TreeNode<>(7);
            TreeNode<Integer> nextSibling12 = new TreeNode<>(8);
    
            TreeNode<Integer> firstChild2 = new TreeNode<>(9);
            TreeNode<Integer> nextSibling21 = new TreeNode<>(10);
            TreeNode<Integer> nextSibling22 = new TreeNode<>(11);
            treeNode.setFirstChild(firstChild);
            firstChild.setNextSibling(nextSibling);
            nextSibling.setNextSibling(nextSibling1);
            nextSibling1.setNextSibling(nextSibling2);
    
            nextSibling.setFirstChild(firstChild1);
            firstChild1.setNextSibling(nextSibling11);
            nextSibling11.setNextSibling(nextSibling12);
    
            nextSibling1.setFirstChild(firstChild2);
            firstChild2.setNextSibling(nextSibling21);
            nextSibling21.setNextSibling(nextSibling22);
            levelOrder(treeNode);
        }
    
        public static void levelOrder(TreeNode<Integer> root) {
            if (root == null) {
                return;
            }
            TreeNode<Integer> temp;
            LLQueue<TreeNode> queue = new LLQueue<>();
            queue.enQueue(root);
            while (!queue.isEmpty()) {
                temp = queue.deQueue();
                System.out.println(temp.getData());
                //判断是否存在孩子节点
                if (temp.getFirstChild() != null) {
                    queue.enQueue(temp.getFirstChild());
                    temp = temp.getFirstChild();
                    // 如果存在兄弟 就一直向queue中放
                    while (temp.getNextSibling() != null) {
                        queue.enQueue(temp.getNextSibling());
                        temp = temp.getNextSibling();
                    }
                }
            }
        }
    }

     

     

     

    展开全文
  • 使用Java简单实现多叉树遍历结点个数与插入结点 多叉树结点定义 class Node { public int id; public List<Node> sonList; public int getId() { return id; } public Node(int id,List<Node> ...

    使用Java简单实现多叉树的遍历结点个数与插入结点

    多叉树结点定义

    class Node {
        public int id;
        public List<Node> sonList;
        public int getId() {
            return id;
        }
    
        public Node(int id,List<Node> sonList) {
            this.id = id;
            this.sonList = sonList;
        }
        
        public void setId(int id) {
            this.id = id;
        }
    
        public List<Node> getSonList() {
            return sonList;
        }
    }
    

    多叉树的示例输入

    // 第一行为多叉树结点个数
    // 接下来有n-1行,每行有两个正整数x,y,表示在x和y结点之间存在一条边(1<=x<=y<=n)。默认y为x的根结点,结点1为多叉树的树根。
    6
    2 1
    3 2
    4 3
    5 2
    6 1
    

    代码:

    求以深度为2的结点为根结点的树,包含多少个结点,依次输出结点个数。
    如图所示,即求结点2和6下有多少个子结点。

    如图所示

    主程序
    public static int nodenum = 0; // 结点个数
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = Integer.parseInt(in.nextLine())-1;
        int[][] tree = new int[count][2];
        for(int i=0;i<count;i++){
            String temp = in.nextLine();
            String[] ss = temp.trim().split(" ");
            tree[i][0] = Integer.parseInt(ss[0]);
            tree[i][1] = Integer.parseInt(ss[1]);
        }
    
        Node entry = new Node(1, new ArrayList<Node>());
    
        for(int i=0;i<count;i++){
            insert(entry, tree[i][1], new Node(tree[i][0], new ArrayList<Node>()));
        }
    
        List<Node> subtree = entry.sonList;
        int[] num = new int[entry.sonList.size()]; // 存放子结点个数
    
        for(int i=0;i<entry.sonList.size);i++){
            nodenum = 0;
            queryAll(entry.sonList.get(i));
            num[i] = nodenum;
        }
        for(int t:num)
        	System.out.println(t);
    }
    
    插入新结点
    public static void insert(Node changeNode, int fatherId, Node newNode) {
        if (fatherId==changeNode.getId()) {
            changeNode.getSonList().add(newNode);
            return;
        }
    
        List<Node> sonList = changeNode.getSonList();
        if (sonList == null || sonList.isEmpty()) 
            return;
        else 
            for (int i = 0; i < sonList.size(); i++) 
                insert(sonList.get(i), fatherId, newNode);
    }
    
    遍历结点个数
    public static void queryAll(Node changeNode){
        List<Node> sonList = changeNode.getSonList();
    
        if (sonList==null||sonList.isEmpty())
            return;
    
        for (int i = 0; i <sonList.size() ; i++) {
            nodenum += 1;
            queryAll(sonList.get(i));
        }
    }
    
    展开全文
  • java多叉树遍历

    千次阅读 2019-01-23 08:54:26
    用过了二叉树后,正好业务上有一个需求,就是需要求出从根节点到每个叶子节点的路径集合,由于不是二叉树,而是如同一种多叉树的结构,下面来看具体代码, 1、节点对象,包含3个属性,当前节点Id,持有的父节点Id,...

    用过了二叉树后,正好业务上有一个需求,就是需要求出从根节点到每个叶子节点的路径集合,由于不是二叉树,而是如同一种多叉树的结构,下面来看具体代码,

    1、节点对象,包含3个属性,当前节点Id,持有的父节点Id,当前节点的内容,

    public class TreeNode {
    
    	/** 节点Id */
    	private String nodeId;
    	/** 父节点Id */
    	private String parentId;
    	/** 文本内容 */
    	private String text;
    
    	/**
    	 * 构造函数
    	 * 
    	 * @param nodeId
    	 *            节点Id
    	 */
    	public TreeNode(String nodeId) {
    		this.nodeId = nodeId;
    	}
    
    	/**
    	 * 构造函数
    	 * 
    	 * @param nodeId
    	 *            节点Id
    	 * @param parentId
    	 *            父节点Id
    	 */
    	public TreeNode(String nodeId, String parentId) {
    		this.nodeId = nodeId;
    		this.parentId = parentId;
    	}
    
    	public String getNodeId() {
    		return nodeId;
    	}
    
    	public void setNodeId(String nodeId) {
    		this.nodeId = nodeId;
    	}
    
    	public String getParentId() {
    		return parentId;
    	}
    
    	public void setParentId(String parentId) {
    		this.parentId = parentId;
    	}
    
    	public String getText() {
    		return text;
    	}
    
    	public void setText(String text) {
    		this.text = text;
    	}
    
    }
    

    2、多节点,我理解的是某个包含了多个其他节点的节点,即这个ManyTreeNode实际上存储的是当前节点以及对其包含的多个节点的引用,

    public class ManyTreeNode {
    
    	private TreeNode data;
    
    	private List<ManyTreeNode> childList;
    
    	public ManyTreeNode(TreeNode data) {
    		this.data = data;
    		this.childList = new ArrayList<ManyTreeNode>();
    	}
    
    	public ManyTreeNode(TreeNode data, List<ManyTreeNode> childList) {
    		this.data = data;
    		this.childList = childList;
    	}
    
    	public TreeNode getData() {
    		return data;
    	}
    
    	public void setData(TreeNode data) {
    		this.data = data;
    	}
    
    	public List<ManyTreeNode> getChildList() {
    		return childList;
    	}
    
    	public void setChildList(List<ManyTreeNode> childList) {
    		this.childList = childList;
    	}
    
    }
    

    3、多叉树节点的操作,插入,遍历等,

    public class ManyNodeTree {
    
    	/** 树根 */
    	private ManyTreeNode root;
    
    	public ManyNodeTree() {
    		root = new ManyTreeNode(new TreeNode("root"));
    	}
    
    	// 生成一个多茶树,根节点为root
    	public ManyNodeTree createTree(List<TreeNode> treeNodes) {
    
    		if (treeNodes == null || treeNodes.size() <= 0) {
    			return null;
    		}
    
    		ManyNodeTree manyNodeTree = new ManyNodeTree();
    		// 将所有节点添加到多茶树中
    		for (TreeNode treeNode : treeNodes) {
    			if (treeNode.getParentId().equals("root")) {
    				manyNodeTree.getRoot().getChildList().add(new ManyTreeNode(treeNode));
    			} else {
    				addChild(manyNodeTree.getRoot(), treeNode);
    			}
    		}
    		return manyNodeTree;
    	}
    
    	// 向指定多叉树节点添加子节点
    	public void addChild(ManyTreeNode manyTreeNode, TreeNode child) {
    		for (ManyTreeNode item : manyTreeNode.getChildList()) {
    			if (item.getData().getNodeId().equals(child.getParentId())) {
    				// 找到对应的父亲
    				item.getChildList().add(new ManyTreeNode(child));
    				break;
    			} else {
    				if (item.getChildList() != null && item.getChildList().size() > 0) {
    					addChild(item, child);
    				}
    			}
    		}
    
    	}
    
    	// 遍历多叉树
    	public String iteratorTree(ManyTreeNode manyTreeNode) {
    		List<String> rsData = new ArrayList<>();
    		StringBuilder buffer = new StringBuilder();
    		buffer.append("|");
    		if (manyTreeNode != null) {
    			for (ManyTreeNode index : manyTreeNode.getChildList()) {
    				buffer.append(index.getData().getNodeId() + ",");
    				if (index.getChildList() != null && index.getChildList().size() > 0) {
    					buffer.append(iteratorTree(index));
    					
    				}
    			}
    		}
    		
    		//buffer.append("\n");
    		
    		return buffer.toString();
    		
    		
    	}
    
    	public ManyTreeNode getRoot() {
    		return root;
    	}
    
    	public void setRoot(ManyTreeNode root) {
    		this.root = root;
    	}
    
    	public static void main(String[] args) {
    		List<TreeNode> treeNodes = new ArrayList<TreeNode>();
    		
    		treeNodes.add(new TreeNode("系统权限管理", "root"));
    		treeNodes.add(new TreeNode("用户管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("角色管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("组管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("用户菜单管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("角色菜单管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("用户权限管理", "系统权限管理"));
    		treeNodes.add(new TreeNode("站内信", "root"));
    		treeNodes.add(new TreeNode("写信", "站内信"));
    		treeNodes.add(new TreeNode("收信", "站内信"));
    		treeNodes.add(new TreeNode("草稿", "站内信"));
    
    		ManyNodeTree tree = new ManyNodeTree();
    
    		System.out.println(tree.iteratorTree(tree.createTree(treeNodes).getRoot()));
    		System.out.println("-------------");
    		String result = tree.iteratorTree(tree.createTree(treeNodes).getRoot());
    		
    	}
    
    }
    

    运行一下main函数,可以打印出从root开始到各个最终的子节点的值

    展开全文
  • 多叉树遍历

    2020-06-22 21:28:17
    429. N叉的层序遍历 给定一个 N 叉,返回其...深度不会超过 1000。 的节点总数不会超过 5000。 class Solution { public: vector<vector<int>> levelOrder(Node* root) { //特判 if(root ==

    429. N叉树的层序遍历

    给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。
    img
    返回其层序遍历:

    [
         [1],
         [3,2,4],
         [5,6]
    ]
    

    说明:

    1. 树的深度不会超过 1000
    2. 树的节点总数不会超过 5000
    class Solution {
    public:
        vector<vector<int>> levelOrder(Node* root) {
            //特判
            if(root == nullptr) return {};
            vector<vector<int>> res;
            queue<Node*> qu;
            qu.push(root);
            while(!qu.empty()){
                vector<int> temp;
                //每一层的个数
                int size = qu.size();
                for(int i = 0; i < size; i++){
                    Node* node = qu.front();
                    temp.push_back(qu.front()->val);
                    //遍历队头的孩子节点,如果不为空,加入队列
                    for (auto node : qu.front()->children) {
                        if (node){
                            qu.push(node);
                        }
                    }
                    qu.pop();
                }
                res.push_back(temp);
            }
            return res;
        }
    };
    /*
    // Definition for a Node.
    class Node {
    public:
        int val;
        vector<Node*> children;
    
        Node() {}
    
        Node(int _val) {
            val = _val;
        }
    
        Node(int _val, vector<Node*> _children) {
            val = _val;
            children = _children;
        }
    };
    */
    

    589. N叉树的前序遍历

    难度简单83

    给定一个 N 叉树,返回其节点值的前序遍历

    例如,给定一个 3叉树 :

    img

    返回其前序遍历: [1,3,5,6,2,4]

    1.递归解法

    class Solution {
        vector<int> res;
    public:
        vector<int> preorder(Node* root) {
            if(!root)   return{};
            res.push_back(root->val);
            for(auto p : root->children){
                preorder(p);
            }
            return res;
        }
    };
    

    2.迭代解法

    class Solution {
    public:
        vector<int> preorder(Node* root) {
            if(!root)   return{};	//特判
            
            vector<int> res;
            stack<Node*> st;
            
            st.push(root);
            Node* p;
            
            while(!st.empty()){
                p = st.top();
                st.pop();
                res.push_back(p->val);
                int size = p->children.size();
                for(int i = size-1; i>=0; i--){
                    st.push(p->children[i]);
                }
            }
            return res;
        }
    };
    

    590. N叉树的后序遍历

    给定一个 N 叉树,返回其节点值的后序遍历

    例如,给定一个 3叉树 :

    img

    返回其后序遍历: [5,6,3,2,4,1].

    分析:多叉树的后序遍历,仍然是左->右->根的顺序,只不过这里的左右是从左到右的顺序。N叉树的前序遍历类似, 但子树的入栈顺序为从左到右,最后将数组反转一下

    class Solution {
    public:
        vector<int> postorder(Node* root) {
            vector<int> v;
    
            if(!root) return v;
           
            stack<Node*> s;
            s.push(root);
    
            while(!s.empty()){
                Node* node = s.top();
                v.push_back(node->val);
                s.pop();
    
                //从左到右入栈
                for(int i = 0 ; i < node->children.size(); ++i){
                    if(node->children.at(i)) //非空结点才入栈
                        s.push(node->children.at(i));
                }
            }
    
            //将v反转
            reverse(v.begin(), v.end());
    
            return v;       
        }
    };
    

    另外因为多叉树有多个分叉,因此就没有中序遍历的概念了。

    展开全文
  • 从后台获得的json格式字符串如下: [{"thisNode":"10000480","prientNode":"10000480","level":"0","isLeaf":"0","children":[{"level":"1","prientNode":"10000440","this...我在前台的js中要怎么遍历出来啊,谢谢。
  • 关于多叉树遍历

    千次阅读 2019-06-26 16:34:49
    经过了一番查询与思考。目前把平常见的Tree的遍历分成3种情况。 递归遍历。非递归广度优先遍历。非递归深度优先遍历。...而非递归广度优先去遍历一个多叉树要用到 队列 这个东西。 目前java 的linkedList 实现了Qu...
  • 多叉树,简单地说,与二叉树类似,但叉可能要多的树形结构;类似于计算机文件目录。
  • 多叉树深度遍历

    千次阅读 2017-04-26 22:21:51
    问题:一个根目录下有多个子目录,每个子目录下又有多个子目录,要求按顺序深度遍历输出目录文件。 定义结点对象: package test; import java.util.List; public class Node { protected int value; ...
  • solution 多叉树的存储和遍历:一是链表指针结构强行乱搞,二是邻接表记录每个节点的子节点,vectorG[110]或者Tree[110][10]都可以。 用book[i]表示每一层的叶子节点个数,dfs遍历一遍树并记录当前depth,每访问到一...
  • 多叉树应用(多叉树创建, 遍历

    千次阅读 2017-11-03 17:32:01
    多叉树创建, 遍历...
  • 多叉树遍历 针对数据库仅由PID存储父子结构的情况 递归遍历 数据库全量取出数据 根据pid找出第一批节点 递归组装剩下节点 遍历根节点,找到根节点的下一层节点 深度优先遍历 public List<Node> ...
  • 主要介绍了JavaScript实现多叉树的递归遍历和非递归遍历算法,结合实例形式详细分析了JavaScript多叉树针对json节点的递归与非递归遍历相关操作技巧,需要的朋友可以参考下
  • 多叉树遍历不再分为前中后序遍历,而是深度优先遍历和广度优先遍历。其中深度优先遍历又分为递归和非递归。遍历算法深度优先遍历递归版本function recursionOrder(node) { nodeArr.push(node); if(node==null ||...
  • java多叉树的实现:节点集合生成多叉树,单个节点添加到多叉树深度遍历,广度遍历
  • 给定一个 N 叉,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个3叉: 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 基本思路: 就是BFS,记录层数的那一种。 AC代码: /* //...
  • 在做项目的过程中,遇到了多叉树的访问问题,其中要求保存访问至叶子节点的路径,查找网上资料都不是很合心意,故而自己用比较笨的方法保存然后输出 多叉树结构: class DataModel { public string name { get; ...
  • 一种多叉树的前序遍历C实现算法代码例子 在偶然的机会间涉及到了要对某些多未知数多方程求解其中的多数公因式的工程,然后在寻找他们的公因式时需要对其所有因式进行查找对比,由此自己感兴趣地花了几个时间写了一个...
  • //深度优先遍历 traverseDF(callback) { let stack = [], found = false; stack.unshift(this._root); let currentNode = stack.shift(); while (!found && currentNode) { found = callback...
  • javascript实现数据结构: 和二叉树,二叉树的遍历和基本操作 树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结构。 在计算机领域中也有着广泛的应用,例如在编译程序中,用来...
  • 项目上遇到了一个典型的多叉树应用案例, 记录一下。 (1) //结构 typedef struct st_OriTree { int levelValue; //树的level int orderValue; //排序值 QString nameValue; //当前节点名称 QString ...
  • 多叉树的递归遍历

    2015-08-13 21:13:01
    有一颗的结点结构为 struct TreeNode { int itemName; TreeNode *firstChild; //表明当前结点的第一个孩子结点 ...现在我想通过深度优先的方式遍历该结点,该怎么写? 求大神指点,谢谢
  • 多叉树非递归遍历

    千次阅读 2014-06-23 18:32:04
    //思想:此为先根遍历,与有向图的深度优先遍历相似 typedef int ElemType; typedef struct Node { ElemType data; struct Node *lchild; struct Node *rchild; }BTNode, *BTree;   void ...
  • //lastchild[f]不等于0,创建兄弟,即右儿子 }//i每加一次就要创建一个左儿子或右儿子,意思是第i个元素是上一个元素(若是兄弟,则是i-1,若是父亲则f(f=nodes[i].parent))的左子树或者右子 } } void Preorder...
  • 前天面试遇到一个多叉树面试的题目,在这里分享记录一下。 题目:一个树形的数据(如下数据),面试官给你一个id,然后拿到对应的name? 数据结构大概是这个样子 var cityData = [ { id: 1, name: '广东省', ...
  • 深度优先遍历 void travel(TreeNode *root); private : TreeNode* find (TreeNode *root, string str); private : TreeNode *root; }; # endif // TREE_H tree.cpp #include "tree.h" ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,180
精华内容 1,272
关键字:

多叉树深度遍历