精华内容
下载资源
问答
  • 详解二叉排序树的性质,如何通过代码创建一个二叉排序树二叉排序树的一个重要用处。

    二叉排序树(Binary Sort Tree)又叫二叉搜索树(Binary Sreach Tree),简称BST。
    二叉排序树的性质:如果任一结点的左子树非空,则左子树的所有结点的值都小于根结点的值;如果任一结点的右子树非空,则右子树的所有结点的值都大于根结点的值。
    这个性质怎么理解呢?
    现在比如说我要将 7 4 5 6 1 8 9这七个数放到一个二叉排序树中
    首先,将7放入一个节点:
    在这里插入图片描述
    下面放第二个数字 4 ,这个数字在放的时候需要和我们的根节点比较大小,比根节点大就放在右边,比它小就放在左边,4比7小因此应该放在左边。
    在这里插入图片描述
    接下来放5,将5和7比较,发现比7小,因此应该放在左边,但这时左边已经有一个4了,那么我们需要把5和4进行比较,5大于4,因此应该放在4的右边。
    在这里插入图片描述
    接下来插6,6和7比,比7小,再和4比,比4大,再和5比,比5大,因此应该放在5的右边。
    在这里插入图片描述
    接下来放1,应该就放在4的左边。
    在这里插入图片描述
    接下来放8,8比7大,应该放在7的右边。
    在这里插入图片描述
    最后一个9,就应该放在8的右边。
    在这里插入图片描述
    至此,就将这几个数放在二叉排序树中了。
    知道原理之后,就需要通过代码实现了。

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
    	int data;
    	struct node *left;
    	struct node *right;
    }Node;
    
    typedef struct tree {
    	Node *root;
    }Tree;
    
    void create_tree(Tree *tree, int val)
    {
    	Node *node = (Node*)malloc(sizeof(Node));  //定于一个节点,将数放到节点中
    	node->data = val;
    	node->left = NULL;
    	node->right = NULL;
    	
    	if (tree->root == NULL) {
    		tree->root = node;   //如果根为空,就将这个节点放到根节点
    	}
    	else {
    		Node *temp = tree->root;  //定义指针指向根节点
    		while (temp != NULL) {
    			if (val < temp->data) {  //如果要放入的值小于根节点
    				if (temp->left == NULL) {  //根节点左孩为空,就直接放入
    					temp->left = node;
    					return;
    				}
    				else {
    					temp = temp->left;  //根节点左孩不为空,就指向下一个左孩节点
    				}
    			}
    			else {
    				if (temp->right == NULL) { //右孩为空,直接放入
    					temp->right = node;
    					return;
    				}
    				else {
    					temp = temp->right;  //右孩不为空,指向下一个右孩节点
    				}
    			}
    		}
    	}
    }
    int main(int argc, char **argv)
    {
    	int a[7] = {7,4,5,6,1,8,9};
    	Tree tree;
    	tree.root = NULL;
    	int i;
    	int len = sizeof(a) / sizeof(int);
    	for (i=0; i<len; i++) {
    		create_tree(&tree, a[i]);
    	}
    	return 0;
    }
    

    遍历方法有三种,前序遍历,中序遍历,后序遍历,详细的情况在我上一篇文章中有讲解。
    其中二叉排序树有一个性质比较重要,二叉排序树使用中序遍历输出的时候,输出的值是从小到大排列的。
    总的代码如下

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
    	int data;
    	struct node *left;
    	struct node *right;
    }Node;
    
    typedef struct tree {
    	Node *root;
    }Tree;
    
    void create_tree(Tree *tree, int val)
    {
    	Node *node = (Node*)malloc(sizeof(Node));  //定于一个节点,将数放到节点中
    	node->data = val;
    	node->left = NULL;
    	node->right = NULL;
    	
    	if (tree->root == NULL) {
    		tree->root = node;   //如果根为空,就将这个节点放到根节点
    	}
    	else {
    		Node *temp = tree->root;  //定义指针指向根节点
    		while (temp != NULL) {
    			if (val < temp->data) {  //如果要放入的值小于根节点
    				if (temp->left == NULL) {  //根节点左孩为空,就直接放入
    					temp->left = node;
    					return;
    				}
    				else {
    					temp = temp->left;  //根节点左孩不为空,就指向下一个左孩节点
    				}
    			}
    			else {
    				if (temp->right == NULL) { //右孩为空,直接放入
    					temp->right = node;
    					return;
    				}
    				else {
    					temp = temp->right;  //右孩不为空,指向下一个右孩节点
    				}
    			}
    		}
    	}
    }
    void preorder(Node *node)
    {
    	if (node != NULL) {
    		printf("data is %d\n",node->data);
    		preorder(node->left);
    		preorder(node->right);
    	}
    }
    
    void inorder(Node *node)
    {
    	if (node != NULL) {
    		inorder(node->left);
    		printf("data is %d\n",node->data);
    		inorder(node->right);
    	}
    }
    
    void postorder(Node *node)
    {
    	if (node != NULL) {
    		postorder(node->left);
    		postorder(node->right);
    		printf("data is %d\n",node->data);
    	}
    }
    
    int main(int argc, char **argv)
    {
    	int a[7] = {7,4,5,6,1,8,9};
    	Tree tree;
    	tree.root = NULL;
    	int i;
    	int len = sizeof(a) / sizeof(int);
    	for (i=0; i<len; i++) {
    		create_tree(&tree, a[i]);
    	}
    
    	inorder(tree.root);
    	return 0;
    }
    
    展开全文
  • 二叉排序树(Java实现)二叉排序树代码实现结点定义合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...

    二叉排序树

    二叉排序树又称二叉查找树,它或者是一颗空树,或者是具有以下性质的二叉树。

    • 若左子树非空,则左子树上所有结点的值均小于根结点的值
    • 若右子树非空,则右子树上所有结点的值均大于根结点的值
    • 左、右子树本身是二叉排序树

    如下为一颗二叉排序树:
    二叉排序树

    代码实现

    树的结点定义

    Node.java 省略get(),set()方法

    public class Node {
      
       //结点值
        private int value;
        //双亲结点
        private Node parent;
        //左右结点
        private Node left;
        private Node right;
        
        public Node() {
        }
    
        public Node(int value, Node parent, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
    
        public Node(int value,Node parent) {
            this(value,parent,null,null);
        }
    }
    

    二叉排序树算法实现

    BinarySortTree.Java

    public class BinarySortTree {
    
        private Node root = null;
    
        /**二叉排序树中的查找算法*/
        public boolean searchBST(int key){
            Node current = root;
            while (current != null){
                //等于当前值,返回true
                if(key == current.getValue())
                    return true;
                //小于当前值,进入左节点
                else if (key < current.getValue())
                    current = current.getLeft();
                //进入右节点
                else
                    current = current.getRight();
            }
            //没找到结果返回false
            return false;
        }
    
        /**二叉排序树中插入结点*/
        public boolean insertBST(int newKey){
            Node p = root;
            Node parent = null;
            //记录插入结点位置(prev为要插入结点的父节点)
            Node prev = null;
            //在树中寻找插入位置
            while (p != null){
                parent = p;
                prev = p;
                if(newKey > p.getValue())
                    p = p.getRight();
                else if (newKey < p.getValue())
                    p = p.getLeft();
                //键值为newKey的结点已在树中,不再插入
                else
                    return false;
            }
            //若为空树,键值为newKey的结点为树根
            if (root == null)
                root = new Node(newKey,parent);
            //作为左结点插入
            else if (newKey < prev.getValue())
                prev.setLeft(new Node(newKey,parent));
            //作为右结点插入
            else
                prev.setRight(new Node(newKey,parent));
            return true;
        }
    
        /**删除结点,有三种情况:
         * 1.被删除结点P为叶子结点,直接删除
         * 2.被删除结点P只有左子树或只有右子树,将被删除结点P的左子树或右子树接成其双亲结点的左/右子树
         * 3.被删除结点P有左子树和右子树,
         * 用被删除结点P左子树中最大的值(即最右端结点S)代替被删除结点P,并删除左子树中最大值(最右端结点S)
         */
        public boolean deleteBST(int key){
            return deleteBST(root,key);
        }
        public boolean deleteBST(Node node,int key){
            if (node == null)
                return false;
            else {
                if (key == node.getValue())
                    return deleteNode(node);
                else if (key < node.getValue())
                    return deleteBST(node.getLeft(),key);
                else
                    return deleteBST(node.getRight(),key);
            }
        }
    
        private boolean deleteNode(Node node) {
            Node temp = null;
            //被删除结点为叶子结点,直接删除
            if(node.getLeft() == null && node.getRight() == null){
                //被删除结点是根结点
                if(node == root)
                    root = null;
                else{
                    if(node.getValue() == node.getParent().getLeft().getValue())
                        node.getParent().setLeft(null);
                    else
                        node.getParent().setRight(null);
                }
            }
            //被删除结点P只有左子树或只有右子树,将被删除结点P的左子树或右子树接成其双亲结点的左/右子树
            else if (node.getLeft() == null){
                if(node.getValue() == node.getParent().getLeft().getValue())
                    node.getParent().setLeft(node.getRight());
                else
                    node.getParent().setRight(node.getRight());
            }
            else if (node.getRight() == null){
                if(node.getValue() == node.getParent().getLeft().getValue())
                    node.getParent().setLeft(node.getLeft());
                else
                    node.getParent().setRight(node.getLeft());
            }
            //被删除结点P有左子树和右子树,
            //用被删除结点P左子树中最大的值(即最右端结点S)代替被删除结点P,并删除左子树中最大值(最右端结点S)
            else {
                temp = node;
                Node s = node;
                /**在左子树中获取最右端结点S*/
                s = s.getLeft();
                while(s.getRight() != null){
                    temp = s;
                    s = s.getRight();
                }
                //S替代P
                node.setValue(s.getValue());
                //删除S
                if(temp != node){
                    temp.setRight(s.getLeft());
                }
                else{
                    temp.setLeft(s.getLeft());
                }
            }
            return true;
        }
    	//测试
        public static void main(String[] args) {
            BinarySortTree binarySortTree  = new BinarySortTree();
            int num[] = {38,25,45,15,30,40};
            for(int i=0;i<num.length;i++){
                binarySortTree.insertBST(num[i]);
            }
            boolean result = binarySortTree.searchBST(15);
            boolean delete = binarySortTree.deleteBST(25);
        }
    }
    
    展开全文
  • 题目描述:将二叉排序树转换成一个有序的双向链表,要求:不能创建任何新的节点,只能通过调整指针的指向来实现; 解题思路:二叉排序树的中序遍历是一个递增的序列,根据这个特性,在二叉排序树的中序遍历过程...

    题目描述:将二叉排序树转换成一个有序的双向链表,要求:不能创建任何新的节点,只能通过调整指针的指向来实现;

                                      

    解题思路:二叉排序树的中序遍历是一个递增的序列,根据这个特性,在二叉排序树的中序遍历过程中构造出一条双向链表不就行了嘛。关键是如何实现呢?

    (1)在中序遍历过程中用一个引用变量last记录遍历的上一个节点(初始为NULL),假设当前遍历的节点为root,则通过以下代码可完成双向链表的构造:

    root->left = last;
    last->right = root;
    last = root;
    

    (2)last为引用变量保证在递归遍历过程中,last可以更改指针的指向别的节点;初始化为NULL可以保证双向链表的头结点的前驱为NULL。

    C++实现代码:

    //结点的结构
    template<typename Type>
    struct BiNode{
        Type data;
        BiNode *left;//左孩子
        BiNode *right;//右孩子
    };
     
    //二叉排序树转换成有序双向链表
    template <typename Type>
    void Convert(BiNode<Type> *root, BiNode<Type> *& last)
    {
        if(root == NULL)
            return;
     
        Convert(root->left, last);
     
        root->left = last;
        if(last != NULL)//考虑last初始为NULL的情况
            last->right = root;
     
        last = root;
     
        Convert(root->right, last);
    }
     
    template <typename Type>
    BiNode<Type> * Convert2BinLink(BiNode<Type> *root)
    {
        if(root == NULL)    
            return NULL;
        
        BiNode<Type> * last = NULL;
        
        //二叉排序树转换成有序双向链表
        Convert(root, last);
     
        //取得双向链表的头指针
        while(root->left != NULL)
            root = root->left;
     
        return root;
    }

     

     

    展开全文
  • 几乎每一位码士的编程起点都是C,在玩过了Java、C#、PHP、Python之后,...如何创建二叉树如何遍历二叉树如何创建二叉链表怎样使用递归算法 这是一道非常老土但又十分经典的数据结构题,或许很多人会说自己...

    几乎每一位码士的编程起点都是C,在玩过了Java、C#、PHP、Python之后,重回C语言,又是什么样的一种感觉呢?

    此篇博文作为 【C语言强化】系列文章的第一篇,来聊聊曾让许多码士抓耳挠腮的二叉树。

    通过这道题,你可以掌握

    • 如何创建二叉树
    • 如何遍历二叉树
    • 如何创建二叉链表
    • 怎样使用递归算法


    这是一道非常老土但又十分经典的数据结构题,或许很多人会说自己之前已经做过了,但又有多少人回过头来做的时候,可以不借助任何参考资料把解题思路写出来?

    题目要求:二叉排序树->双向链表排序

    不能新增结点,只能修改指针指向

    思路
    1.定义二叉树结构体
    2.二叉树构造函数,作用:指定要插入的值和二叉树的根结点,可以自动插入到二叉排序树
    3.中序遍历二叉树的同时向双向链表插入结点并打印


    源代码

    #include <stdio.h>
    #include<stdlib.h>
    #include <iostream>
    
    using namespace std;
    
    /**
    二叉排序树->双向链表排序
    不能新增结点,只能修改指针指向
    
    思路
    1.创建二叉树结构体
    2.二叉树构造函数
    3.中序遍历二叉树的同时向双向链表插入结点并打印
    */
    
    //创建二叉树结构体
    struct BTreeNode{
    	int value;
    	BTreeNode *leftNode;
    	BTreeNode *rightNode;
    };
    typedef BTreeNode Btn;
    BTreeNode *dListIndex;//双向链表的索引,指向当前链表的尾巴
    BTreeNode *dListHead;//双向链表的头
    
    /*
    二叉树构造函数
    	按照二叉排序的算法插入(左小右大)
    node	二叉树的根结点
    value	要插入的结点的值 
    */
    void insertToBTree(BTreeNode * &node,int value){
    	//结点为空,插入结点为根结点
    	if(NULL==node){
    		BTreeNode * btNode=new BTreeNode();
    		btNode->value=value;
    		btNode->leftNode=NULL;
    		btNode->leftNode=NULL;
    		node=btNode;
    	}else{//结点非空
    		//值小于根结点,递归左结点
    		if((node->value)>value)
    			insertToBTree(node->leftNode,value);
    		//值大于根结点,递归右结点
    		else if(value>(node->value))
    			insertToBTree(node->rightNode,value);
    		//值与已有结点值相等,提示错误
    		else
    			printf("结点已经存在,不可以再次插入!");
    	}
    }
    
    /*
    双向链表构造函数
    btNode	要插入的结点
    */
    void insertToDoubleList(Btn * btNode){
    	//要插入的结点的左指针指向双向链表尾巴
    	btNode->leftNode=dListIndex;
    	//如果双向链表非空,双向链表尾巴右边指向要插入的结点,完成双向链接
    	if(NULL!=dListIndex)
    		dListIndex->rightNode=btNode;
    	//双向链表为空,头结点为要插入结点
    	else
    		dListHead=btNode;
    
    	//索引结点永远指向插入的结点
    	dListIndex=btNode;
    	//输出值
    	cout<<btNode->value<<endl;
    }
    
    /*中序遍历二叉排序树,同时往双向链表插入值
    btNode  二叉树根结点
    */
    void goThroughBTree(Btn * btNode){
    	//结点为空,返回
    	if(NULL==btNode)
    		return;
    	//左结点不为空,继续向左深入
    	else if(NULL!=btNode->leftNode)
    		goThroughBTree(btNode->leftNode);
    	//直到左结点为空,插入
    	insertToDoubleList(btNode);
    	//右不为空,向右深入
    	if(NULL!=btNode->rightNode){
    		goThroughBTree(btNode->rightNode);
    	}
    }
    
    void main()
    {
    	BTreeNode *root=NULL;//二叉树根结点
    	dListIndex=NULL;
    	dListHead=NULL;
    
    	//创建二叉排序树
    	insertToBTree(root,10);
    	insertToBTree(root,6);
    	insertToBTree(root,12);
    	insertToBTree(root,14);
    	insertToBTree(root,8);
    	insertToBTree(root,4);
    	insertToBTree(root,16);
    	
    	//遍历二叉树
    	goThroughBTree(root);
    
    	system("pause");
    }


    这道题十分基础,基础到几乎每个程序员都见过,但有多少人能够真的理解二叉树的概念而不借助任何参考把它做出来呢?这也是它会是微软的面试题的原因。


    转载于:https://www.cnblogs.com/javdroider/p/5184301.html

    展开全文
  • 这道题看例子就能明白是什么意思。...一种是map,一种是创建排序二叉树。 map写法: #include #include #include #include #include using namespace std; map mapTree; int main() { double ans=0;
  • 引入 本篇博客偏理论, 将会介绍一下知识: 索引介绍 索引原理 索引的数据结构(二叉树—>平衡二叉树—>...索引是对数据库表中一列或多列的值进行排序的一种数据结构, 使用索引可以快速访问数据库表中的特定
  • 题目要求: ...因此目前的问题转化为:如何进行二叉搜索的中序遍历,并将其转换为双链表 分为三步: (1)找到最底层的左叶子节点,并作为双向链表的头节点。 (2)对于不是头结点的点,调...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 二、解题思路 调整指针 原先指向左子节点的指针调整为链表中指向前一个节点的指针 原先...
  • 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树 二叉树查找树是一棵空树,或者是具有下列性质的二叉树: 若左子树不空,则左子树上所有结点的值均小于它的根结点的值; ...
  • 关于二叉搜索树、AVL树和红黑树二叉搜索树平衡二叉树(AVL树)AVL树的介绍AVL树的插入AVL树的删除红黑树红黑树的五大特性红黑树的插入操作合理的创建标题,有助于目录的生成...二叉树又叫二叉查找树,或者二叉排序树
  • 二叉搜索树二叉搜索树概念二叉搜索树结点的定义二叉搜索...二叉搜索树也叫二叉排序树,它或者是一颗空树,或者具有以下性质: 1.若左子树不为空,则左子树上所有结点的值都小于根结点的值; 2.若右子树不为空,则右子树
  • 输入一棵二叉查找,将该二叉查找转换成一个排序的循环双向链表。 要求不能创建任何新的结点,只调整指针的指向,也不能开辟新的存储空间O(1) 题目分析 首先照旧我们问题的解决思路,首先简化问题。(前提...
  • 今天我们要介绍的是一种特殊...开始之前呢,我们先来介绍一下如何创建一颗二叉搜索。 假设我们有这样一些数据:[9,5,2,1,4,2,1,41,22,11,35,24,11,10,4,23,9,45,2,35,12,35,16,27,56,31,73] 我们就用这些数据来创...
  • 它的左、右子树也分别为二叉排序树。 2、插入节点 二叉搜索数如何插入节点呢,我们来看看二叉搜索树的性质, 首先二叉搜索树无重复值;如果插入值已经存在,则不插入。 二叉搜索数根节点大于左子树所有节点,小于右...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。如图: ##一、知识提要: 1.什么是二叉搜索(BST): 2.什么是双向链表:跟正常链表比 ...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 二叉搜索按中序遍历有序,因此我们只需按照中序遍历的顺序修改指向,但是如何知道left该...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整中结点指针的指向。 注意: 需要返回双向链表最左侧的节点。 例如,输入下图中左边的二叉搜索,则输出右边...
  • 那么,如何创建一棵二叉搜索呢?最简单的方法就是我们可以从一棵空开始,每次调用一个addNode函数,将一个新的值插入二叉搜索中。但是在每次插入的时候我们都要保持的一个排序关系,因此我们要做的就是在...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索为例: 我们希望将这个二叉搜索转化为...
  • 因为这是一个二叉搜索,并且要求将其变成排序的双向链表,这正符合二叉树的中序遍历思路,当我们遍历到根节点的时候,左子树已经排好序,我们要就是将左子树的最大节点与根节点相连,至于如何实现左子树的排序,用...
  • 由于二叉搜索的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了,但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个节点的left与right指针,现在问题是如何设置这两个指针?二叉...
  • 那么,如何创建一棵二叉搜索呢?最简单的方法就是我们可以从一棵空开始,每次调用一个addNode函数,将一个新的值插入二叉搜索中。但是在每次插入的时候我们都要保持的一个排序关系,因此我们要做的就是在...
  • 思路:由于二叉搜索的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了,但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个节点的left与right指针,现在问题是如何设置这两个指针?...
  • 输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 返回双向链表最左侧的节点。 解题思路: 这道题的重点就是在如何左子树的最右下节点,...
  • 面试题36:输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。 思路 调整指针 原先指向左子节点的指针调整为链表中指向前一个节点的指针 原先...
  • 题目描述:输入一颗二叉搜索,将该二叉搜索转换成一个排序的双向链表,要求不能创建任何新的节点,只能调整树种节点指针的指向。思路:由于二叉搜索的中序遍历就是排序的,如果是构造单链表,只需要一次中序...
  • 思路:对于二叉搜索,根结点的左子树都比它小,右子都比它大,如果按照中序遍历那么结点就是排序的,问题的关键是如何修改指针指向。假设左右子树已经排序,那么只要将左子树的尾结点连接上根结点,根结点连接上...
  • 题目描述:输入一棵二叉搜索,将该二叉搜索转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整中结点指针的指向。题目分析:在搜索二叉树中,左子结点的值总是小于父结点的值,右子结点的值总是...

空空如也

空空如也

1 2 3 4
收藏数 66
精华内容 26
关键字:

如何创建二叉排序树