精华内容
下载资源
问答
  • 主要介绍了JavaScript实现多叉的递归遍历和非递归遍历算法,结合实例形式详细分析了JavaScript多叉针对json节点的递归与非递归遍历相关操作技巧,需要的朋友可以参考下
  • 多叉树非递归遍历

    2015-09-26 20:35:37
    所用代码为C++ #define NOTHING_DONE ...//遍历用栈 finderStack.clear();//清空栈 sPointStr* point = &(this->m_point); finderStack.push_back(point);//初始入栈 while ((NULL != point) && (TRUE !

    所用代码为C++

    #define NOTHING_DONE

    std::vector<sPointStr*> finderStack;//遍历用栈
    finderStack.clear();//清空栈
    sPointStr* point = &(this->m_point);
    finderStack.push_back(point);//初始入栈
    while ((NULL != point) && (TRUE != finderStack.empty()))
    {
    cout << point->m_string << endl;
    point = finderStack.at(finderStack.size() - 1);//移动到栈顶
    finderStack.pop_back();//出栈
    if (0 != point->m_targetVector.size())
    {
    for (std::vector<sPointStr>::size_type counter = point->m_targetVector.size(); counter > 0; NOTHING_DONE)
    {
    finderStack.push_back(&(point->m_targetVector.at(--counter)));//入栈
    }
    }
    }
    finderStack.clear();point = NULL;

    #undef NOTHING_DONE

    思路跟递归调用一样,不过单独用一个栈解决。大致意思就是将父叶出栈的同时将子叶的所有元素入栈即可。

    展开全文
  • 本内容对二叉树前中后序遍历和K叉前后序遍历等5种遍历,用一种十分简单的策略,给出了非递归算法。
  • 算法列表 递归算法: ... 非递归算法 中序遍历 先序遍历 //先序遍历二叉树 bool PreOrder(PBitNode B) { if (B != NULL) { printf("%d ", B->da...

    算法列表

    递归算法:

    先序遍历

    中序遍历

    后序遍历

     非递归算法

    中序遍历

    先序遍历        

    //先序遍历二叉树
    bool PreOrder(PBitNode B)
    {
    	if (B != NULL)
    	{
    		printf("%d  ", B->data);
    		PreOrder(B->lchild);
    		PreOrder(B->rchild);
    	}
    	return true;
    }
    //中序遍历二叉树
    bool inorder(PBitNode B)
    {
    	if (B!=NULL)
    	{
    		inorder(B->lchild);
    		printf("%d  ", B->data);
    		inorder(B->rchild);
    	}
    	return true;
    }
    //后序遍历二叉树
    bool postorder(PBitNode B)
    {
    	if (B!=NULL)
    	{
    		inorder(B->lchild);
    		inorder(B->rchild);
    		printf("%d  ", B->data);
    	}
    	return true;
    }
    //中序遍历二叉树  非递归算法
    void inOrder(PBitNode root)
    {
    	if (root == NULL)
    		return;
    	PBitNode p = root;
    	stackNode s;
    	InitStack(s);
    	while(!StackEmpty(s) || p)
    	{
    		if (p)
    		{
    			PushStack(s, p);
    			p = p->lchild;
    		}
    		else
    		{
    			GetStackTopElement(s, &p);
    			PopStack(s);
    			std::cout << p->data;
    			p = p->rchild;
    		}
    	}
    }
    //先序遍历二叉树  非递归算法
    void preOrder(PBitNode root)
    { 
    	if (root == NULL) 
    		return;
    	PBitNode p = root;
    	stackNode s;
    	InitStack(s);
    	while (!StackEmpty(s) || p)
    	{ 
    		using namespace std;
    		if (p) 
    		{ 
    			cout << p->data; 
    			PushStack(s, p);
    			p = p->lchild; 
    		}
    		else 
    		{ 
    			GetStackTopElement(s, &p);
    			PopStack(s);
    			p= p->rchild; 
    		} 
    	}
    }
    
    

     

    展开全文
  • 数据结构遍历
    public class TreeNode {
        private int value;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(int value, TreeNode left, TreeNode right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
    
        public int getValue() {
            return value;
        }
    
        public TreeNode getLeft() {
            return left;
        }
    
        public TreeNode getRight() {
            return right;
        }
    }
    
    public static void main(String[] args) {
            printByNonRecursive();
            printByRecursive();
        }
        private static void printByNonRecursive(){
            TreeNode treeNode = buildTree();
            System.out.println("\n=======非递归访问结果======\n");
            System.out.print("前序:\t");
            preOrderByNonRecursive(treeNode);
            System.out.print("\n中序:\t");
            inOrderByNonRecursive(treeNode);
            System.out.print("\n后序:\t");
            postOrderByNonRecursive(treeNode);
        }
        /**
         * 利用栈保存访问路径
         * node 标示遍历的当前节点,如果当前节点为空,则置为null
         */
        private static void preOrderByNonRecursive(TreeNode root){
            Deque<TreeNode> stack = new LinkedList();
            TreeNode node = root;
            while (node != null || !stack.isEmpty()){
                //遍历,直到左子树为空
                while (node != null){
                    System.out.print(node.getValue() + "\t");
                    stack.push(node);
                    node = node.getLeft();
                }
                //弹出栈顶元素并遍历右子树
                while (!stack.isEmpty()){
                    node = stack.pop().getRight();
                    //右子树不空,则需要进行右子树的左子树遍历;右子树为空,则继续弹出栈顶元素
                    if (node != null){
                        break;
                    }
                }
            }
        }
    
        private static void inOrderByNonRecursive(TreeNode root){
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode node = root;
            while(node != null || !stack.isEmpty()){
                //遍历左子树
                while (node != null){
                    stack.push(node);
                    node = node.getLeft();
                }
                //弹出、访问栈顶元素,并遍历右子树
                while(!stack.isEmpty()){
                    node = stack.pop();
                    System.out.print(node.getValue() + "\t");
                    node = node.getRight();
                    if (node != null){
                        break;
                    }
                }
            }
        }
    
        private static void postOrderByNonRecursive(TreeNode root){
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode node = root;
            while (node != null || !stack.isEmpty()){
                //访问左子树
                while (node != null){
                    stack.push(node);
                    node = node.getLeft();
                }
                //弹出栈顶指针,访问右子树
                while (!stack.isEmpty()){
                    //获取到栈顶元素,但不弹出
                    node = stack.peek();
                    if(node.getRight() != null){
                        node = node.getRight();
                        break;
                    }else{
                        //如果栈顶元素没有右子树则弹出,并且如果是右孩子,还需要弹出其父节点
                        TreeNode right;
                        do {
                            right = stack.pop();
                            System.out.print(right.getValue() + "\t");
                        }while (!stack.isEmpty() && right == stack.peek().getRight());
                        node = null;
                    }
                }
            }
        }
    
        private static void printByRecursive(){
            TreeNode treeNode = buildTree();
            System.out.println("\n=======递归访问结果======\n");
            System.out.print("前序:\t");
            preOrderByRecursive(treeNode);
            System.out.print("\n中序:\t");
            inOrderByRecursive(treeNode);
            System.out.print("\n后序:\t");
            postOrderByRecursive(treeNode);
        }
        private static void preOrderByRecursive(TreeNode node){
            if(node == null){
                return;
            }
            System.out.print(node.getValue() + "\t");
            preOrderByRecursive(node.getLeft());
            preOrderByRecursive(node.getRight());
        }
    
        private static void inOrderByRecursive(TreeNode node){
            if (node == null){
                return;
            }
            inOrderByRecursive(node.getLeft());
            System.out.print(node.getValue() + "\t");
            inOrderByRecursive(node.getRight());
        }
    
        private static void postOrderByRecursive(TreeNode node){
            if (node == null){
                return;
            }
            postOrderByRecursive(node.getLeft());
            postOrderByRecursive(node.getRight());
            System.out.print(node.getValue() + "\t");
        }
    
        /**
         *                          100
         *           50                               80
         *       9      30                 20                  90
         *    3             15        16      25          150
         *               45    12                 30
         *  前序: 100 50 9 3 30 15 45 12 80 20 16 25 30 90 150
         *  中序: 3 9 50 30 45 15 12 100 16 20 25 30 80 150 90
         *  后序: 3 9 45 12 25 30 50 16 30 25 20 150 90 80 100
         */
        private static TreeNode buildTree(){
            TreeNode left = new TreeNode(45, null, null);
            TreeNode right = new TreeNode(12, null, null);
            TreeNode root = new TreeNode(15, left, right);
            root = new TreeNode(30, null, root);
            left = new TreeNode(3, null, null);
            TreeNode r1 = new TreeNode(9, left, null);
            root = new TreeNode(50, r1, root);
            left = new TreeNode(16, null, null);
            right = new TreeNode(25, null, new TreeNode(30, null, null));
            r1 = new TreeNode(80, new TreeNode(20, left, right), new TreeNode(90, new TreeNode(150, null, null), null));
            return new TreeNode(100, root, r1);
        }

     

    展开全文
  • 演示之前的准备工作演示项目的文件结构:index.html jsonData.js recurrenceTree.js ... jsonData.js 里面存储着多叉的JSON数据。 recurrenceTree.js 递归算法遍历树。 noRecurrenceTree.js 非递归

    演示之前的准备工作

    演示项目的文件结构:

    index.html
    jsonData.js
    recurrenceTree.js
    noRecurrenceTree.js

    解释一下各个文件:

    index.html 是用来演示的 HTML 文件。
    jsonData.js 里面存储着多叉树的JSON数据。
    recurrenceTree.js 递归算法遍历树。
    noRecurrenceTree.js 非递归算法遍历树。

    jsonData.js

    /**
     * 用于演示的 JSON 树形数据结构
     */
    var root = {
        name:'D盘',
        children:[
            {
                name:'学习',
                children:[
                    {
                        name:'电子书',
                        children:[
                            {
                                name:'文学',                                         
                                children:[
                                    {
                                        name:'茶馆'                                                   
                                    },
                                    {
                                      name:'红与黑'
                                    }
                                ]
                            }
                        ]
                    }
                ]
            },
            {
                name:'电影',
                children:[
                    {
                        name:'美国电影'
                    },
                    {
                        name:'日本电影'
                    }
                ]                  
            }
        ]
    }
    

    index.html

    <!DOCTYPE html>
    <html lang="en">
      <head>
        <meta charset="UTF-8">
        <meta name="renderer" content="webkit"/>
        <meta http-equiv="x-ua-compatible" content="ie=edge, chrome=1">
        <meta http-equiv="Cache-Control" content="max-age: 31536000">
        <title>blog04</title>
        <meta name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no">
        <meta name="wap-font-scale" content="no">
        <meta name="author" content="">
        <meta name="keywords" content="">
        <meta name="description" content="">
        <script type="text/javascript" src="jsonData.js"></script>
      </head>
      <body>
        递归遍历:<span id="app"></span>
        <script type="text/javascript" src="recurrenceTree.js"></script>
        <hr>
        非递归遍历:<span id="app2"></span>
        <script type="text/javascript" src="noRecurrenceTree.js"></script>
      </body>
    </html>
    

    递归遍历

    recurrenceTree.js

    // 遍历单个节点
    function traverseNode(node){
        var divObj = document.getElementById("app");
        divObj.innerHTML = divObj.innerHTML + "  " + node.name;
    }
    
    // 递归遍历树
    // 作者:张超
    function traverseTree(node){
        if (!node) {
            return;
        }
    
        traverseNode(node);
        if (node.children && node.children.length > 0) {
            var i = 0;
            for (i = 0; i < node.children.length; i++) {
                this.traverseTree(node.children[i]);
            }
        }
    }
    
    traverseTree(root);
    
    

    非递归遍历

    noRecurrenceTree.js

    // 遍历单个节点
    function traverseNode2(node){
        var divObj2 = document.getElementById("app2");
        divObj2.innerHTML = divObj2.innerHTML + "  " + node.name;
    }
    
    // 非递归遍历树
    // 作者:张超
    function traverseTree2(node){
        if (!node) {
            return;
        }
    
        var stack = [];
        stack.push(node);
        var tmpNode;
        while (stack.length > 0) {
            tmpNode = stack.pop();
            traverseNode2(tmpNode);
            if (tmpNode.children && tmpNode.children.length > 0) {
                var i = tmpNode.children.length - 1;
                for (i = tmpNode.children.length - 1; i >= 0; i--) {
                    stack.push(tmpNode.children[i]);
                }
            }
        }
    }
    
    traverseTree2(root);
    

    最后效果应该如下:

    这里写图片描述

    展开全文
  • /*********************************...的递归遍历和非递归遍历 ********************************************/ #include #include using namespace std; struct Node { Node(int v=0,Node* l=NULL,Node* r=NUL
  • 递归遍历 void preOrder(TreeNode *root){ if(!root) return; cout << root->val ; preOrder(root->left); preOrder(root->right); } void inOrder(TreeNode *root){ if(!root) return
  • 的递归与非递归遍历算法

    千次阅读 2017-10-28 14:01:55
    的递归与非递归遍历算法 的递归与非递归遍历算法 的遍历 实例 遍历的口诀 的递归遍历代码 的先序遍历 的中序遍历 的后序遍历 递归遍历思想 非递归遍历 的先序非递归遍历 先序遍历运行结果 ...
  • 按层遍历+ 中序非递归遍历+ 数据结构 + ……c++
  • 二叉树递归遍历与非递归遍历

    千次阅读 2015-07-23 21:10:11
    二叉树递归遍历与非递归遍历 二叉树递归遍历与非递归遍历 引言 递归式遍历 前序遍历 中序遍历 后序遍历 非递归式遍历 前序遍历 中序遍历 后序遍历 一种更简单的非递归式遍历 前序遍历 中序遍历 后序遍历 ...
  • 2.非递归遍历 3.层次遍历 1.递归遍历 在使用递归遍历的时候,每个节点会经过三次. public class PreInPosTraversal { public static class Node { public int value; public Node left; public Node ...
  • 文章目录前言前序遍历递归非递归中序遍历递归非递归后序遍历递归...然后我们分别实现一下各种遍历的递归与非递归的方式,节点定义如下: class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(...
  • 二叉树学习笔记(一)之遍历二叉树二叉树基础知识概念二叉树的性质满二叉树与完全二叉树二叉树的存储结构顺序存储链式存储二叉树的遍历首先来认识一下遍历先序遍历递归遍历非递归遍历中序遍历递归遍历非递归遍历后序...
  • 二叉树的前序、中序和后序的递归遍历与非递归遍历前序遍历前序遍历的递归遍历前序遍历的非递归遍历中序遍历中序遍历的递归遍历中序遍历非递归遍历后续遍历后序遍历的递归遍历后续遍历的非递归遍历
  • 二叉树的非递归遍历C/C++实现: 非递归先序遍历代码: void PreOrderTraversal (struct tree* root) { //非递归先序遍历 struct tree* temp = root; while (temp != NULL || S.top > 0) { while (temp !=...
  • 二叉树的非递归遍历及其递归遍历算法  二叉树的结构定义是一个递归的定义,在的定义中用到了的概念。在二叉树的一些应用中,,常常需要通过遍历二叉树获取某些元素的属性。 一:递归遍历   1.递归先序遍历 ...
  • 二叉树的递归与非递归遍历前序遍历二叉树递归遍历非递归遍历中序遍历二叉树递归遍历非递归遍历后序遍历二叉树递归遍历非递归遍历 将二叉树遍历的结果保存到vector中返回。 递归遍历代码简短,也相对容易理解,此不...
  • 详解二叉树的递归遍历与非递归遍历——(二)

    千次阅读 多人点赞 2019-08-04 21:44:10
    非递归遍历    上一边文章中,咱们谈到了二叉树的递归遍历,也是十分的简单哈,这回又继续将非递归遍历写一下。从前序开始扯吧,哈哈!!! 先给出存储结构: typedef struct Node{   &...
  • 文章目录1 先序遍历1.1 先序遍历递归1.2 先序遍历非递归2 中序遍历2.1 中序遍历递归2.2 中序遍历非递归3 后序遍历3.1 后序遍历递归3.2 后序遍历非递归4 层序遍历 1 先序遍历 若二叉树为空,则操作返回,否则先访问...
  • 二叉树的递归遍历与非递归遍历

    千次阅读 2018-07-27 14:14:05
    二叉树的遍历有递归与非递归两种方式,但思想大致相同 前序:先打印然后遍历完他的左子树,左子树为空时开始返回,并且开始以栈中元素为根遍历右子 中序:先遍历左子树然后左子树入栈,左子树为空再打印,再遍历...
  • 但是我发现自己对非递归遍历并不十分熟悉,所以把三种非递归遍历都写了一遍,以后看到这篇记录博客也可以帮助自己好好回想熟悉一下。 Leetcode对应习题:前序,中序,后序。 相对而言,这三种非递归遍历的难度...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 77,908
精华内容 31,163
关键字:

树的非递归遍历