精华内容
下载资源
问答
  • 构建二叉树

    2021-03-29 12:48:53
    通过前序遍历序列和中序遍历序列及后序遍历 构建二叉树

    根据前序遍历构建二叉树

    如何构建二叉树呢,我们如果只单纯通过前序遍历,很难确定唯一的二叉树,因为会有很多种样式。

    例如:前序序列为 A B C就可以构建很多的二叉树。

    在这里插入图片描述
    所以我们要想通过前序遍历构建唯一的二叉树,需要将空节点也带上,这样便可以构建唯一的二叉树。

    问题

    牛客网链接:二叉树构建和遍历
    在这里插入图片描述

    思路

    我们需要拿到一段二叉树的前序序列,首先可以得到头结点,’#‘代表结点为空,当遇到’#'的时候,便返回。知道将序列使用完成。
    如上题目:构建的二叉树样子应该为:
    在这里插入图片描述
    实现:

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    /**
     *
     */
     //构建结点
    class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(char val) {
            this.val = val;
        }
    }
    
    
    public class Main {
    	//构建二叉树
        public static TreeNode buildTree(List<Character> preorder) {
            if (preorder.isEmpty()) {
                return null;
            }
            char rootval = preorder.remove(0);
            if (rootval == '#') {
                return null;
            }
            TreeNode root = new TreeNode(rootval);
            root.left = buildTree(preorder);
            root.right = buildTree(preorder);
            return root;
        }
        //中序遍历
        public static void inorder(TreeNode root) {
            if (root == null) {
                return;
            }
            inorder(root.left);
            System.out.println(root.val);
            inorder(root.right);
        }
        
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextLine()) {
                String s = scanner.nextLine();
                char[] p = s.toCharArray();
    
                List<Character> list = new ArrayList<>();
                for (char c : p) {
                    list.add(c);
                }
    
                TreeNode root = buildTree(list);
    
                inorder(root);
    
                System.out.println();
            }
        }
    }
    

    根据前序遍历+中序遍历

    当我们已知前序和中序遍历的序列的时候,是否能构建唯一的二叉树呢?当然是可以的。
    已知前序序列,我们可以找到根节点,然后在中序序列中确定左子树和右子树个数。
    如此循环往复构建二叉树。

    题目:

    链接:
    105. 从前序与中序遍历序列构造二叉树
    在这里插入图片描述

    class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length == 0) {
                return null;
            }
            int rootVal = preorder[0];
            TreeNode root = new TreeNode(rootVal);
    
            int size = 0;
            for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == rootVal) {
                    size = i;
                }
            }
            
            //构建左子树
            int[] leftpreorder = Arrays.copyOfRange(preorder, 1, size + 1);
            int[] leftinorder = Arrays.copyOfRange(inorder, 0, size);
            root.left = buildTree(leftpreorder, leftinorder);
    
            //构建右子树
            int[] rightpreorder = Arrays.copyOfRange(preorder, size + 1, preorder.length);
            int[] rightinorder = Arrays.copyOfRange(inorder, size + 1, inorder.length);
            root.right = buildTree(rightpreorder, rightinorder);
            return root;
        }
    }
    

    根据后序遍历+中序遍历

    和前序遍历与中序遍历求解二叉树类似,后序遍历我们也可以得到根节点…

    题目:

    106. 从中序与后序遍历序列构造二叉树

    在这里插入图片描述

    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (postorder.length == 0) {
                return null;
            }
            int rootVal = postorder[postorder.length - 1];
            TreeNode root = new TreeNode(rootVal);
            int size = 0;
            for (int i = 0; i < inorder.length; i++) {
                if (inorder[i] == rootVal) {
                    size = i;
                }
            }
    
            int[] leftPostorder = Arrays.copyOfRange(postorder, 0, size);
            int[] leftInorder = Arrays.copyOfRange(inorder, 0, size);
            root.left = buildTree(leftInorder, leftPostorder);
            
            int[] rightPostorder = Arrays.copyOfRange(postorder,size,postorder.length-1);
            int[] rightInorder = Arrays.copyOfRange(inorder,size+1,inorder.length)  ;
            root.right = buildTree(rightInorder, rightPostorder);
            
            return root; 
        }
    }
    

    我们那前序遍历和后序遍历构建不出唯一确定的二叉树,因为两种都只能确定根节点。

    展开全文
  • 建立二叉树

    2018-04-15 15:34:16
    建立二叉树,其实与二叉树的遍历类似,把打印结点的部分换成生成结点、给结点赋值的操作即可比如代码://利用前序遍历序列AB#D##C#建立二叉树 void CreateBiTree(TreeNode*T) { typename ch; scanf("%c"...

    建立二叉树,其实与二叉树的遍历类似,把打印结点的部分换成生成结点、给结点赋值的操作即可

    比如代码:

    //利用前序遍历序列AB#D##C#建立二叉树
    void CreateBiTree(TreeNode*T)
    {
    	typename ch;
    	scanf("%c", ch);
    	if (ch == '#');
    	T = NULL;
    	else {
    		TreeNode*T = new TreeNode;
    		if (!T)//检查T结点是否创建成功
    			exit(OVERFLOW);
    		T->val = ch;//生成根结点
    		CreateBiTree(T->left);//构建左子树
    		CreateBiTree(T->right);//构建右子树
    	}
    }

    展开全文
  • 通过递归的方法根据前序序列构建二叉树、根据后序序列构建二叉树、根据前序+中序序列构建二叉树、根据中序+后序序列构建二叉树。 一、二叉树结点定义以及一些基本函数定义 ①二叉树结点: // 二叉树结点结构体 ...

    通过递归的方法构建二叉树.

    一、二叉树结点定义以及一些基本函数定义

    ①二叉树结点:

    // 二叉树结点结构体 			定义在BinaryTree.h文件中
    #pragma once
    #include<iostream>
    using namespace std;
    
    template <class T>
    struct BinTNode
    {
    	T data;
    	BinTNode<T>* lchild, * rchild;
    	BinTNode() :lchild(NULL), rchild(NULL) {}
    	BinTNode(T x, BinTNode<T>* l = NULL, BinTNode<T>* r = NULL)
    		:data(x), lchild(l), rchild(r) {}
    };
    

    ②二叉树类:

    //二叉树类 					同样定义在BinaryTree.h文件中
    template <class T>
    class BinaryTree
    {
    protected:
    	BinTNode<T>* root;//根结点
    	T tag;//输入终止符
    public:
    	BinaryTree() :root(NULL) {}
    	BinaryTree(T x) :tag(x), root(NULL) {}
    	~BinaryTree() { DestroyTree(root); }		
    	BinTNode<T>* GetRoot(BinTNode<T>* p) { p = root; return p; }//取得根节点的地址
    	void DestroyTree(BinTNode<T>* tree);						//删除一颗树
    	void CreateBinTree1(BinTNode<T>*& tree,char* pre);	//根据前序序列建立二叉树
    	void CreateBinTree2(BinTNode<T>*& tree,char* post);	//根据后序序列建立二叉树
    	void CreateBinTree3(BinTNode<T>*& tree, char* pre, char* in,int n);//根据前序+中序建立二叉树(其中n为序列长度)
    	void CreateBinTree4(BinTNode<T>*& tree, char* in, char* post, int n);//根据中序+后序建立二叉树(其中n为序列长度)
    	void OutputBinTree(BinTNode<T>*& tree);				//按照前序序列打印二叉树
    };
    

    二、创建二叉树的函数:

    ①根据前序序列创建二叉树:

    递归法建立,根据书上的代码做了一些改变,但是算法不变。

    // 根据前序序列创建二叉树
    template <class T>
    //tree是要建立树的结点,pre是前序序列
    void BinaryTree<T>::CreateBinTree1(BinTNode<T>*& tree, char* pre)
    {
    	T tmp;
    	tmp = *pre;						
    	for (int i = 0; i < strlen(pre); i++)	//读取完字符,就把所有字符前移一位,覆盖掉第一个字符
    		pre[i] = pre[i + 1];				//以确保后面每次调用第一个字符不与之前重复
    	if (tmp != tag)						//正向写入树中
    	{
    		tree = new BinTNode<T>(tmp);
    		CreateBinTree1(tree->lchild, pre);
    		CreateBinTree1(tree->rchild, pre);
    	}
    	else	tree = NULL;
    }
    

    ②根据后序序列创建二叉树:

    错误的方法:
    很多人会以为只需要调①中间建立的三步的顺序就行了,但是这样是错误的,因为后序序列为“左右根”,建立第一个一定读取“#”,也就是空结点,程序直接把树置空了,就无法再进行下去了。
    正确的方法:
    我们把用户输入的后序序列反向读取,这样就由“左右根”的顺序变为了“根右左”,这样就解决了读取的第一个元素直接将树置空的问题。

    有了思路后,就可以这样建立:

    // 根据后序序列创建二叉树
    template <class T>
    //tree是要建立树的结点,post是后序序列
    void BinaryTree<T>::CreateBinTree2(BinTNode<T>*& tree, char* post)
    {
    	T tmp;
    	int l = strlen(post) - 1;
    	tmp = post[l];
    	post[l] = '\0';		//用完就封口,使得下一次l的值变为前一位
    	if (tmp != tag)					//反向写入树中
    	{
    		tree = new BinTNode<T>(tmp);
    		CreateBinTree2(tree->rchild,post);
    		CreateBinTree2(tree->lchild,post);
    	}
    	else tree = NULL;
    }
    

    ③根据前序+中序序列创建二叉树:

    前序:根左右
    中序:左根右
    根据序列的差异我们可以得出以下步骤:
    1.找前序序列第一个结点,它是这棵树的根节点。
    2.在中序中找这个结点,它左边就是左子树中序序列,右边就是右子树中序序列。
    3.计算中序中确定的左子树结点个数n,在前序中除了根节点外的结点中取前n个,就是左子树的前序序列,剩余就是右子树前序序列。
    4.由得到的左子树和右子树的前序、中序序列继续递归。当左右子树为空时递归结束。

    举个例子:
    前序序列:ABDC
    中序序列:BDAC
    由前序序列知,A为根节点。
    在中序序列中查找A,找到它左边BD就是左子树中序序列,右边C就是右子树中序序列。
    根据左子树中序序列BD的结点个数2,在前序序列除了根节点外的结点中找到前2个:BD就是左子树的前序序列,剩余C就是右子树的前序序列。
    继续递归,左子树前序序列第一个是B,那么B就是左子树根节点。
    在左子树中序序列BD中找到B,其左边没有结点,那么B的左子树为空。其右子树中序序列为:D。
    在前序序列BD中找,除了根节点B以外的前0个节点是左子树前序序列,此处即左子树为空。剩余D就是右子树前序序列。
    A的右子树为C。
    这样就解得了二叉树的结构。
    接下来我们只需要翻译以上算法即可。
    代码如下:

    // 根据前序+中序序列创建二叉树
    template <class T>
    //tree是要建立树的结点,pre是前序序列,in是中序序列,n是序列长度
    void BinaryTree<T>::CreateBinTree3(BinTNode<T>*& tree, char* pre, char* in, int n)
    {
    	if (n <= 0) return;//递归结束条件,序列长度小于等于0
    	T tmp = *pre;//前序第一个节点必为根节点
    	tree = new BinTNode<T>(tmp);
    	int m = 0;
    	for (; m < n; m++)//找到根节点在中序中的下标
    	{
    		if (tmp == in[m])
    			break;
    	}
    	//根据下标m分割序列,得到子树序列
    	CreateBinTree3(tree->lchild, pre + 1, in, m);
    	CreateBinTree3(tree->rchild, pre + m + 1, in + m + 1, n - m - 1);
    }
    

    ④根据中序+后序序列创建二叉树:

    算法同③,只是获取根节点的方式从前序第一个变成了后序最后一个。
    代码如下:

    // 根据中序+后序序列创建二叉树
    template <class T>
    //tree是要建立树的结点,in是中序序列,post是后序序列,n是序列长度
    void BinaryTree<T>::CreateBinTree4(BinTNode<T>*& tree, char* in, char* post, int n)
    {
    	if (n <= 0) return;//递归结束条件,序列长度小于等于0
    	T tmp = post[n - 1];//后序最后一个节点必为根节点
    	tree = new BinTNode<T>(tmp);
    	int m = 0;
    	for (; m < n; m++)//获得根节点在中序的下标
    	{
    		if (tmp == in[m])
    			break;
    	}
    	//根据下标m分割序列,得到子树序列
    	CreateBinTree4(tree->lchild, in, post, m);
    	CreateBinTree4(tree->rchild, in + m + 1, post + m, n - m - 1);
    }
    

    三、根据前序序列打印二叉树:

    // 根据前序序列打印二叉树
    template <class T>
    void BinaryTree<T>::OutputBinTree(BinTNode<T>*& tree)
    {
    	if (tree != NULL)
    	{
    		cout << tree->data;
    		if (tree->lchild != NULL || tree->rchild != NULL)
    		{
    			cout << "(";
    			OutputBinTree(tree->lchild);
    			cout << ",";
    			OutputBinTree(tree->rchild);
    			cout << ")";
    		}
    	}
    }
    

    四、测试程序:

    // 在BinaryTree.cpp文件中
    #include"BinaryTree.h"
    #include<string>
    int main()
    {
    	int mode = 0;
    	BinaryTree<char> Tree('#');//创建一个以“#”为终止符的树
    	BinTNode<char>* p = NULL;
    	Tree.GetRoot(p);//获取根节点地址
    	//只通过前序或后序序列建立二叉树时只用到了list1
    	//通过结合前序+中序或者中序+后序建立二叉树时用list1和list2分别存储两个序列
    	char* list1 = new char[100], * list2 = new char[100];
    	string st1, st2;
    	cout << "请输入选项:" << endl;
    	cout << "【1】根据前序序列建立二叉树" << endl;
    	cout << "【2】根据后序序列建立二叉树" << endl;
    	cout << "【3】根据前序+中序建立二叉树" << endl;
    	cout << "【4】根据中序+后序建立二叉树" << endl;
    	cin >> mode;
    	int n = 0;
    	if (mode == 3 || mode == 4)//选择了同时根据两个序列构建二叉树
    	{
    		cout << "请输入第一个序列:(无空节点,且每个节点之间无需用空格间隔开)" << endl;
    		cin >> st1;
    		list1 = (char*)st1.data();//将string类型转化为char*
    		cout << "请输入第二个序列:(无空节点,且每个节点之间无需用空格间隔开)" << endl;
    		cin >> st2;
    		list2 = (char*)st2.data();
    	}
    	else//选择了根据前序或后序建立二叉树
    	{
    		cout << "请输入序列建立树:((#)是空节点,且每个节点之间无需用空格间隔开)" << endl;
    		cin >> st1;
    		list1 = (char*)st1.data();//将string类型转化为char*
    	}
    	switch(mode)
    	{
    		case 1:
    			Tree.CreateBinTree1(p, list1);
    			break;
    		case 2:
    			Tree.CreateBinTree2(p, list1);
    			break;
    		case 3:
    			Tree.CreateBinTree3(p, list1, list2, n);
    			break;
    		case 4:
    			Tree.CreateBinTree4(p, list1, list2, n);
    			break;
    		default:
    			cout << "输入参数错误!" << endl;
    	}
    	cout << "建立的树为:" << endl;
    	Tree.OutputBinTree(p);
    	return 0;
    }
    

    五、结果展示:

    界面:

    在这里插入图片描述

    根据后序建立二叉树:

    在这里插入图片描述

    根据前序+中序建立二叉树:(注意:输入的节点值不能相同,只有这样才能满足根据前序+中序或者中序+后序能建立唯一二叉树的要求。)

    在这里插入图片描述
    以上是我本人数据结构课程最近的一次作业所要求实现的功能,希望对大家有所帮助。
    本人水平有限,如有出错之处,欢迎指正,谢谢大家。
    最后一次修订:2020年10月29日.

    展开全文
  • 二叉树中序遍历与前序遍历构建二叉树二叉树中序遍历和后续遍历构建二叉树二叉树中序遍历与前序遍历构建二叉树二叉树中序遍历与后序遍历构建二叉树 主要是利用分治的思想,根据中序遍历的结果找到分治的左子树和右...

    主要是利用分治的思想,根据中序遍历的结果找到分治的左子树和右子树序列,然后递归实现树的重建。

    1.二叉树中序遍历与前序遍历构建二叉树

    1. 从前序与中序遍历序列构造二叉树
      根据一棵树的前序遍历与中序遍历构造二叉树。

    注意:

    可以假设树中没有重复的元素。

     public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (inorder == null || preorder == null || inorder.length < 1 || preorder.length < 1) return null;
            Map<Integer, Integer> inorderIndexMap = new HashMap<>();// 构建二叉树中序遍历数值和index的hash表,因为元素都不相同
            for (int i = 0; i < inorder.length; i++) {
                inorderIndexMap.put(inorder[i], i);
            }
            return helper(0, inorder.length - 1, 0, preorder.length - 1, inorder, preorder, inorderIndexMap);
    
        }
    
    
        public TreeNode helper(int inStart, int inEnd, int preStart, int preEnd, int[] inorder, int[] preOrder, Map<Integer, Integer> indexMap) {
            if (inStart > inEnd || preStart > preEnd) return null;// 结束条件
            TreeNode node = new TreeNode(preOrder[preStart]);
            int mid = indexMap.get(preOrder[preStart]);
            //容易知道 左子树中序遍历的开始和结束下标 [inStart, mid-1], 前序遍历的左边的元素个数和中序遍历左边的元素个数相同,容易得到前序遍历的start和end
            node.left = helper(inStart, mid - 1, preStart + 1, preStart + 1 + (mid - 1 - inStart), inorder, preOrder, indexMap);
            //容易知道 右子树中序遍历的开始和结束下标 mid+1, inEnd,
            node.right = helper(mid + 1, inEnd, preEnd - (inEnd - mid - 1), preEnd, inorder, preOrder, indexMap);
            return node;
        }
    

    2. 二叉树中序遍历与后序遍历构建二叉树

    1. 从中序与后序遍历序列构造二叉树
      根据一棵树的中序遍历与后序遍历构造二叉树。

    这里是引用

    可以假设树中没有重复的元素。

    /**
         * 分治的思想
         * @param inorder
         * @param postOrder
         * @return
         */
        public TreeNode buildTree(int[] inorder, int[] postOrder) {
            if (inorder == null || postOrder == null || inorder.length < 1 || postOrder.length < 1) return null;
            Map<Integer, Integer> inorderIndexMap = new HashMap<>();// 构建二叉树中序遍历数值和index的hash表
            for (int i = 0; i < inorder.length; i++) {
                inorderIndexMap.put(inorder[i], i);
            }
            return helper(0, inorder.length - 1, 0, postOrder.length - 1, inorder, postOrder, inorderIndexMap);
        }
    
        public TreeNode helper(int inStart, int inEnd, int postStart, int postEnd, int[] inorder, int[] postOrder, Map<Integer, Integer> indexMap) {
            if (inStart > inEnd || postStart > postEnd) return null;// 结束条件
            TreeNode node = new TreeNode(postOrder[postEnd]);
            int mid = indexMap.get(postOrder[postEnd]);
            //容易知道 左子树中序遍历的开始和结束下标 [inStart, mid-1],
            // 后续遍历的左边的元素个数和中序遍历左边的元素个数相同,所以后续遍历的左边的结束下标是mid-1 - inStart+postStart
            node.left = helper(inStart, mid - 1, postStart, mid - 1 - inStart + postStart, inorder, postOrder, indexMap);
            //容易知道 右子树中序遍历的开始和结束下标 mid+1, inEnd,
            node.right = helper(mid + 1, inEnd, mid - 1 - inStart + postStart + 1, postEnd - 1, inorder, postOrder, indexMap);
            return node;
        }
    
    展开全文
  • 建立二叉树的几种方法: 一、已知先序遍历顺序,构建二叉树。(链式存储) 二、已知层次遍历顺序,构建二叉树。(链式存储) 三、已知节点关系,建立二叉树(邻接表存储) 四、已知先序和中序遍历顺序,建立...
  • 根据二叉树的前序中序构建二叉树

    千次阅读 多人点赞 2019-04-20 15:59:45
    构建二叉树 构建二叉树,这是个比较繁琐的问题,假如我们知道二叉树的先序及中序遍历我们能不能构建二叉树呢?答案肯定是能得,这不废话么,不能得话我就得换我的标题了。 为什么能根据先序以及中序构建一棵二叉树...
  • Java构建二叉树

    千次阅读 2018-03-16 14:03:04
    Java构建二叉树二叉树节点类定义:public class Node{ int data; Node leftChild; Node rightChild; //构造方法 Node(int data){ this.data = data; leftChild = null; rightChild =...
  • 二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
  • 建立二叉树,前后中序遍历二叉树,求二叉树的深度
  • 根据二叉树先序遍历和中序遍历构建二叉树

    万次阅读 多人点赞 2019-04-24 21:20:37
    欢迎使用 Cmd Markdown 编辑阅读器...此问题变成了根据左子树的先序和序列构建左子树的二叉树,根据右子树的先序和中序序列构建右子树的二叉树问题得以分解成子问题 ​​ 令先序序列和中序序列在数组中连续存放。...
  • 前序中序和中序后序 递归构建二叉树(检测输入序列的合法性)和二叉树的动态打印 前序中序和中序后序 递归构建二叉树(检测输入序列的合法性)和二叉树的动态打印 前序中序和中序后序 递归构建二叉树(检测输入序列...
  • 二叉树的递归算法:建立二叉树、遍历二叉树.doc 多多指教
  • [问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
  • 二叉树的递归算法:建立二叉树、遍历二叉树
  • 构建二叉树、输出二叉树、求树深、复制二叉树 前序遍历
  • java初始化和构建二叉树

    千次阅读 2019-05-19 13:37:13
    首先请看如下什么叫做完全二叉树,本人认为以完全二叉树的方法构建二叉树算比较的简单,易实现。。 下面,我们就按照构建完全二叉树的形式来构建我们的二叉树: 主干代码为: import java.util.ArrayList; ...
  • 首先我们要明白先中后序遍历的特点: 先序遍历中 第一个一定是根结点。 中序遍历中 根结点左子树的...根据先序遍历和中序遍历构建二叉树 解题细想: 设置变量inedx 方便从preorder数组中获取元素构建结点。 判断i...
  • 题目:设计并验证如下算法:按后序序列建立二叉树的二叉链表结构,求其单分支结点数目,双分支结点数目,并交换该二叉树。后序序列建立二叉树需要借助栈,栈的定义如下stack.h#include&lt;stdio.h&gt; #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 120,402
精华内容 48,160
关键字:

构建二叉树