精华内容
下载资源
问答
  • 二叉树 先根遍历 中跟遍历 后跟遍历 结构体: struct Node{ int val; Node *LC; Node *RC; Node(int k){ this->val=k; LC=NULL; RC=NULL; } }; 函数: void preOrder(Node *root){//先根遍历就是DFS...

    二叉树 先根遍历 中跟遍历 后跟遍历

    结构体:

    struct Node{
    	int val;
    	Node *LC;
    	Node *RC;
    	Node(int k){
    		this->val=k;
    		LC=NULL;
    		RC=NULL;
    	}
    };
    

    函数:

    void preOrder(Node *root){//先根遍历就是DFS呀 递归实现 
    	if(root==NULL){
    		return;
    	}
    	cout<<root->val<<" ";
    	preOrder(root->LC);
    	preOrder(root->RC); 
    }
    void inOrder(Node *root){
    	if(root==NULL){
    		return;
    	}
    	inOrder(root->LC);
    	cout<<root->val<<" ";
    	inOrder(root->RC);
    }
    void postOrder(Node *root){
    	if(root==NULL){
    		return;
    	}
    	postOrder(root->LC);
    	postOrder(root->RC);
    	cout<<root->val<<" ";
    } 
    //迭代实现     先访问,然后去左节点,最后右节点 stack起到了保存的作用。 
    void ppreOrder(Node *root){
    	stack<Node*> s;
        Node *p=root;
        while(p!=NULL||!s.empty())
        {
            while(p!=NULL)
            {
                cout<<p->val<<" ";
                s.push(p);
                p=p->LC;
            }
            if(!s.empty())
            {
                p=s.top();
                s.pop();
                p=p->RC;
            }
        }
    }
    void iinOrder(Node *root){
    	stack<Node *> s;
    	Node *p=root;
    	while(p!=NULL||!s.empty()){
    		while(p!=NULL){
    			s.push(p);
    			p=p->LC;
    		} 
    		if(!s.empty()){
    			p=s.top();
    			cout<<p->val<<" ";
    			s.pop();
    			p=p->RC;
    		}
    	}
    } 
    void ppostOrder(Node *root){  // 后序非递归遍历二叉树的顺序是先访问左子树,再访问右子树,最后访问根节点。当用堆栈来存储节点,必须分清返回根节点时,是从左子树返回的,还从右子树返回的。所以,使用辅助指针r,其指向最近访问过的节点。也可以在节点中增加一个标志域,记录是否已被访问
    	 Node *p = root, *r = NULL;
        stack<Node*> s;
        while (p!=NULL || !s.empty()) {
            if (p!=NULL) {//走到最左边
                s.push(p);
                p = p->LC;
            }
            else {
                p = s.top();
                if (p->RC!=NULL && p->RC != r)//右子树存在,未被访问
                    p = p->RC;
                else {
                    s.pop();
                    cout<<(p->val)<<" ";
                    r = p;//记录最近访问过的节点
                    p = NULL;//节点访问完后,重置p指针
                }
            }//else
        }//while
    }
    

    要写头文件 include<stack>
    Main函数:

    int main(){
    	Node *p=new Node(5);
    	Node *q=new Node(2);
    	Node *l=new Node(6);
    	Node *k=new Node(3);
    	q->RC=k; 
    	p->LC=q;
    	p->RC=l;
    	preOrder(p);
    	cout<<endl;
    	inOrder(p);
    	cout<<endl;
    	postOrder(p);
    	cout<<endl;	
    	ppreOrder(p);
    	cout<<endl;
    	iinOrder(p); 
    	cout<<endl;
    	ppostOrder(p);
    }
    

    结果输出:
    在这里插入图片描述
    先跟遍历和BFS一样,DFS利用queue来实现。
    参考博客:二叉树前序(先序)中序后序遍历 C++递归和非递归实现

    展开全文
  • 一、已知前序、中序、后序遍历结果的其中两种,还原二叉树。①已知前序遍历结果:1,2,4,5,3,6,7中序遍历结果:4,2,5,1,6,3,7还原二叉树后BFS出结果。TreeNode.javapublic class TreeNode {private ...

    一、已知前序、中序、后序遍历结果的其中两种,还原二叉树。

    ①已知前序遍历结果:1,2,4,5,3,6,7

    中序遍历结果:4,2,5,1,6,3,7

    还原二叉树后BFS出结果。

    TreeNode.java

    public class TreeNode {

    private TreeNode leftChild;

    private TreeNode rightChild;

    private Object data;

    public TreeNode getLeftChild() {

    return leftChild;

    }

    public void setLeftChild(TreeNode leftChild) {

    this.leftChild = leftChild;

    }

    public TreeNode getRightChild() {

    return rightChild;

    }

    public void setRightChild(TreeNode rightChild) {

    this.rightChild = rightChild;

    }

    public Object getData() {

    return data;

    }

    public void setData(Object data) {

    this.data = data;

    }

    public TreeNode(Object data) {

    super();

    this.data = data;

    }

    }

    CreateTree.java:

    import java.util.LinkedList;

    import java.util.Queue;

    public class CreateTree {

    public static TreeNode genenateTree(int[] pre, int[] in) {

    if (pre.length == 0 || in.length == 0) {

    return null;

    }

    TreeNode root = new TreeNode(pre[0]);

    int i = 0;

    while (in[i] != pre[0]) {

    i++;

    }

    int[] preLeftChild = new int[i];

    int[] preRightChild = new int[pre.length - 1 - i];

    int[] inLeftChild = new int[i];

    int[] inRightChild = new int[pre.length - 1 - i];

    for (int j = 0; j < in.length; j++) {

    if (j < i) {

    preLeftChild[j] = pre[j + 1];

    inLeftChild[j] = in[j];

    } else if (j > i) {

    preRightChild[j - i - 1] = pre[j];

    inRightChild[j - i - 1] = in[j];

    }

    }

    root.setLeftChild(genenateTree(preLeftChild, inLeftChild));

    root.setRightChild(genenateTree(preRightChild, inRightChild));

    return root;

    }

    public static void visited(TreeNode node) {

    System.out.print(node.getData() + " ");

    }

    public static void LevenOrder(TreeNode root) {

    if (root == null) {

    return;

    }

    Queue queue = new LinkedList<>();

    queue.add(root);

    TreeNode temp = null;

    while (!queue.isEmpty()) {

    temp = queue.poll();

    visited(temp);

    if (temp.getLeftChild() != null) {

    queue.add(temp.getLeftChild());

    }

    if (temp.getRightChild() != null) {

    queue.add(temp.getRightChild());

    }

    }

    }

    public static void main(String[] args) {

    int[] pre = { 1, 2, 4, 5, 3, 6, 7 };

    int[] in = { 4, 2, 5, 1, 6, 3, 7 };

    LevenOrder(genenateTree(pre, in));

    }

    }

    ②已知前序遍历结果:1,2,4,5,3,6,7

    后序遍历结果:4,5,2,6,7,3,1

    这种情况不能确定唯一的二叉树(即根据前序、后序结果不能确定唯一二叉树)

    ③已知 中序遍历结果:4,2,5,1,6,3,7

    后序遍历结果:4,5,2,6,7,3,1

    还原二叉树后BFS出结果。

    //这里只写出核心代码,其他部分可以参考第一种情况

    public class CreateTree {

    public static TreeNode genenateTree(int[] in, int[] post) {

    if (post.length == 0 || in.length == 0) {

    return null;

    }

    TreeNode root = new TreeNode(post[post.length - 1]);

    int i = 0;

    while (in[i] != post[post.length - 1]) {

    i++;

    }

    int[] postLeftChild = new int[i];

    int[] postRightChild = new int[post.length - 1 - i];

    int[] inLeftChild = new int[i];

    int[] inRightChild = new int[post.length - 1 - i];

    for (int j = 0; j < in.length; j++) {

    if (j < i) {

    postLeftChild[j] = post[j];

    inLeftChild[j] = in[j];

    } else if (j > i) {

    postRightChild[j - i - 1] = post[j - 1];

    inRightChild[j - i - 1] = in[j];

    }

    }

    root.setLeftChild(genenateTree(inLeftChild, postLeftChild));

    root.setRightChild(genenateTree(inRightChild, postRightChild));

    return root;

    }

    二、如果已知的前序、中序、后序的结果中包含占位符#,此时,只需知道其中一种遍历结果就能还原二叉树,且结果是唯一的。

    ①已知前序遍历结果是 :"1", "2", "4", "#", "#", "5", "#", "#", "3", "6", "#", "#", "7", "#", "#",还原二叉树后BFS出结果。

    import java.util.LinkedList;

    import java.util.Queue;

    public class CreateTree {

    static int count = 0;

    public static TreeNode genenateTree(String[] data) {

    TreeNode root = null;

    if (count >= data.length || data[count++].equals("#")) {

    root = null;

    } else {

    root = new TreeNode(data[count - 1]);

    root.setLeftChild(genenateTree(data));

    root.setRightChild(genenateTree(data));

    }

    return root;

    }

    public static void visited(TreeNode node) {

    System.out.print(node.getData() + " ");

    }

    public static void LevenOrder(TreeNode root) {

    if (root == null) {

    return;

    }

    Queue queue = new LinkedList<>();

    queue.add(root);

    TreeNode temp = null;

    while (!queue.isEmpty()) {

    temp = queue.poll();

    visited(temp);

    if (temp.getLeftChild() != null) {

    queue.add(temp.getLeftChild());

    }

    if (temp.getRightChild() != null) {

    queue.add(temp.getRightChild());

    }

    }

    }

    public static void main(String[] args) {

    String[] dataStr = { "1", "2", "4", "#", "#", "5", "#", "#", "3", "6", "#", "#", "7", "#", "#" };

    LevenOrder(genenateTree(dataStr));

    }

    }

    展开全文
  • span name=whlm id=whlm回答:smile2me学妹6月13日 13:32 //BinaryTree.h/* 二叉树的二叉链表结点定义 */typedef char datatype;typedef struct BiTNode{datatype data;struct BiTNode * LChild , * RChild ;...

    c9939646696d0e082ee17fcb364eb940.png

    span name=whlm id=whlm回答:smile2me

    学妹

    6月13日 13:32 //BinaryTree.h

    /* 二叉树的二叉链表结点定义 */

    typedef char datatype;

    typedef struct BiTNode

    {

    datatype data;

    struct BiTNode * LChild , * RChild ;

    } BiTNode , * BiTree ;

    //数叶子结点的数目

    /*

    Author: WadeFelix RenV

    */

    #include <stdio.h>

    #include <stdlib.h>

    #include "BinaryTree.h"

    int countLeaf( BiTree BT )

    {

    if( BT == NULL ) return 0;

    if( BT->LChild==NULL && BT->RChild==NULL ) return 1;

    return(countLeaf(BT->LChild)+countLeaf(BT->RChild));

    }

    //数非叶子结点的数目

    int countNotLeaf( BiTree BT )

    {

    if( BT == NULL ) return 0;

    if( BT->LChild==NULL && BT->RChild==NULL ) return 0;

    return(1+countNotLeaf(BT->LChild)+countNotLeaf(BT->RChild));

    }

    //判断是否是排序二叉树

    #include <stdio.h>

    #include <stdlib.h>

    #include "BinaryTree.h"

    int isPaiXu( BiTree BT )

    {

    if( BT == NULL )return 1;

    if( BT->LChild && (BT->LChild->data > BT->data) )return 0;

    if( BT->RChild && (BT->RChild->data < BT->data) )return 0;

    return( isPaiXu(BT->LChild)&&isPaiXu(BT->RChild) );

    }/span

    ◆◆

    评论读取中....

    请登录后再发表评论!

    ◆◆

    修改失败,请稍后尝试

    展开全文
  • 1,先根遍历-递归 由于先根次序遍历规则是递归,采用递归算法实现的递归方法必须有参数,通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法,因此,每种递归的遍历...

    1,先根遍历-递归

    由于先根次序遍历规则是递归,采用递归算法实现的递归方法必须有参数,通过不同的实际参数区别递归调用执行中的多个方法。而二叉树类必须提供从根节点开始遍历的成员方法,因此,每种递归的遍历算法由两个重载的成员方法实现。

    【思路先根遍历,即第一次遇到的结点就开始打印。一直遍历左子树,直到为空,然后开始递归右子树,直到为空。

    【过程】先将1进入方法,2,3执行方法,2先执行,在2中将4,5执行方法,直到发现4无子树,然后轮到5执行方法。直到发现5没有子树,此时2方法结束,轮到3执行方法。

    public void preorder(){        //输出先根次序遍历序列
        preorder(this.root);       //调用先根次序遍历二叉树的递归方法
        System.out.println();
    }    
    private void preorder(BinaryNode<T> p){     //先根次序遍历以p结点为根的子树,递归方法
        if (p!=null){                                      //若二叉树不空
            System.out.print(p.data.toString()+" ");       //先访问当前结点元素
            preorder(p.left);      //按先根次序遍历p的左子树,递归调用,参数为左孩子
            preorder(p.right);     //按先根次序遍历p的右子树,递归调用,参数为右孩子
        }
    }

    2,先根遍历-非递归

    【思路】还是先根遍历,遇到结点就压入栈中,每当发现某个结点无子树,将结点设置为从栈中弹出元素。如果不为空就打印。

    【过程】先将1压入栈中,然后让结点=1.left,1的左子树=2,发现2不为空压入栈中,继续。。。当发现4无子树时,从栈中弹出2,使得p=2,right=5,此时栈中只有1,等发现5没有子树时,p弹栈=1。

    public void preorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
    	BinaryNode<T> p = this.root;
    	while (p != null || !stack.isEmpty()) {
    	    if (p != null) {
    		    System.out.print(p.data + " "); // 先根遍历
    			stack.push(p);
    			p = p.left;
    		} else {
    			System.out.print("^ ");
    			p = stack.pop();
    			p = p.right;
    		}
    	}
    }​​

    3,中根遍历-递归

    【思路】开始从跟结点遍历,当第二次遍历到该结点时打印。如何区分是第二次了,在递归中只需要在左右子树中间打印即可。因为但遍历完左子树时,回到父母结点时为第二次遍历到父母结点,第一次为通过父母接到遍历到孩子结点时。

    【过程】从1开始进入遍历方法,发现1不为空,将2,3进入遍历方法。由于2先开始,此时3一直在等待2的结束。2发现4.5不是空,将4,5进入遍历方法,此时没有打印2.当4结束时在通过2进入5之前打印此时结点,即为中根遍历。

    public void inorder(){         //输出中根次序遍历序列
        inorder(this.root);
        System.out.println();
    }    
    private void inorder(BinaryNode<T> p){    //中根次序遍历以p结点为根的子树,递归方法
        if (p!=null){
            inorder(p.left);                  //中根次序遍历p的左子树,递归调用
            System.out.print(p.data.toString()+" ");
            inorder(p.right);             //中根次序遍历p的右子树,递归调用
        }
    }

    4,中根遍历-非递归

    【思路】参考先根遍历中的非递归方法。先根遍历是在第一次遇到非空的时候打印。中根稍有区别,在第一次非空时入栈,不打印,当发现子树为空时,弹栈时回到空子树的父母结点时,打印,此时为第二次访问,即中根遍历。

    【过程】1开始进入while循环,发现1.left=2不为空入栈,此时不要打印,然后4,进入循环,入栈,发现4左子树为空,此时弹栈,弹出4,立即打印,达到中根遍历。其余相似。

    public void inorderTraverse() {
        LinkedStack<BinaryNode<T>> stack = new LinkedStack<BinaryNode<T>>();
    	BinaryNode<T> p = this.root;
    	BinaryNode<T> q1 = null;
    	BinaryNode<T> q2;
    	boolean flag = true;
    	while (p != null || !stack.isEmpty()) {
    	    if (p != null) {
    		    stack.push(p);
    			p = p.left;
    		} else {
    			System.out.print("^ ");
    			p = stack.pop();
    			System.out.print(p.data + " "); // 中跟遍历
    			p = p.right;
    		}
    
    	}
    }

    5,后根遍历-递归

    【思路】现遍历子树,等左右子树都遍历完后,在打印结点。跟之前的类比一下很容易想到。

    【过程】1进入递归,发现2,3非空,然后2进入递归,3等待,2又发现4,5非空,此时4进入递归,5等待,然后4发现左右子树都为空,此时不再进行递归,打印4结点的值。

    public void postorder(){      //输出后根次序遍历序列
        postorder(this.root);
        System.out.println();
    }
    private void postorder(BinaryNode<T> p){        //后根次序遍历以p结点为根的子树,递归方法
        if (p!=null){
            postorder(p.left);
            postorder(p.right);
            System.out.print(p.data.toString()+" ");      //后访问当前结点元素
        }
    }

    6,后根遍历-非递归

    【思路】由于需要确定当前结点被访问过两次,此时需要额外一个结点来储存之前访问的结点。符合打印条件的就一共两种情况,一是无子结点,直接打印。二是当前访问的结点其右子树已被访问,或者右子树不存子,左子树被访问过。

    一定要注意,先将右子树入栈,再将左子树入栈,因为访问时是现访问左子树,在访问右子树。

    public void postorderTraverse() {
        LinkedStack<BinaryNode> stack = new LinkedStack<BinaryNode>();
    	BinaryNode cur, pre = null;       //pre为额外结点,记录前一个结点,用于打印
    	stack.push(this.root);
    	while (!stack.isEmpty()) {
    	    cur = stack.peek();
    		if ((cur.left == null && cur.right == null) || (pre != null && (cur.left == pre || cur.right == pre))) {            //判断是否为上述条件决定是否打印
    		    BinaryNode temp = stack.pop();
    			System.out.print(temp.data + " ");
    			pre = temp;
    		} else {
    			if (cur.right != null) {        //右结点入栈
    			    stack.push(cur.right);
    			}
    			if (cur.left != null) {
    				stack.push(cur.left);
    			}
    		}
    	}
    }

     

    展开全文
  • 二叉树遍历

    2018-03-16 10:20:44
    二叉树遍历方法有三种:先根遍历、中根遍历、后跟遍历。遍历方法:判断二叉树是否存在,如果存在,判断左孩子是否存在,如果存在,把左孩子作为参数传入,继续调用;判断右孩子是否存在,如果存在,把右孩子作为参数...
  • 若树不空,则先依次后跟遍历各棵子树,然后访问根节点。 按层次遍历: 若树不空,则自上而下自左至右访问树中每个结点。 遍历结果: 先跟遍历:ABCDEABCDEABCDE 后跟遍历:BDCEABDCEABDCEA 层次遍历:...
  • 树和森林的遍历

    2019-10-13 21:33:25
    其访问顺序与这棵树相应的二叉树的先序遍历相同,后跟遍历,若树非空,则从左到右的顺序遍历根结点的每一棵子树,之后再访问根结点。其访问顺序与这颗树相应二叉树的中序遍历相同。另外,树也有层次遍历,与二叉树的...
  • 二叉树的非递归遍历

    2014-03-24 20:17:11
    后跟遍历一个节点,这个节点一般的入栈两次,第二次出战的时候才访问,所以得有个标志,标记是节点第几次入栈。 层次遍历一般得用到队列 线索树:左链接域指向左孩子节点或前驱节点,右链接域指向右孩子节点或...
  • 给定二叉树的2个遍历序列(如先根+中根,先根+后根,中根+后根等),是否能够根据这2个遍历序列唯一确定二叉树? 2结论 这三种组合并不是都能唯一确定二叉树的,其中先根+后根就不能唯一确定一棵二叉树,中根+先根...
  • 二叉树的内容分

    2012-12-01 18:53:05
    二叉树的先根,中根遍历,后跟遍历,层次遍历,
  • 矩阵的遍历

    2020-05-07 11:04:23
    对它进行回形遍历的顺序为:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Input 测试数据有多组,第1行是测试数据的组数T。每组的第1行是正整数n(1<n<10), 后跟n行,每行n个整数。数据之间由空格分隔。...
  • 练习(8-29)

    2019-08-29 21:51:03
    1.给定一棵树的先根遍历序列和后跟遍历序列,能否唯一确定一棵树?若能,请举例说明;若不能,请给出反例 答:一棵树的先根遍历与其对应二叉树的先序遍历结果相同,树的后根遍历结果与其对应二叉树表示的中序遍历...
  • 后跟跳跃遍历,Postorder Traversal (LRD)Jumped,是一种轻量级、高性能的个性化匹配算法,可用于APP中启动图片、 运营广告位、推荐应用等功能模块,实现不限规则任意可配的效果。
  • JS 循环遍历总结

    2020-11-26 00:19:09
    使用分号分隔,后跟一个用于在循环中执行的语句(通常是一个块语句)。 示例 var i = 0; for (; i < 9; i++) { console.log(i); // more statements } for…in 介绍 1.for...in语句以任意顺序遍历一个...
  • 背景:有两种结构:对象和数组,对象是没有length这个属性,而数组结构是有的,下面分别说下这两种结构之间的区别和遍历方式。1.对象一个对象以"{"开始,"}"结束。每个"key"后跟一":","'key/value' 对"之间运用 ",...
  • 我们惊人的发现:树、森林的前跟遍历和二叉树的前序遍历结果相同;树、森林的后跟遍历和二叉树的中序遍历结果相同! 参考资料:http://www.cnblogs.com/xxiaoye/p/3642533.html
  • 中序遍历是先左孩子 后跟 最后右孩子的顺序。所以应该先一个while循环把所有的根及其左孩子依次入栈,然后一个while循环 将栈顶元素取出,遍历,如果有右孩子,同样需要将其及其左孩子入栈。代码如下 TreeNode tem ...
  • javascript遍历json对象数据的方法

    万次阅读 2018-01-10 09:02:37
    JSON中,有两种结构:对象和数组,对象是没有length这个属性,而...每个“key”后跟一“:”,“‘key/value’ 对”之间运用 “,”分隔。 packJson = {"name":"phpernote", "password":"111"} 原生Js遍历json对象的方
  • Python循环遍历文件

    千次阅读 2015-04-20 14:56:35
    for后跟变量名,in后跟序列,注意加冒号 for循环每次从序列中取一个值放到变量中 此处的序列主要指 列表 元组 字符串 文件 ''' print i else: print "error" for i in "qwe","asd","zxc": print i ''' python...
  • 二叉树的实现 c++

    2008-12-14 22:11:01
    c++二叉树的实现, 二叉树的建立,输出。 先根,中根,后跟遍历。。。 二叉树的插入机删除。。。
  • DFS又称深度优先遍历,包括先根遍历(先遍历根节点,其次左结点,最后右节点),中根遍历(先遍历左节点,其次根结点,最后右节点),后跟遍历(先遍历左节点,其次右结点,最后根节点) 源码实现 节点实体类定义 ...
  • 后跟跳跃遍历,是指在树结构的后根遍历过程中,跳过那些对计算结果不再起作用的节点,让遍历速度达到最快的一种遍历方式。可以在涉及到规则匹配的系统中使用。 研发背景 老的广告运营位的设计存在一些问...
  • for语句用于创建一个循环,它包含了三个可选的表达式,这三个表达式被包围在圆括号之中,使用分号分隔,后跟一个用于在循环中执行的语句(通常是一个块语句)。 var arr = ['一','二','三','四','五'] ; for (var...
  • Given inorder and postorder traversal of a tree, construct the...根据中根遍历和后跟遍历,求二叉树。 class Solution { public: TreeNode *createTree(vector<int>&in,int l1,int r1,vector<int>&post,int l2,int
  • 概述 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,采用完全独立于语言的文本格式,是理想的数据交换格式。同时,JSON是 JavaScript 原生格式,这意味着在 JavaScript 中...每个“key”后跟一“:”

空空如也

空空如也

1 2 3 4 5
收藏数 86
精华内容 34
关键字:

后跟遍历