精华内容
下载资源
问答
  • 后序遍历:{左孩子}{右孩子}根 根据当前先序遍历的第一个元素可以确定该元素是当前树的根结点,从中序遍历中找到该结点,该结点左边是左子树,右边是右子树,递归上述过程,直到当前先序遍历序列长度为0 转化函数...

    思路

    先序遍历:根{左孩子}{右孩子}
    中序遍历:{左孩子}根{右孩子}
    后序遍历:{左孩子}{右孩子}根
    根据当前先序遍历的第一个元素可以确定该元素是当前树的根结点,从中序遍历中找到该结点,该结点左边是左子树,右边是右子树,递归上述过程,直到当前先序遍历序列长度为0

    转化函数代码

    static class Node {
    	int key;
    	Node leftChild;
    	Node rightChild;
    	public Node(int key) {
    		this.key = key;
    		this.leftChild = null;
    		this.rightChild = null;
    	}
    }
    	
    static Node init(int[] preOrder, int[] inOrder) {
    	if(preOrder.length > 0 && inOrder.length > 0){
    		Node root = new Node(preOrder[0]);
    		int i;
    		for(i = 0 ; i < inOrder.length ; i++) 
    		    if(inOrder[i] == preOrder[0]) 
    		        break;
    			root.leftChild = init(Arrays.copyOfRange(preOrder, 1, 1+i), Arrays.copyOfRange(inOrder, 0, 0+i));
    			root.rightChild = init(Arrays.copyOfRange(preOrder, 1+i, preOrder.length), Arrays.copyOfRange(inOrder, 1+i, inOrder.length));
    			return root;
    		}
    	else
    		return null;
    }
    
    展开全文
  • 2018.4.18 这道题说的是利用栈来模拟...理解了这点这道题就转换成已知先序遍历+中序遍历,打印二叉树的后序遍历的问题了。 有两个思路:1.根据先序遍历和中序遍历先构建一棵二叉树,再后序遍历打印这棵树;2....

    2018.4.18

    这道题说的是利用栈来模拟二叉树,通过栈的出入情况,模拟出这棵二叉树,并后序遍历打印这棵二叉树。

    这题关键点在于理解二叉树的非递归遍历,能够看得出入栈顺序就是二叉树的先序遍历序列,出栈顺序就是二叉树的中序遍历序列。理解了这点这道题就转换成已知先序遍历+中序遍历,打印二叉树的后序遍历的问题了。

    有两个思路:1.根据先序遍历和中序遍历先构建一棵二叉树,再后序遍历打印这棵树;2.直接通过先序遍历和中序遍历得出后序遍历序列。其实能够做出思路1,想想肯定能做出思路2。本题我采用的是思路2。

    思路概述:先序遍历的第一个结点,在中序遍历中的位置i,i对应根节点,中序遍历中i左半部分的元素即为根节点左子树,右半部分元素即为根节点右子树。通过先序遍历先递归左子树的根节点,再递归右子树的根节点,直到递归到叶节点时打印,在递归函数出栈时依次打印根节点,就可以输出该二叉树的后序遍历。

    这题其实很简单,但是我碰上了两个大坑,1.在验证输入字符串时,不能用==,要用equals;2.注意N大于10时字符串为2位数,不能用int data = str[1].charAt(0) - '0';,要用int data = Integer.parseInt(str[1]);,否则N>10输出结果不正确。为了查出第二个大坑花了两个晚上,之前因为十位以内的输入都正确了,输入push等又太麻烦,因此调试的时候都直接跳过了输入步骤直接给前序遍历和中序遍历赋值查输出结果。查到错之后感慨万分,debug这种事还是得踏踏实实地来啊。(代码中和文后附一个自己手撕的N=30的测试样例)

     

    An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.


    Input Specification:
    Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.

    Output Specification:

     

    For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

     

    以下是具体实现(被注释的内容均为当初debug留下的印记,大坑啊):

    import java.util.ArrayList;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class TreeTraversalsAgain {
    
    	private static ArrayList<Integer> inorderTree = new ArrayList<Integer>(); // 出栈顺序,即中序遍历顺序
    	private static ArrayList<Integer> inputList = new ArrayList<Integer>(); // 入栈顺序,即先序遍历顺序
    	private static ArrayList<Integer> postorderTree = new ArrayList<Integer>(); // 后序遍历顺序
    	private static int num = 0;
    	private static Scanner indata = new Scanner(System.in);
    	
    	//30测试用例
    	private static int[] pre = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29};
    	private static int[] in = {3,5,4,8,7,6,2,1,10,9,12,14,13,15,11,0,17,19,18,21,23,22,20,16,24,25,26,28,29,27};
    
    	private static void Init() {
    
    		Stack<Integer> stack = new Stack<Integer>();
    		num = Integer.parseInt(indata.nextLine());
    		
    		for (int i = 0; i < 2 * num; i++) {
    			String[] str = indata.nextLine().split(" ");
    			if (str[0].equals("Push")) { // 这里不能用==,要用equals
    				int data = Integer.parseInt(str[1]);//这里不能用str[1].charAt(0) - '0',因为N大于10时字符串为2位数
    				inputList.add(data);
    				stack.push(data);
    			} else if (str[0].equals("Pop")) {
    				inorderTree.add(stack.pop());
    			}
    		}
    		/*
    		//测试用例
    		num = 30;
    		for(int i=0;i<30;i++){
    			inputList.add(pre[i]);
    			inorderTree.add(in[i]);
    		}
    		*/
    	}
    
    	private static void PostorderTree() {
    		int flag = 0; // input元素下标
    		int head = 0;
    		int tail = num - 1;
    		int root = Find(inputList.get(flag)); // 根节点的下标
    
    		if(root != -1){
    			Print(root, head, tail, flag);
    		}
    
    	}
    
    	// 返回指定元素的下标
    	private static int Find(int data) {
    		for (int i = 0; i < num; i++) {
    			if (inorderTree.get(i) == data) {
    				return i;
    			}
    		}
    		return -1;
    	}
    
    	private static void Print(int root, int head, int tail, int flag) {
    		int temp = flag + (root - head + 1);	//存在右子树情况下的前序遍历root对应下标
    		// 左右子树均有,递归先打印左子树,后递归打右子树
    		if (root != head && root != tail) {			
    			Print(Find(inputList.get(flag + 1)), head, root - 1, flag + 1);
    			Print(Find(inputList.get(temp)), root + 1, tail, temp);
    		}
    		// 只有右子树,递归打右子树
    		else if (root == head && tail != root) {
    			Print(Find(inputList.get(temp)), root + 1, tail, temp);
    		}
    		// 只有左子树,递归打左子树
    		else if (root == tail && head != root) {
    			Print(Find(inputList.get(flag + 1)), head, root - 1, flag + 1);
    		}
    		// 递归终点打印叶子结点,递归函数出栈过程依次打印各个根结点
    		postorderTree.add(inorderTree.get(root));
    	}
    	
    	
    	private static void Out() {
    		System.out.print("post:");
    		if (!postorderTree.isEmpty()) {
    			System.out.print(postorderTree.get(0));
    		}
    		for (int i = 1; i < postorderTree.size(); i++) {
    			System.out.print(" " + postorderTree.get(i));
    		}
    	}
    	
    	/*
    	//打印先序遍历
    	private static void Out2() {
    		System.out.print("pre:");
    		if (!inputList.isEmpty()) {
    			System.out.print(inputList.get(0));
    		}
    		for (int i = 1; i < inputList.size(); i++) {
    			System.out.print(" " + inputList.get(i));
    		}
    		System.out.println("");
    	}
    	
    	//打印中序遍历
    	private static void Out3() {
    		System.out.print("in:");
    		if (!inorderTree.isEmpty()) {
    			System.out.print(inorderTree.get(0));
    		}
    		for (int i = 1; i < inorderTree.size(); i++) {
    			System.out.print(" " + inorderTree.get(i));
    		}
    		System.out.println("");
    	}
    	*/
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Init();
    		//Out2();
    		//Out3();
    		PostorderTree();
    		Out();
    		indata.close();
    	}
    
    }
    

    附一颗N=30的复杂二叉树测试用例,你们在测试自己代码时可能可以用上:

    Push 0
    Push 1
    Push 2
    Push 3
    Pop
    Push 4
    Push 5
    Pop
    Pop
    Push 6
    Push 7
    Push 8
    Pop
    Pop
    Pop
    Pop
    Pop
    Push 9
    Push 10
    Pop
    Pop
    Push 11
    Push 12
    Pop
    Push 13
    Push 14
    Pop
    Pop
    Push 15
    Pop
    Pop
    Pop
    Push 16
    Push 17
    Pop
    Push 18
    Push 19
    Pop
    Pop
    Push 20
    Push 21
    Pop
    Push 22
    Push 23
    Pop
    Pop
    Pop
    Pop
    Push 24
    Pop
    Push 25
    Pop
    Push 26
    Pop
    Push 27
    Push 28
    Pop
    Push 29
    Pop
    Pop

    #Coding一小时,Copying一秒钟。留个言点个赞呗,谢谢你#

     

    展开全文
  • 目录1、概念2、前序遍历和中序遍历还原二叉树3、中序遍历后序遍历还原二叉树4、前序遍历和后序遍历还原二叉树 1、概念 (1)前序遍历      a、访问根节点;b、前序遍历左子树;c、前序遍历右子树。...

    1、概念

    (1)前序遍历

          a、访问根节点;b、前序遍历左子树;c、前序遍历右子树。

    (2)中序遍历

          a、中序遍历左子树;b、访问根节点;c、中序遍历右子树。

    (3)后序遍历

          a、后序遍历左子树;b、后续遍历右子树;c、访问根节点。

    2、前序遍历和中序遍历还原二叉树

    思想如下:

        a、根据前序遍历结果,第一个元素为二叉树的根结点;

        b、观察中序遍历结果,根结点左侧的为左子树,若左子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;根结点右侧的为右子树,若右子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;

        c、上面的过程是递归的。先找到当前树的根结点,然后划分为左右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

    例:

        已知前序遍历:ABDHIEJKCFLMGNO

               中序遍历:HDIBJEKALFMCNGO


    按照上述步骤先画出二叉树,然后在进行求解后序遍历结果。结果为:HIDJKEBLMFNOGCA

    练习:

    1、前序遍历:GDAFEMHZ

          中序遍历:ADEFGHMZ

        求得后序遍历结果为:AEFDHZMG

    2、前序遍历:ADCEFGHB

          中序遍历:CDFEGHAB

        求得后序遍历结果为:CFHGEDBA

    3、中序遍历和后序遍历还原二叉树

    思想如下:

        a、根据后序遍历结果,最后一个元素为二叉树的根结点;

        b、观察中序遍历结果,其中根结点左侧为左子树,若左子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;其中根结点右侧为右子树,若右子树根结点前(后)再无任何元素,则左(右)子树的左分支为空;

        c、上面的过程是递归的。先根据后序遍历结果找根结点,根结点左侧为左子树,右侧为右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。

    例:

        已知

    中序遍历:HDIBJEKALFMCNGO

    后序遍历:HIDJKEBLMFNOGCA

             

    按照上述步骤先画出二叉树,然后在进行求解前序遍历结果。结果为:

    ABDHIEJKCFLMGNO

    练习:可参考前序遍历和中序遍历的练习

    4、前序遍历和后序遍历还原二叉树

    已知前序和中序,后序和中序遍历序列之后,可以唯一确定一棵二叉树。但是,只知道前序和后序遍历序列,是无法知道哪个结点是左子树还算右子树。



    展开全文
  • 1、遍历是对树的一种最基本的运算,所谓遍历...二叉树的遍历分为:前序遍历、中序遍历后序遍历。 前序遍历:根节点、左子树、右子树 中序遍历:左子树、根节点、右子树 后序遍历:左子树、右子树、根节点 先来看一个

    1、遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。二叉树的遍历分为:层次遍历、前序遍历、中序遍历、后序遍历。

    二叉树的深度为k,则该二叉树最多有2^k - 1个结点。

    层次遍历:这个太简单,,从左到右,从上到下

    前序遍历:根节点、左子树、右子树

    中序遍历:左子树、根节点、右子树

    后序遍历:左子树、右子树、根节点

    先来看一个简单示例:


    该二叉树的深度为:4。

    层次遍历结果:1  2  3  4  5  6  7  8

    前序遍历结果:1  2  4  5  7  8  3  6

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

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

    遍历过程:以中序遍历为例,首先访问左子树(左边叶子节点 )4,即将 1 2 4 依次压栈,直到左子树为空,将4输出(出栈)。然后输出根节点2(出栈),再访问右节点5,5的左子树不为空,压栈;然后访问7,7直接输出,再将5出栈,再访问右节点8, 8的左子树为空直接输出。这样进行依次的输出顺序就是:4 2 7 5 8。

    注意:层次遍历需要用队列来实现

    2、代码测试

    注意:程序主要是对于二叉树结点的存储结构定义和二叉树的创建,最开始自己把BitTree*理解不了。然后翻了下typedef定义的知识,才明白其实就等于 struct BitNode*,一个结构体指针而已,只不过是类型别名。

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    //***************仅仅做测试,对比struct 和 typedef struct**************
    struct node{
    	int data;
    	struct node *lchild;
    	struct node *rchild;
    }mynode,*mylistnode;//这里定义的是struct node 对象和 struct node* 对象
    
    void testNode(){
    
    	mynode.data = 10;
    	mylistnode = (struct node*)malloc(sizeof(struct node) * 5);
    	mylistnode[0].data = 100;
    	mylistnode[1].data = 1000;
    	printf("test:%d %d %d \n", mynode.data, mylistnode[0].data, mylistnode[1].data);//10 100 1000
    }
    //******************************************************************
    
    
    typedef char ElemType;
    typedef struct BitNode{
    	ElemType data;
    	struct BitNode* lchild;//左结点
    	struct BitNode* rchild;//右结点
    }BitNode, *BitTree;
    //这里定义的是类型别名,*修饰类型,而不是对象,即定义了类型别名,等同于struct BitNode*
    //等同于typedef BitNode*  BitTree;
    
    void createTree(BitTree &T){
    	ElemType indata;
    	scanf("%c", &indata);
    	if (indata == '#'){
    		T = NULL;
    	}else{
    		T = (BitTree)malloc(sizeof(BitNode));
    		if (NULL == T){
    			printf("locate memery error.\n");
    			return;
    		}
    		T->data = indata;
    		createTree(T->lchild);
    		createTree(T->rchild);
    	}
    }
    
    //先续遍历二叉树
    void preOrderTraverse(BitTree T){
    	if (T){
    		printf("%c ",T->data);
    		preOrderTraverse(T->lchild);
    		preOrderTraverse(T->rchild);
    	}
    }
    //中序遍历
    void midOrderTraverse(BitTree T){
    	if (T){
    		midOrderTraverse(T->lchild);
    		printf("%c ", T->data);
    		midOrderTraverse(T->rchild);
    	}
    }
    //后序遍历
    void postOrderTraverse(BitTree T){
    	if (T){
    		postOrderTraverse(T->lchild);
    		postOrderTraverse(T->rchild);
    		printf("%c ", T->data);
    	}
    }
    /******
    				A
               B            C
    		D           E      F
    	  G  H            I  
    
    	  输入格式为: ABDG##H###CE#I##F##   总数量为2^k - 1个节点  15个
    ******/
    int main(){
    
    	testNode();
    	BitTree one;
    	printf("按先序序列输入结点序列,输入的是扩展二叉树。'#'代表其子节点空\n");
    	createTree(one);
    	printf("\n前序遍历:\n");
    	preOrderTraverse(one);
    	printf("\n中序遍历:\n");
    	midOrderTraverse(one);
    	printf("\n后序遍历:\n");
    	postOrderTraverse(one);
    	printf("\n");
    	return 0;
    }
    


    测试2:


    补充:求取二叉树的深度

    //求取二叉树的深度:根节点开始为第一层
    int getDeep(BitTree T){
    	int left, right;
    	int h = 0;
    	if (T){
    		left = getDeep(T->lchild);
    		right = getDeep(T->rchild);
    		h = left > right ? left : right;
    		h = h + 1;
    	}
    	return h;
    }




    展开全文
  • 中序遍历+先序遍历 中序遍历+后续遍历 #方法 1.中序遍历+先序遍历 算法: 1.通过先序遍历找到根节点A,再通过根节点A在中序遍历的位置找出左子树和右子树 2.在A的左子树中,找左子树的根节点(在先序中找),...
  • 二叉树的后序遍历给定一个二叉树,返回它的前序、中序、后序 遍历。示例:输入: [1,null,2,3]前序输出: [1,2,3]中序输出: [1,3,2]后序输出: [3,2,1]进阶: 递归算法很简单,你可以通过迭代算法完成吗?来源:力扣...
  • 二叉树的基本遍历方式1 二叉树的概念1.1 二叉树的Java实现2 二叉树的遍历2.1 递归实现二叉树的遍历前序遍历:递归实现中序遍历:递归实现后序遍历:递归实现2.1 循环实现二叉树的遍历前序遍历1:模拟递归的方式前序...
  • 首先,我们看看前序、中序、后序遍历的特性: 前序遍历:  1.访问根节点  2.前序遍历左子树  3.前序遍历右子树 中序遍历:  1.中序遍历左子树  2.访问根节点  3.中序遍历右子树 后序遍历: ...
  • 算法思想 如下图,右边序列为二叉树(B)的中序和后序序列...根据中序序列建立二叉树的思想,如图后序遍历二叉树的算法 void postioder(BTNode *root) { if(root!=NULL) { postioder(root->lchild); postod...
  • void dfs(int t) { //实际上就是按中序遍历的顺序访问 if(t > n) return ; dfs(t << 1); ans[t] = zx[++ idx]; dfs(t << 1 | 1); } dfs(1); 后序转层序: int idx = 0; void dfs(int t) { //...
  • 中序遍历数组转换为后序遍历数组 不能通过构建二叉树来做 import sys str_value = sys.stdin.readline().split() preOrder = list(map(int, str_value)) str_value = sys.stdin.readline().split() inOrder = list...
  • 问题描述:给出二叉树的先序,中序遍历序列,求出其后序遍历序列 作者:何知令 完成时间:2017年8月1日 输入:首行输入该二叉树节点数量,随后一行输入该二叉树前序序列,后一行输入中序序列 输出:该二叉树后序...
  • 首先,我们看看前序、中序、后序遍历的特性: 前序遍历: 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历: 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历:...
  •  中序遍历:左——>根——>右  后序遍历:左——>右——>根 自>>https://www.cnblogs.com/polly333/p/4740355.html 转载于:https://www.cnblogs.com/wumz/p/7881168.html...
  • 二叉树的遍历,二叉树的创建、前序遍历、中序遍历后序遍历) // BTree.cpp : Defines the entry point for the console application./* 作者:成晓旭 时间:2001年7月2日(9:00:00-14:00:00) 内容:完成...
  • 中序遍历的访问过程: 1.沿着根的左孩子,依次入栈,直到左孩子为空,说明已经找到可以输出的节点。 2.栈顶元素出栈并访问,若其右孩子为空,继续执行2。 3.若右孩子不空,将右子树执行1。 void InOrder(BiTree ...
  • 二叉树的遍历 例如,将中缀表达式(a+b)/c-d+e*f表示为二叉树 前序遍历 - 前缀表达式(波兰式) 根节点->左子树->右子树 示例二叉树的前序遍历 +-/+abcd*ef ...后序遍历 - 后缀表达式(逆...
  • 递归方法下的二叉树的中序遍历比较简单,大概过程就是func(root->left)????visit(root)????func(root->right),如果不使用递归的方法的话,就要用栈来模拟这个过程。 将一个递归函数转换成为非递归的解决方法...
  • 树的遍历顺序大体分为三种:前序遍历(先根遍历、先序遍历),中序遍历(中根遍历),后序遍历(后根遍历)。--左总是在右前,根=》前、中、后 如图所示二叉树: 前序遍历:前序遍历可以记...
  • 105. 从前序与中序遍历序列构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回...
  • 二叉树的遍历是指不重复地访问二叉树中所有结点,主要指非空二叉树,对于空二叉树则结束返回,二叉树的遍历主要包括前序遍历、中序遍历后序遍历 前序遍历:首先访问根结点,然后遍历左子树,最后遍历右子树(根...
  • /* 树中已知先序和中序求后序。  如先序为:abdc,中序为:bdac . ...中的a就为根节点,由于中序遍历为:左中右,再根据根节点a,我们就可以知道,左子树包含 元素为:db,右子树包含元素:c,再把后序进行
  • 后序遍历 后序遍历要求左右子树均完成后才对自身进行访问。入栈时,先将右子树(若存在)入栈再将左子树(若存在)入栈,然后指向左孩子(若存在左孩子,否则指向右孩子)。在对这个部分结点构成的栈进行出栈操作时...
  • 后序遍历:先左孩子节点,再遍历右孩子节点,再遍历左孩子节点。利用递归实现。(图1-3,遍历后:7-8-3-4-1-5-6-2-0) 注意:前三种遍历是以深度优先,比如前序遍历,同一层节点,左孩子没有遍历结束,不会遍历右...
  • 前序好理解点,后序是前序的几乎完全相反体,但是有点难理解,可能是脑子不过弯。 参考自别人的CSDN博客 前+中序: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode...
  • 二叉树遍历遍历是对树的一种最基本的运算,所谓遍历...设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 789
精华内容 315
关键字:

中序遍历转后序遍历