精华内容
下载资源
问答
  • 对一棵二叉排序树进行中序遍历
    2021-02-26 22:19:11
    #include <iostream>
    #include <cstdio>
    #include <queue>
    using namespace std;
    struct TreeNode{
        int data;
        TreeNode *leftchild;
        TreeNode *rightchild;
    };
    
    TreeNode* Insert(TreeNode* root, int x){//二叉排序树建树
        if(root == NULL){
            root = new TreeNode();
            root->data = x;
            root->leftchild = NULL;
            root->rightchild = NULL;
        }else if(x < root->data){
            root->leftchild = Insert(root->leftchild,x);
        }else{
            root->rightchild = Insert(root->rightchild,x);
        }
        return root;
    }
    void InOrder(TreeNode* root){//二叉排序树中序输出升序所以叫排序树
        if(root != NULL){
            InOrder(root->leftchild);
            printf("%d\n",root->data);
            InOrder(root->rightchild);
        }
        return;
    }
    int main(){
        int n;
        while(scanf("%d",&n) != EOF){
            TreeNode* root = NULL;
            while(n--){
                int x;
                scanf("%d",&x);
                root = Insert(root,x);
            }
            InOrder(root);
        }
        return 0;
    }
    
    
    更多相关内容
  • 二叉排序树-中序遍历

    2012-06-14 10:32:21
    采用llink-rlink方式存储二叉排序树,编写能够通过键盘输入建立二叉排序树,并在建立完立即在屏幕显示中序遍历结果的程序
  • 建立位数组,然后以位数组为例进行二叉排序树中序遍历
  • 二叉搜索中序遍历

    千次阅读 2021-03-30 20:30:08
    二叉搜索树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根节点的值; 若它的右子树不空,则右子树...

    二叉搜索树的概念

    二叉搜索树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 

     图1                              图2

    类似图1,此处3比5小,不是二叉搜索树,中序遍历得出的序列为[1, 5, 3, 4, 6]可以看出,并不是逐个递增的。图2是二叉搜索树,中序遍历得出的序列[1, 2, 3, 4, 5, 6]

    二叉搜索树的性质

    二叉树由于左子树的结点的值均小于根节点的值,右子树的结点的值均大于根节点的值。所以二叉搜索树可以根据中序遍历,转换成值递增的一维数组。 因此大部分的二叉搜索树的题目都可以先直接使用中序遍历,然后进行相应的操作。

    中序遍历的方式可以递归,也可以迭代,迭代写法方便对序列进行操作,所以尽量使用迭代中序遍历。写法可以参考往期博客。

    https://blog.csdn.net/weixin_42835209/article/details/115321081?spm=1001.2014.3001.5501

     

    二叉搜索树相关leetcode题解

    leetcode-98. 验证二叉搜索树

     

    思路:根据中序遍历把二叉树转换成List,逐个比较是否依次递增。利用了二叉搜索树的特性,方法较为暴力。

    import java.util.ArrayList;
    import java.util.List;
    
    import 树.TreeNode;
    
    public class IsValidBST {
    
    	public static void main(String[] args) {
    		TreeNode root1 = new TreeNode(1);
    		TreeNode root2 = new TreeNode(1);
    //		TreeNode root3 = new TreeNode(6);
    //		TreeNode root4 = new TreeNode(3);
    //		TreeNode root5 = new TreeNode(7);
    		
    		root1.left = root2;
    //		root1.right = root3;
    //		root3.left = root4;
    //		root3.right = root5;
    		IsValidBST ivbst = new IsValidBST();
    		
    		System.out.println(ivbst.isValidBST(root1));
    	}
    	List<Integer> list = new ArrayList<Integer>();
    	public List<Integer> midOrderTraversal(TreeNode root){
    		if(root == null) {
    			return list;
    		}
    		midOrderTraversal(root.left);
    		list.add(root.val);
    		midOrderTraversal(root.right);
    		return list;
    	}
    	
        public boolean isValidBST(TreeNode root) {
        	if(root == null) {
        		return true;
        	}
        	List<Integer> arr = midOrderTraversal(root);
        	for(int i=1;i<arr.size();i++) {
        		if(arr.get(i) <= arr.get(i-1)) {
        			return false;
        		}
        	}
        	return true;
        }
    }

     

    leetcode-99. 恢复二叉搜索树

     

    思路:1. 根据中序遍历,把树转换成List。2. 根据List找到对应的x和y,x为第一个比后面的数大的数字,y为最后一个比x小的数。交换树中对应x结点和y结点的值。

    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    import 树.TreeNode;
    
    public class RecoverTree {
    
    	public static void main(String[] args) {
    		TreeNode root1 = new TreeNode(1);
    		TreeNode root2 = new TreeNode(3);
    		TreeNode root3 = new TreeNode(2);
    
    		
    		root1.left = root2;
    		root2.right = root3;
    		RecoverTree rt = new RecoverTree();
    		rt.recoverTree(root1);
    	}
    	
    	
        public void recoverTree(TreeNode root) {
        	List<Integer> nums = new ArrayList<Integer>();
        	inorder(root, nums);
        	int [] swapped = findTwoSwapped(nums);
        	recover(root, 2, swapped[0], swapped[1]);
    
        }
        
        public void inorder(TreeNode root, List<Integer> nums) {
        	if(root == null) {
        		return;
        	}
        	inorder(root.left, nums);
        	nums.add(root.val);
        	inorder(root.right, nums);
        }
        
        public int[] findTwoSwapped(List<Integer> nums) {
        	int n = nums.size();
        	int x = -1, y = -1;
        	for(int i=1;i<n;i++) {
        		if(nums.get(i) < nums.get(i-1)) {
        			y = nums.get(i);
        			if(x == -1) { // 只记录第一次 
        				x = nums.get(i-1);
        			}else {
        				break;
        			}
        		}
        	}
        	return new int[] {x, y};
        }
        
        public void recover(TreeNode root, int count, int x, int y) {
        	if(root != null) {
        		if(root.val == x || root.val == y) {
        			root.val = root.val == x?y:x;
        			if(--count == 0) { // 找到再减count
        				return;
        			}
        		}
        		recover(root.right, count, x, y);
        		recover(root.left, count, x, y);
        	}
        }
    }

     

    leetcode-230. 二叉搜索树中第K小的元素

     

    思路:把二叉树转换成List,按索引取数字,第k小对应的索引为k-1。

    import java.util.ArrayList;
    import java.util.List;
    
    import 树.TreeNode;
    
    public class KthSmallest {
    
    	public static void main(String[] args) {
    
    	}
    
        public int kthSmallest(TreeNode root, int k) {
        	List<Integer> nums = new ArrayList<>();
        	
        	inorder(root, nums);
        	return nums.get(k-1);
        }
        
        public void inorder(TreeNode root, List<Integer> nums) {
        	if(root == null) {
        		return;
        	}
        	inorder(root.left, nums);
        	nums.add(root.val);
        	inorder(root.right, nums);
        }
    }

     

    leetcode-二叉搜索树中的中序后继

     

    思路:用迭代写法的中序遍历,定义一个flag初始化为false,代表是否找到p。如果找到p,则置flag为true,则下一次迭代时得到的node则为p的后继。由于中序遍历取数都是在栈中弹栈才取的,所以需要在弹栈的时候进行flag的判断和修改。

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    import 树.TreeNode;
    
    public class InorderSuccessor {
    	public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    		if(root == null) {
    			return null;
    		}
    		
    		// 迭代中序遍历
    		Stack<TreeNode> stack = new Stack<>();
    		boolean flag = false;
    		while(root!=null || !stack.empty()) {
    			while(root!=null) {
    				stack.push(root);
    				root = root.left;
    			}
    			TreeNode node = stack.pop();
    			if(flag == true) {
    				return node;
    			}
    			// 判断p的值是否相等,如果相等,则设置为true,获得下一次遍历的值
    			if(node.val == p.val) {
    				flag = true;
    			}
    			if(node.right != null) {
    				root = node.right;
    			}
    		}
    		return null;
    	}
    	
    }
    

     

    leetcode-最接近的二叉搜索树值II

     

    思路:先实现中序遍历,用一个map记录<差值,原值>,在java中转换成TreeMap进行升序排序。得到差值小的排在前面,则根据k得到前k个差值最小的数字,即最接近的数字进行返回。

    import java.util.ArrayList;
    import java.util.Collection;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    import java.util.PriorityQueue;
    import java.util.Queue;
    import java.util.Set;
    import java.util.Stack;
    import java.util.TreeMap;
    
    import 树.TreeNode;
    
    public class ClosestKValues {
    
    	List<Integer> closestKValues(TreeNode root, double target, int k){
    		List<Integer> res = new ArrayList<Integer>();
    		if(root == null) {
    			return res;
    		}
    		Stack<TreeNode> stack = new Stack<>();
    		Map<Double, Integer> map = new HashMap<Double, Integer>();
    		while(!stack.empty() || root != null) {
    			while(root != null) {
    				stack.push(root);
    				root = root.left;
    			}
    			TreeNode node = stack.pop();
    			map.put(Math.abs(node.val-target), node.val);
    			if(node.right != null) {
    				root = node.right;
    			}
    		}
    		
    		TreeMap<Double, Integer> sorted = new TreeMap<>(map);
    		System.out.println(sorted.toString());
    		List<Integer> arr = new ArrayList<Integer>(sorted.values());
    		for(int i=0;i<k;i++) {
    			res.add(arr.get(i));
    		}
    		Collections.sort(res);
    		return res;
    	}
    
    }
    

     

    总结

    总而言之,只要是二叉搜索树的题目,都可以实现中序遍历先。中序遍历可以先额外写一个递归的中序遍历函数返回各种参数,也可以直接用迭代的中序遍历直接在迭代体中进行一系列操作。主要是要掌握各种数据结构容器的使用,并深刻理解树的遍历的写法。

    展开全文
  • 本文链接:https://blog.csdn.net/m0_37609579/article/details/99687256 、计算机科学中的 二、二叉树的定义 一棵树,它的每个节点最多只能有两个子节点,此时就叫二叉树。(我们一般在书中试题中见到的是...

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/m0_37609579/article/details/99687256

    一、计算机科学中的树

    96fa72fbd21ee2663ae0f388e9baa037.png


    二、二叉树的定义
    一棵树,它的每个节点最多只能有两个子节点,此时就叫二叉树。(我们一般在书中试题中见到的树是二叉树,但并不意味着所有的树都是二叉树。如果节点多于两个,我们也称之为多路树)

    411a77aa2f0a5e092a4b2cedad3415e8.png

    1532f0a2a8ccfa9376dfb5033bdbac57.png

    c657c427733b911bcd9bba3e9ff98a55.png

    可以看出: 满二叉树一定是完全二叉树;完全二叉树不一定是满二叉树。
    如果我们给二叉树加一个额外的条件,就可以得到一种被称作二叉查找树(binary search tree)的特殊二叉树。
    二叉查找树要求:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。【左边下边小,右边上边大

    941c8c622703742c665e2572e559724b.png


    三、二叉查找树的日常操作
    PS:二叉树很多,但对我们来说,在实际的应用中,二叉排序树的应用比较多。1.插入新节点
    假设我们要为数组 a[] = {10 , 5 , 15 , 6 , 4 , 16 }构建一个二叉排序树,我们按顺序逐个插入元素。

    76491bece59dd8de38b0ba537a1de338.png


    插入过程是这样的:
    如果是空树,则创建一个新节点,新节点作为根,因此以元素10构建的节点为该二叉查找树的根。

    • 插入5,5比10小,与10的左孩子节点进行比较,10的左孩子节点为空,进行插入。
    • 插入15,15比10大,与10的右孩子节点进行比较,10的右孩子节点为空,进行插入。
    • 插入6,6比10小,与10的左孩子节点5比较;6比5大,与5的右孩子节点进行比较,5的右孩子为空,进行插入。
    • 插入4,4比10小,与10的左孩子节点5比较;4比5小,与5的左孩子节点进行比较,5的左孩子为空,进行插入。
    • 插入16,16比10大,与10的右孩子节点15比较;16比15大,与15的右孩子节点进行比较,15的右孩子为空,进行插入。

    从这个过程我们可以总结出插入新元素的步骤:

    • 寻找元素合适的插入位置:新元素与当前结点进行比较,若值大于当前结点,则从右子树进行寻找;否则从左子树进行寻找.
    • 找到插入位置之后,以元素的值构建新节点,插入二叉排序树中。

    2.遍历平衡二叉树
    【百度百科】平衡二叉搜索树,又被称为AVL树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    620ffd80c79390cb0e16280713fac6dd.png


    遍历平衡二叉树,就是以某种方式逐个“访问”二叉树的每一个节点。举例说明:

    e9c6c56eb5507e206be95c03b00032c9.png


    前序遍历

    • 访问根结点中的数据
    • 前序遍历左子树
    • 前序遍历右子树
      前序遍历结果:
      1, 2, 4, 8, 9, 5, 10, 3, 6, 7

    中序遍历

    • 中序遍历左子树
    • 访问根结点中的数据
    • 中序遍历右子树
      中序遍历结果:
      8, 4, 9, 2, 10, 5, 1, 6, 3, 7

    后序遍历

    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根结点中的数据
      后序遍历结果:
      8, 9, 4, 10, 5, 2, 6, 7, 3, 1

    层次遍历

    • 访问根结点中的数据
    • 访问第二层所有结点的数据
    • 访问第三层所有结点的数据
    • ……
      层次遍历结果:
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10

    3.删除节点
    删除二叉排序树的某个节点有三种情况:

    • 被删除节点同时有左子树与右子树。将前驱节点的值保存在当前结点,继而删除前驱节点。
    • 被删除节点只有左子树或只有右子树。直接用子树替换被删节点。
    • 被删除节点没有子树。可以直接删除节点。

    2fa740c8ea6185dd94d41970938a090d.png

    4.查找最值元素
    二叉排序树的最小值位于其最左节点上;最大值位于其最右节点上

    ea46bde75941c88375854569a37bebb8.png


    我的微信公众号:架构真经(id:gentoo666),分享Java干货,高并发编程,热门技术教程,微服务及分布式技术,架构设计,区块链技术,人工智能,大数据,Java面试题,以及前沿热门资讯等。每日更新哦!

    886de73118a3e72a9ba4e5b40a10d245.png


    四、参考资料https://blog.csdn.net/wannuoge4766/article/details/83998377https://www.cnblogs.com/shixiangwan/p/7530015.htmlhttps://www.cnblogs.com/ysocean/p/8032642.htmlhttps://blog.csdn.net/u014634338/article/details/42465089http://www.it610.com/article/3607922.htm

    展开全文
  • 给你个二叉树的根节点 root ,判断其是否是个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树只包含 小于 当前节点的数。...算法:树中序遍历的顺序为左根右,根据二叉树搜索树的性质,如果一棵树满

    给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。

    有效 二叉搜索树定义如下:

    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。

    示例 1:
    在这里插入图片描述

    输入:root = [2,1,3]
    输出:true
    示例 2:

    在这里插入图片描述

    输入:root = [5,1,4,null,null,3,6]
    输出:false
    解释:根节点的值是 5 ,但是右子节点的值是 4 。

    算法:树中序遍历的顺序为左根右,根据二叉树搜索树的性质,如果一棵树满足二叉搜索树,它的中序遍历结果一定是升序的;
    java栈实现

    class Solution {
        public boolean isValidBST(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<TreeNode>();
            double inorder = -Double.MAX_VALUE;
    
            while (!stack.isEmpty() || root != null) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                  // 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树
                if (root.val <= inorder) {
                    return false;
                }
                inorder = root.val;
                root = root.right;
            }
            return true;
        }
    }
    
    展开全文
  • 实现要求: ...该二叉树类提供方法进行节点的追加(追加节点时,构建二叉排序树),并提 供中序遍历二叉树节点的方法。 BinaryTreeNode类 public class BinaryTreeNode { private int data; priv...
  • 二叉排序树中序遍历是递增的!!!记住
  • class Solution { int res = 0; int index = 0; public int kthSmallest(TreeNode root, int k) { zhongxu... //从这开始是遍历到第个元素 if( k == index){ res = root.val; return; }; zhongxu(root.right,k); } }
  • !... 我看书上说“二叉排序树中序遍历结果是递增序列”,然后我随便写了几个数,生成二叉排序树进行中序遍历,结果如上图,它不是递增序列啊???是我知识上有什么漏洞吗?求教啊~~
  • 二叉排序树建立及中序遍历,数据结构作业
  • 文章目录【1】代码:①Node节点②BST binarySortTree二叉排序树:③ 测试代码:【2】测试结果: 【1】代码: ①Node节点 package algorithm.tree.binarySortTree_BST; public class Node { int val; Node left; ...
  • 对二叉排序树中序遍历(非递归不用栈队列) 找到这树的中序遍历的第个节点 相当于找这课二叉树的最小值 BstNode* First(BstNode* ptr)//找到这树的中序遍历的第个节点 { while (ptr != nullptr &&...
  • 给定个二叉树,判断它是否是合法的二叉查找(BST) 一棵BST定义为: 节点的左子树中的值要严格小于该节点的值。节点的右子中的值要严格大于该节点的值。左右子树也必须是二叉查找个节点的也是二叉查找...
  • 中序遍历二叉排序树

    2018-06-30 21:06:55
    输入整数序列,建立二叉排序树,然后中序遍历。 输入说明 输入第行为整数的个数n,第二行是具体的n个整数。 输出说明 建立二叉排序树,然后输出中序遍历的结果。 输入样例 5 1 6 5 9 8 输出样例 1 5 6 8 9
  • (2) 建立一棵二叉排序树,然后进行中序遍历,并实现动态查找。(输入零为空) 头文件:1.h #include &lt;iostream&gt; #include &lt;malloc.h&gt; #include &lt;string.h&gt; #define TRUE...
  • 二叉排序树创建、中序遍历(由小到大)、交换左右子树输出(由大到小),完整C++实现代码,在Clion中编译通过。 #include "stdio.h" #include "stdlib.h" #include "malloc.h" //...
  • 二叉查找 中序遍历

    2020-11-08 15:49:01
    * 二叉查找 */ public class BinarySortTreeTest { // 创建个节点类 包含值,左节点 右节点 public class Node { int value; Node left; Node right; public Node() { } // 有参构造 .
  • 恢复二叉搜索 二叉搜索中的两个节点被错误地交换。 请在不改变其结构的情况下,恢复这棵树。 示例1: 输入: [1,3,null,null,2] 1 / 3 \ 2 输出: [3,1,null,null,2] 3 / ...
  • 二叉排序树或者是一棵空树,或者是颗具有以下特性的非空二叉树: 若左子树非空,则左子树上所有结点的值都小于根节点的值。 若右子树非空,则左子树上所有结点的值都大于根节点的值。 左、右子树也分别是颗...
  • 针对数据结构的遍历问题主要有四种,前序遍历、中序遍历、后序遍历、层序遍历,我们主要说明一下二叉树前序、中序、后序的递归方式代码模板。 基本思想 前序遍历:根结点 —> 左子树 —> 右子 中序...
  • 、题目描述 给你个二叉树的根节点 root ,判断其是否是个有效的二叉搜索。 有效 二叉搜索定义如下: 节点的左子树只包含 小于 当前节点的数。 节点的右子只包含 大于 ...中序遍历 + 递归 当前节点是否大于
  • 可能有多组测试数据,对于每组数据,将题目所给数据建立二叉排序树,并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出行。每行最后个数据之后有个空格。 样例输入 1 2 2 8 15 4 21 10 5 39 ...
  • 题目:将二叉查找按照中序遍历转换成双向链表。 给定二叉查找: 4 / \ 2 5 / \ 1 3 返回1<->2<->3<->4<->5。 思路:如果对于当前节点,把右子转换成双向...
  • 棵二叉搜索中的所有元素(中序遍历)
  • } //查看树中的值 System.out.println("二叉排序树中序遍历:"); bst.midShow(); System.out.println(); System.out.println("============="); Node node = bst.search(10); System.out.println(node.value); Node...
  • } } 2、Answer( Java ) 解法思路:二叉搜索树中序遍历 + 归并排序 ⚡️二叉搜索树 的 中序遍历 结果是有序的 中序遍历这两棵二叉搜索树,可以得到两个有序数组。然后可以使用 双指针 方法来合并这两个有序数组...
  • 1. 题目 二叉搜索中的两个节点被错误地交换。...循环中序遍历(栈),记录不满足的节点,交换其val O(n)O(n)O(n) 空间复杂度 class Solution { public: void recoverTree(TreeNode* root) { if(root == ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,611
精华内容 12,244
热门标签
关键字:

对一棵二叉排序树进行中序遍历