精华内容
下载资源
问答
  • 前序中序创建二叉树: preOrder:{1,2,4,7,3,5,6,8} inOrder:{4,7,2,1,5,3,8,6}

    前序中序创建二叉树:
    preOrder:{1,2,4,7,3,5,6,8}
    inOrder:{4,7,2,1,5,3,8,6}

    • 找到中序中和先序相同的节点(i=3)、leftLen=i、rightLen=len-leftLen-1;
    • 将先序和中序分为两半,递归调用:(preS+1,inS,leftLen,preorder,inorder) 和 (preS+leften+1,ins+leftlen+1,rightlen.preorder,inorder)

    递归实现:

    public static TreeNode createTree(int preS,int inS,int length,int[]preorder,int[]inorder){
            if (preorder == null || preorder.length ==0){
                return null;
            }
            TreeNode node = new TreeNode(preorder[preS]);
            if(length ==1 && preorder[preS] == inorder[inS])
                return node;
            int i = 0;
            //找到分界点
            while (i <=length-1 && preorder[preS]!= inorder[inS+i])
                i++;
            //左半边长度
            int leftLen = i;
            //右半边长度
            int rightLen = length-leftLen-1;
            if(leftLen>=1){
                node.left=createTree(preS+1,inS,leftLen,preorder,inorder);
            }
            if(rightLen>=1){
                node.right=createTree(preS+leftLen+1,inS+leftLen+1,rightLen,preorder,inorder);
            }
            return node;
        }

    中序后序创建二叉树:
    inOrder:{4,7,2,1,5,3,8,6}
    postOrder={7,4,2,5,8,6,3,1}

    • 找到中序中和后序相同的节点(i=3);
    • 将中和后序分为两半,递归调用:(inS,postE-rightLen-1,leftLen,inorder,postorder)、createTree(inS+leftLen+1,postE-1,rightLen,inorder,postorder)

    递归实现:

    public  TreeNode createTree(int inS,int postE,int length,int[]inorder,int[]postorder){
            if (inorder == null || inorder.length ==0){
                return null;
            }
            TreeNode node = new TreeNode(postorder[postE]);
            if(length ==1 && inorder[inS] == postorder[postE])
                return node;
            int i = 0;
            //找到分界点
            while (i <=length-1 && postorder[postE]!= inorder[inS+i])
                i++;
            //左半边长度
            int leftLen = i;
            //右半边长度
            int rightLen = length-leftLen-1;
            if(leftLen>=1){
                node.left=createTree(inS,postE-rightLen-1,leftLen,inorder,postorder);
            }
            if(rightLen>=1){
                node.right=createTree(inS+leftLen+1,postE-1,rightLen,inorder,postorder);
            }
            return node;
        }
    展开全文
  • 前序中序创建二叉树(用中序后序创建二叉树)

    千次阅读 多人点赞 2019-04-05 22:52:23
    前序中序创建 因为前序遍历的顺序是 根 , 左 ,右。 中序的遍历是 左 根 右。 我们会很不好想,但我们可以用前序和中序把上面那个二叉树的遍历一边 前序遍历:ABDEHCFG 中序遍历:DBEHAFCG 然后根据这我们来想 ...

    定义二叉树结点
    在这里插入图片描述
    比如就拿这个二叉树
    在这里插入图片描述

    前序中序创建

    因为前序遍历的顺序是 根 , 左 ,右。
    中序的遍历是 左 根 右。
    我们会很不好想,但我们可以用前序和中序把上面那个二叉树的遍历一边

    	前序遍历:ABDEHCFG
    	中序遍历:DBEHAFCG
    

    然后根据这我们来想
    创建的时候,值都是以数组的形式传进来,所以找到根节点,前序和中序左子树个数一定相等,都是r。
    前序和中序创建左子树的时候,挨个往后走就行,传的数组长度也就是个数就是r,左子树的个数,到右子树时。此时左子树创建完,所以前序要跳过r个元素,也就是创建左子树的个数,并加上根节点,也就是r+1.,创建右子树时个数就要减去根+左子树的个数。中序也是如此。

    在这里插入图片描述
    程序一开始,要先找到r的大小,也就是中序遍历和前序遍历时根结点的位置。
    在这里插入图片描述

    中序后序创建

    与之前的道理是相似的,先找到根节点所在位置,也就是左子树个数
    在这里插入图片描述
    然后找到根的值,也就是后序数组中的最后一个,然后道理相同,先左,再右
    在这里插入图片描述

    展开全文
  • 前序中序创建二叉树

    2012-03-20 00:14:34
    前序中序可以唯一确定一课二叉树前序可以确定根节点在中序中的位置,在递归简历左右子树。         #include "stdafx.h" #include "stdio.h" struct node { char value; node *left; node *...

     前序和中序可以唯一确定一课二叉树,前序可以确定根节点在中序中的位置,在递归简历左右子树。

     

     

     

     

    #include "stdafx.h"
    #include "stdio.h"


    struct node
    {
    char value;
    node *left;
    node *right;



    };

    node * creat(char *pre,char *mid,int n)
    {
    if(n==0)
    return NULL;
    int k=0;
    while(pre[0]!=mid[k])k++;

    node * root=new node;
    root->value=mid[k];

    root->left=creat(pre+1,mid,k);
    root->right=creat(pre+k+1,mid+k+1,n-k-1);

    return root;


    }


    int main(int argc, char* argv[])
    {
    char *pre="ABCDEF";
    char *mid="CBDEAF";
    node *tree=creat(pre,mid,6);


    return 0;
    }

    展开全文
  • 前序中序创建二叉树 后序中序创建二叉树 层序中序创建二叉树

    前序中序创建二叉树


    先写一个只能保存单个字符的算法:

    /**
     *@param pre:前序序列
     *@param in:后序序列
     */
    template <class T> BinaryTree<T>* CreateBinaryTreeByPreOrderInOrder(string pre, string in) {
    	if(pre.length() == 0) {
    		return NULL;
    	}
    	int root = in.find(pre[0]);
    	BinaryTree<T> *tree = (BinaryTree<T> *)malloc(sizeof(BinaryTree<T>));
    	tree -> data = pre[0];
    	tree -> lchild = CreateBinaryTreeByPreOrderInOrder<char>(pre.substr(1, root), in.substr(0, root));
    	tree -> rchild = CreateBinaryTreeByPreOrderInOrder<char>(pre.substr(root + 1), in.substr(root + 1));
    	return tree;
    }
    

    算法很简单,一下就能看懂,但是局限性也很大,就是二叉树的数据只能保存单个字符,这样模板毫无作用,但我想写成通用的,因此我有了第一个想法:
    1、就是编写一个类似 “substr” 的函数,用来提取 “*T” 的部分数据并返回。但是很快我就否定了,因为这样需要大量的 new ,至少我必须用大量的 new。于是我有了第二个想法,给函数再添加四个参数。
    2、上述代码中, “substr” 使用了两次,因此我直接把这两次使用的四个参数作为函数参数,也相当于变相的实现的 “substr”。
    从而新的代码如下(因此序列长度是一样的,因此给定长度 length, 则可以省去一个参数):

    template <class T> BinaryTree<T>* CreateBinaryTreeByPreOrderInOrder(const T *pre, int s1, const T *in, int s2, int length) {
    	if(length == 0) {
    		return NULL;
    	}
    	int ltreeLength = 0;
    	int rtreeLength = 0;
    	for(int i = s2; i < s2 + length; i++) {
    		if(in[i] == pre[s1]) {
    			break;
    		}
    		ltreeLength++;
    	}
    	rtreeLength = length - ltreeLength - 1;
    	BinaryTree<T> *tree = (BinaryTree<T> *)malloc(sizeof(BinaryTree<T>));
    	tree -> data = pre[s1];
    	tree -> lchild = CreateBinaryTreeByPreOrderInOrder<T>(pre, s1 + 1, in, s2, ltreeLength);
    	tree -> rchild = CreateBinaryTreeByPreOrderInOrder<T>(pre, s1 + 1 + ltreeLength, in, s2 + 1 + ltreeLength, rtreeLength);
    	return tree;
    }
    
    /**
     *前序中序创建二叉树函数接口
     */
    template <class T> BinaryTree<T>* CreateBinaryTreeByPreOrderInOrder(const T *pre, const T *in, int length) {
    	return CreateBinaryTreeByPreOrderInOrder<T>(pre, 0, in, 0, length);
    }
    

    后序中序创建二叉树


    后序中序创建二叉树的思路和前序中序创建二叉树的思路差不多,代码如下:

    template <class T> BinaryTree<T>* CreateBinaryTreeByPostOrderInOrder(const T *post, int s1, const T *in, int s2, int length) {
    	if(length == 0) {
    		return NULL;
    	}
    	int ltreeLength = 0;
    	int rtreeLength = 0;
    	for(int i = s2; i < s2 + length; i++) {
    		if(in[i] == post[s1 + length - 1]) {
    			break;
    		}
    		ltreeLength++;
    	}
    	rtreeLength = length - ltreeLength - 1;
    	BinaryTree<T> *tree = (BinaryTree<T> *)malloc(sizeof(BinaryTree<T>));
    	tree -> data = post[s1 + length - 1];
    	tree -> lchild = CreateBinaryTreeByPostOrderInOrder<T>(post, s1, in, s2, ltreeLength);
    	tree -> rchild = CreateBinaryTreeByPostOrderInOrder<T>(post, s1 + ltreeLength, in, s2 + 1 + ltreeLength, rtreeLength);
    	return tree;
    }
    
    /**
     *后序中序创建二叉树函数接口
     */
    template <class T> BinaryTree<T>* CreateBinaryTreeByPostOrderInOrder(const T *post, const T *in, int length) {
    	return CreateBinaryTreeByPostOrderInOrder<T>(post, 0, in, 0, length);
    }
    

    层序中序创建二叉树


    层序中序创建二叉树,总的思路和前两个差不多,但是因为层序中左右子树的序列是交错的,因此需要做一些处理。
    首先可以肯定的是每次的递归只返回一个节点,但是因为层序的左右子树的序列是交错的,因此必须设置一个标识,用来标识是否已经找到左子树,或者已经找到右子树,或者找到根节点,否则的话,即使已经找到某个节点,那么递归返回后,由于层序左右子树序列的交错,将会有新的节点再次进入与之前同样的递归过程,从而导致之前找到的节点被新找到的节点所覆盖,具体情况,以层序序列:“ABCDE”,中序序列:“DBACE”,构成的二叉树手动模拟一下即可。
    层序中序创建二叉树代码如下:

    template <class T> BinaryTree<T>* CreateBinaryTreeByLevelOrderInOrder(const T *level, int s1, int e1, const T *in, int s2, int e2) {
    	int root;
    	bool isFindRoot = false;
    	bool isFindLTree = false;
    	bool isFindRTree = false;
    	BinaryTree<T> *tree = (BinaryTree<T> *)malloc(sizeof(BinaryTree<T>));
    	for(int i = s1; i <= e1; i++) {
    		for(int j = s2; j <= e2; j++) {
    			if(!isFindRoot && level[s1] == in[j]) {
    				root = j;
    				isFindRoot = true;
    				tree -> data = level[s1];
    				tree -> lchild = NULL;
    				tree -> rchild = NULL;
    				break;
    			}
    			//在层序中查找中序中左子树的根节点
    			if(!isFindLTree && level[i] == in[j] && j < root) {
    				tree -> lchild = CreateBinaryTreeByLevelOrderInOrder<T>(level, i, e1, in, s2, root - 1);
    				isFindLTree = true;
    				break;
    			}
    			//在层序中查找中序中右子树的根节点
    			if(!isFindRTree && level[i] == in[j] && j > root) {
    				tree -> rchild = CreateBinaryTreeByLevelOrderInOrder<T>(level, i, e1, in, root + 1, e2);
    				isFindRTree = true;
    				break;
    			}
    		}
    		//建立完成
    		if(isFindRoot && isFindLTree && isFindRTree) {
    			break;
    		}
    	}
    	return tree;
    }
    
    /**
     *层序中序创建二叉树函数接口
     */
    template <class T> BinaryTree<T>* CreateBinaryTreeByLevelOrderInOrder(const T *level, const T *in, int length) {
    	return CreateBinaryTreeByLevelOrderInOrder<T>(level, 0, length - 1, in, 0, length - 1);
    }
    

    要说一下的是,递归结束条件是 s2 == e2, 但是此时内部循环只执行一次,而外部循环除了 i == s1 时,均不满足内层循环的三个判断,因此不会再进行递归,所以可以省略,但是写上的话,倒也可以提升一点运行效率的。

    本次记录到此结束!

    展开全文
  • 题目要求我们求树的后序遍历,因此这道题的关键就是根据前序遍历和中序遍历来创建一棵二叉树。流程如下: 1根据前序遍历来确定每次根节点的位置,因为前序遍历先访问的是根节点,所以前序遍历第一个位置就是根节点...
  • #include <stdio.h> #include <string.h> #define TREELEN 7 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild;...
  • 前序中序创建二叉树--Java和C语言思路代码Java版本版本1:低效,不借助其他工具类版本2借助Arrays.copyOfRange(),代码简洁C语言版本 思路 1. 找出根节点(先序的第一个节点是根节点) 2. 分出左右子树(再根据...
  • 先序中序建立二叉树 急~~ 1二叉树中存储的数据范围仅限于26个英文字母 2程序要提示用户从键盘分别输入二叉树的先序和中序序列接受输入后调用相应的函数完成二叉树的创建 3成功创建二叉树后程序自动输出该二叉树的...
  • 前序中序建立二叉树

    2021-03-09 11:05:26
    //先序和中序结果创建二叉树 #include <iostream> #include<vector> using namespace std; struct BinaryNode { int val; BinaryNode* left; BinaryNode* right; }; BinaryNode* createTree(vector&...
  • 通过前序中序遍历生成二叉树 通过中序和后序遍历生成二叉树 小伙伴们需要自取,有帮助的话可以点个赞~ 注:本文中提供的代码均为完整代码,放入C++工程后可直接运行。 代码实现 用C++类(class)实现,共包含三个...
  • 1.根据树的前序遍历和中序遍历创建一棵二叉树 思路: 1)在前序中找到根的值。preorder[0]. 2)在中序中找到根的值所在的下标,下标即为左子树的结点个数。 3)切出左子树的前序中序。preorder,跳过1,截取的...
  • 根据前序中序创建二叉树

    千次阅读 2017-11-04 20:42:12
    //前序第一个是根,所以找前序第一个,建立根节点 (*node)->data = preorder[Index]; //root find_in = find_index(inorder,preorder[Index]); //找到该节点在序列中对应的位置 find_pre = 1 ; //原则就是...
  • //创建根节点,根节点肯定是前序遍历的第一个数 TreeNode* head = new TreeNode(pre[0]); //找到中序遍历根节点所在位置,存放于变量gen中 int gen = 0; for (int i = 0; i; i++) { if (in[i] == ...
  • 根据如图创建二叉树: 先序遍历为: "A B C D E F G H" 中序遍历为: "C B E D F A G H" 后序遍历为: "C E F D B H G A" 代码如 下: #include<stdio.h> #include<stdlib.h> #include<...
  • 这里的实现默认二叉树中的所有结点元素的值都是唯一的。 根据前序中序遍历字符串创建二叉树 根据后序、中序遍历字符串创建二叉树
  • 上次记录了广义表生成二叉树的过程,我们也可以通过前序中序,或者中序和后序,来构建一...获取前序字符串的第一个字符A,它作为当前根节点,然后扫描中序字符串,找到A的位置,创建根节点存储结构。 然后在中序字符
  • Java根据前序中序遍历创建二叉树 根据中序、后序遍历创建二叉树代码实现 (包括前序中序、后序遍历代码实现) import java.util.Scanner; class TreeNode {//树节点 int val; TreeNode left; TreeNode...
  • 此代码可以正常运行,下附有运行区,是实实在在的类C语言 #include <stdlib.h> #include <stdio.h> #define STACKINITSIZE 20//栈初始空间大小 #define INCREASEMENT 10//栈...//二叉树节点数据 BiT...

空空如也

空空如也

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

前序中序创建二叉树