精华内容
下载资源
问答
  • 3.2 二叉排序树创建 实现思路: 对于数列{7,3,10,12,5,1,9},先将第一个数字7设置为二叉排序树的根节点; 遍历数列,将剩余的数字插入树中: 每一次插入均从根节点出发; 若待插入的值大于当前节点,判断当前...

    JAVA数据结构与算法 11.树

    3 二叉排序树

    3.1 二叉排序树介绍

    ​ 二叉排序树:BST(Binary Sort Tree),对于二叉排序树的任何一个非叶子结点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大

    在这里插入图片描述

    3.2 二叉排序树的创建

    实现思路

    • 对于数列{7,3,10,12,5,1,9},先将第一个数字7设置为二叉排序树的根节点;
    • 遍历数列,将剩余的数字插入树中:
      • 每一次插入均从根节点出发;
      • 若待插入的值大于当前节点,判断当前节点的左子树是否为空,若为空则直接将待插入节点放在左子节点的位置,若不为空则继续向左递归查找插入位置;
      • 若待插入的值小于当前节点,判断当前节点的右子树是否为空,若为空则直接将待插入节点放在右子节点的位置,若不为空则继续向右递归查找插入位置。

    代码实现

    public class BinarySortTreeDemo {
        public  static void main(String args[]){
            int[] arr = {7,3,10,12,5,1,9};
            BinarySortTree binarySortTree = new BinarySortTree();
            for (int value:arr){
                binarySortTree.addNode(new Node(value));
            }
            binarySortTree.inOrder();
        }
    }
    class BinarySortTree{
        private Node root;
        public void addNode(Node node){
            if(root == null){
                root = node;
            }else {
                root.add(node);
            }
        }
        public void inOrder(){
            if(root == null){
                System.out.println("树为空");
                return;
            }
            root.inOrder();
        }
    }
    class Node{
        public int value;
        public Node left;
        public Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "{" +
                    "value=" + value +
                    '}';
        }
        public void add(Node node){
            if(node == null)return;
            if(node.value < this.value){    //值小于当前节点,向左子树判断
                if(this.left == null){  //若左子节点为空,则直接将node添加到左子节点
                    this.left = node;
                    return;
                }else { //若不为空则继续向左递归直到找到可以添加的叶子节点为止
                    this.left.add(node);
                }
            }else {
                if(this.right == null){     //值大于当前节点,向右子树判断
                    this.right = node;
                    return;
                }else {
                    this.right.add(node);
                }
            }
        }
        //中序遍历
        public void inOrder(){
            if(this.left != null) this.left.inOrder();
            System.out.print(this+"=>");
            if(this.right != null) this.right.inOrder();
        }
    }
    

    3.3 二叉排序树的删除

    二叉排序树删除节点,需要考虑三种情况:

    删除叶子结点

    1. 需要先找到要删除的结点targetNode;
    2. 找到targetNode的父节点parent;
    3. 确定targetNode是parent的左子结点还是右子结点
    4. 根据前面的情况来对应删除parent.left/right = null

    删除只有一颗子树的结点

    1. 需要先找到要删除的结点targetNode;
    2. 找到targetNode的父节点parent;
    3. 如果targetNode是父节点parent的左子节点且targetNode有左子结点:parent.left = targetNode.left;
    4. 如果targetNode是父节点parent的左子节点且targetNode有右子结点:parent.left = targetNode.right;
    5. 如果targetNode是父节点parent的右子节点且targetNode有左子结点:parent.right= targetNode.left;
    6. 如果targetNode是父节点parent的右子节点且targetNode有右子结点:parent.right= targetNode.right;

    删除有两颗子树的结点

    1. 需要先找到要删除的结点targetNode;
    2. 找到targetNode的父节点parent;
    3. 从targetNode的右子树中找到最小的结点minNode;
    4. 将该节点minNode覆盖到targetNode的位置;
    public class BinarySortTreeDemo {
        public  static void main(String args[]){
            int[] arr = {7,3,10,12,5,1,9,2};
            BinarySortTree binarySortTree = new BinarySortTree();
            for (int value:arr){
                binarySortTree.addNode(new Node(value));
            }
            binarySortTree.inOrder();//{value=1}=>{value=2}=>{value=3}=>{value=5}=>{value=7}=>{value=9}=>{value=10}=>{value=12}=>
            //删除叶子结点
            //binarySortTree.delNode(2);
            //binarySortTree.inOrder();//{value=1}=>{value=3}=>{value=5}=>{value=7}=>{value=9}=>{value=10}=>{value=12}=>
    
            //删除有一个子节点
    //        binarySortTree.delNode(1);
    //        binarySortTree.inOrder();//{value=2}=>{value=3}=>{value=5}=>{value=7}=>{value=9}=>{value=10}=>{value=12}=>
            //删除右两个子节点
            binarySortTree.delNode(10);
            binarySortTree.inOrder();
        }
    }
    class BinarySortTree{
        private Node root;
        public void inOrder(){
            if(root == null){
                System.out.println("树为空");
                return;
            }
            root.inOrder();
            System.out.println();
        }
        public Node searchTargetNode(int value){
            if(root != null){
                return root.searchNode(value);
            }
            return null;
        }
        public Node searchParentNode(int value){
            if(root != null){
                return root.searchParent(value);
            }
            return null;
        }
        //删除结点
        public void delNode(int value){
            if(root == null){
                return;
            }
            //1.需要先找到要删除的结点targetNode
            Node targetNode = searchTargetNode(value);
            if(targetNode == null) return;
            //2.找到targetNode的父节点parent
            Node parentNode = searchParentNode(value);
            if(parentNode == null){ //找到了要删除的结点,找不到父节点,此时要删除的结点为根结点
                root = null;
                return;
            }
            //3.分删除情况讨论
            //3.1 情况1:删除叶子结点
            if(targetNode.left == null && targetNode.right == null){
                //3.1.1 确定targetNode是parent的左子结点还是右子结点
                if(parentNode.left == targetNode){
                    parentNode.left = null;
                }else {
                    parentNode.right = null;
                }
                return;
            }
            //3.2 情况2:删除只有一颗子树的结点
            if((targetNode.left != null && targetNode.right == null) || (targetNode.right != null && targetNode.left == null)){
                //3.2.1如果targetNode是父节点parent的左子节点且targetNode有左子结点:parent.left = targetNode.left;
                if(parentNode.left == targetNode && targetNode.left != null){
                    parentNode.left = targetNode.left;
                }
                //3.2.2如果targetNode是父节点parent的左子节点且targetNode有右子结点:parent.left = targetNode.right
                if(parentNode.left == targetNode && targetNode.right != null){
                    parentNode.left = targetNode.right;
                }
                //3.2.3如果targetNode是父节点parent的右子节点且targetNode有左子结点:parent.right= targetNode.left;
                if(parentNode.right == targetNode && targetNode.left != null){
                    parentNode.right = targetNode.left;
                }
                //3.2.4如果targetNode是父节点parent的右子节点且targetNode有右子结点:parent.right= targetNode.right;
                if(parentNode.right == targetNode && targetNode.right != null){
                    parentNode.right = targetNode.right;
                }
                return;
            }
            //3.3 情况3:删除有两颗子树的结点
            if(targetNode.left != null && targetNode.right != null){
                //3.3.1 从targetNode的右子树中找到最小的结点minNode
                int min = delMin(targetNode.right);
                targetNode.value = min;
            }
        }
    
        /**
         * 返回并删除以node结点为根的二叉树的最小子节点,返回value
         * @param node
         * @return
         */
        public int delMin(Node node){
            while(node.left != null){
                node = node.left;
            }
            Node del = node;
            delNode(del.value);
            return del.value;
        }
    }
    class Node{
        public int value;
        public Node left;
        public Node right;
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "{" +
                    "value=" + value +
                    '}';
        }
        //中序遍历
        public void inOrder(){
            if(this.left != null) this.left.inOrder();
            System.out.print(this+"=>");
            if(this.right != null) this.right.inOrder();
        }
    
        /**
         * 查找要删除的结点targetNode
         * @param value
         * @return
         */
        public Node searchNode(int value){
            if(this.value == value){
                return this;
            }else if(this.value > value){
                if(this.left == null) return null ;
                return this.left.searchNode(value);
            }else{
                if(this.right == null) return null;
                return this.right.searchNode(value);
            }
        }
    
        /**
         * 查找待删除结点的父节点
         * @param value 待删除结点的值
         * @return  父节点
         */
        public Node searchParent(int value){
            if((this.left != null && this.left.value == value)||(this.right != null && this.right.value == value)){
                return this;
            }else if(this.value > value && this.left != null){
                return this.left.searchParent(value);
            }else if(this.value < value && this.right != null){
                return this.right.searchParent(value);
            }else {
                return null;
            }
        }
    }
    
    
    展开全文
  • 二叉排序树C实现代码

    2018-03-05 22:25:25
    1.创建二叉排序树; 2.销毁二叉排序树; 3.清空二叉排序树; 4.插入指点结点至二叉排序树; 5.删除二叉排序树指点结点; 5.获取二叉排序树指定结点; 6.获取二叉排序树根结点; 7.获取二叉排序树结点数; 8.获取二叉...
  • 代码实现:二叉排序树(BST)的插入、查找(非递归),递归算法、中序遍历二叉排序树,输出有序树,层序遍历BST树、创建一颗二叉排序树二叉排序树的删除等等。 概念: 没什么好说的,二叉排序树(BST)就是一个...

    主题:

    代码实现:二叉排序树(BST)的插入、查找(非递归),递归算法、中序遍历二叉排序树,输出有序树,层序遍历BST树、创建一颗二叉排序树、二叉排序树的删除等等。

    概念:

    没什么好说的,二叉排序树(BST)就是一个中序遍历有序的树,如图中的红色的区域左边整体小于右边,以77为根,明显绿色区域小于黄色区域,
    所以进行插入时,遇到了比它的根节点大的,就放在左边,比它的根节点小的就放在右边,然后递归,如果遇到了合适的空位,也就是tr==NULL这时候就是插入的时候,
    在这里插入图片描述

    难点:

    二叉排序树(BST)最难的地方在于其删除操作

    1. 当是需要删除的节点是叶子节点,可以直接删掉,因为它没有左右孩子,不需要考虑删除后,二叉排序树的性质改变。
    2. 当需要删除的节点只有一个孩子时,这个孩子可以是左孩子,也可以是右孩子;需要删除当前节点,然后把左孩子(或者右孩子)接到这个被删除节点原本的位置上,也就是被删除节点的父节点的对应孩子变成了被删除节点的孩子,可以理解为【儿子谋权篡位,杀了爸爸,然后继承了爷爷的皇位】 。——————这个从字面上看,需要找到被删除节点的父节点————————而一个巧妙的实现是,交换父节点和儿子节点的值,然后删除儿子节点,并把儿子节点的儿子节点接到原本的父节点的位置。(本文使用的是查找父节点的方式,便于理解)
    3. 当需要删除的节点有两个孩子时,删除该节点时,左边都是比该节点小的值,右边都是比该节点大的值,所以需要找到一个合适的值【接替皇位】,这个值可以是正好比该节点小的值(也就是中序遍历的前驱节点)【皇帝的弟弟】,也可以是正好比该节点大的值【皇帝的哥哥】(也就是中序遍历的,后继节点)。这个值作为根节点,显然,这个根节点左边的值都比根节点小,右边的值都比根节点大。————为了实现这个目标,需要一个查找后继节点的函数,并且需要删除原节点,且把接替它的新的根【新皇帝】节点接上去【顶替皇位】。——————一个巧妙的实现方法同上2:交换要删除的值和顶替这个被删除的节点值的值;然后删除这个旧值的节点,这样一来,就转化为了(1或者2或者3)

    例如:

    删除77,87和77交换位置,而删除77的操作是情况2,需要删除的节点只有一个孩子,这样一来,就可以递归地删除,77的孩子顶替77,
    在这里插入图片描述
    在这里插入图片描述
    得到结果:
    在这里插入图片描述

    输入:

    在这里插入图片描述

    5
    77
    12
    87
    99
    43
    123
    0
    

    函数调用:

    BSTree_use.cpp

    #include "BSTree.h"
    int main()
    {
        int key = 5;
        BSTree tr = CreateBSTree();
        std::cout << "请输入需要查找的值:";
        std::cin >> key;
    
        std::cout << "二叉排序树查找" << key << "(非递归)" << BST_Search(tr, key) << std::endl;
        std::cout << "二叉排序树查找" << key << "(递归)" << FindNodeK(tr, key) << std::endl;
    
        DeleteBSTreeNode(tr, 77);
        DeleteBSTreeNode(tr, 5);
        DeleteBSTreeNode(tr, 12);
        DeleteBSTreeNode(tr, 87);
        DeleteBSTreeNode(tr, 99);
        DeleteBSTreeNode(tr, 123);
        DeleteBSTreeNode(tr, 43);
    }
    

    函数定义:

    BSTree.h

    #include <iostream>
    #include <stack>
    #include <queue>
    typedef struct BSNode
    {
        int data;
        struct BSNode *lchild, *rchild;
    } * BSTree, BSNode;
    
    /***
     * 二叉排序树(BST)的插入
     * 成功返回1, 失败返回0
     */
    int BSTreeInsert(BSTree &tr, int k)
    {
        if (!tr)
        {
            tr = (BSNode *)malloc(sizeof(BSNode));
            tr->data = k;
            tr->lchild = tr->rchild = NULL;
            return 1;
        }
        else if (k == tr->data)
        { //已经有了这个节点了
            return 0;
        }
        else if (k < tr->data)
        {
            return BSTreeInsert(tr->lchild, k);
        }
        else
        {
            return BSTreeInsert(tr->rchild, k);
        }
    }
    
    /***
     * 二叉排序树的查找(非递归)
     */
    BSNode *BST_Search(BSTree tr, int k)
    {
        while (tr && k != tr->data)
        {
            if (k < tr->data)
                tr = tr->lchild;
            else
            {
                tr = tr->rchild;
            }
        }
        return tr;
    }
    
    /***
     * 二叉排序树(BST)的查找,递归算法
     */
    BSNode *FindNodeK(BSTree tr, int k)
    {
        if (!tr)
            return NULL;
        FindNodeK(tr->lchild, k);
        if (tr->data == k)
            return tr;
        FindNodeK(tr->rchild, k);
    }
    
    /**
     * 中序遍历二叉排序树,输出有序树
     */
    void VisitBSTree(BSTree tr)
    {
        if (tr)
        {
            VisitBSTree(tr->lchild);
            std::cout << tr->data << " ";
            VisitBSTree(tr->rchild);
        }
    }
    /**
     * 层序遍历BST树
     */
    void VisitLevelBSTree(BSTree tr)
    {
        std::queue<BSNode *> q;
        BSNode *p = tr, *r = tr;
        q.push(p);
        while (!q.empty())
        {
            p = q.front();
            q.pop();
            if (p)
            {
                std::cout << p->data << " ";
                q.push(p->lchild);
                q.push(p->rchild);
                if (p == r)
                {
                    std::cout << std::endl;
                    r = q.back();
                }
            }
        }
    }
    
    /**
     * 创建一颗二叉树
     */
    BSTree CreateBSTree()
    {
        int input = 5;
        BSTree tr = NULL;
    
        std::cout << "请输入树的节点值,输入0结束: ";
        std::cin >> input;
        while (input)
        {
            std::cout << BSTreeInsert(tr, input) << " "
                      << "目前层序遍历BST树序列:\n";
            VisitLevelBSTree(tr);
            std::cout << std::endl;
            std::cout << "请输入树的节点值,输入0结束: ";
            std::cin >> input;
        }
        return tr;
    }
    
    /***
     * 二叉排序树的删除
     * 1.如果是叶子节点x,直接删除
     * 2.如果x只有左儿子,或者只有右儿子,让子树成为被删除节点x的字数,替代x的位置
     * 3.节点有左、右两颗子树,令x的后继节点(或者前驱节点)替代x,
     *    然后从二叉树删除这个后记节点(或者前驱节点)
     * 所以需要额外写一个查找x的后继节点(或者前驱节点)的方法
     */
    /***
     * 查找节点x的父亲节点的函数
     */
    BSNode *FindNodeFather(BSTree tr, int x)
    {
        std::stack<BSNode *> s;
        BSNode *p = tr;
        while (p || !s.empty())
        {
            if (p)
            {
                s.push(p);
                p = p->lchild;
            }
            else
            {
                p = s.top();
                s.pop();
                if ((p->lchild && p->lchild->data == x) || (p->rchild && p->rchild->data == x))
                    return p;
                p = p->rchild;
            }
        }
        return NULL;
    }
    
    /**
     * 查找BST二叉树的直接后继
     */
    BSNode *FindDirectChild(BSTree tr, int x)
    {
        int next = 0;
        std::stack<BSNode *> s;
        BSNode *p = tr;
        while (p || !s.empty())
        {
            if (next && p)
                return p;
            if (p)
            {
                s.push(p);
                p = p->lchild;
            }
            else
            {
                p = s.top();
                s.pop();
    
                if (p->data == x)
                    next = 1;
                p = p->rchild;
            }
        }
        return NULL;
    }
    
    bool DeleteBSTreeNode(BSTree &tr, int x)
    {
        if (!tr)
            return false; //空树,还删除p =。=
    
        BSNode *p = tr;
        std::stack<BSNode *> s;
        while (!s.empty() || p)
        {
            if (p)
            {
                s.push(p);
                p = p->lchild;
            }
            else
            {
                p = s.top();
                if (p->data == x) //找到了这个节点
                {
                    if (!p->lchild && !p->rchild) //是叶子节点,直接删除
                    {
                        std::cout << "删除叶子节点 " << x << std::endl;
                        BSNode *tmp = FindNodeFather(tr, x);
                        if (!tmp)
                        {
                            //返回了空值,说明没有父节点,这个叶子节点是根节点
                            tr = NULL;
                            return true;
                        }
                        else
                        {
                            if (tmp->lchild && tmp->lchild == p)
                                tmp->lchild = NULL;
                            else if (tmp->rchild && tmp->rchild == p)
                                tmp->rchild = NULL;
                            else
                            {
                                std::cout << "-----代码写错了,删除叶子出现了不可能出现的情况-----";
                            }
                        }
                        free(p);
                        VisitBSTree(tr);
                        std::cout << std::endl;
                        return true;
                    }
                    else if (p->lchild && p->rchild)
                    {
                        std::cout << "删除双孩子节点 " << x << std::endl;
                        BSNode *t = FindDirectChild(tr, x);
                        if (t)
                        {
                            std::cout << "找到" << x << "后继节点:" << t->data << std::endl;
                            int deleteNum = 1000000;
                            p->data = t->data;
                            t->data = deleteNum;
                            DeleteBSTreeNode(tr, deleteNum);
                        }
                        else
                        {
                            std::cout << "-----代码写错了,删除双孩子出现了不可能出现的情况-----";
                        }
                        return false;
                    }
                    else if (!p->lchild || !p->rchild)
                    {
    
                        std::cout << "删除单孩子节点 " << x << std::endl;
                        BSNode *child;
                        if (p->lchild)
                            child = p->lchild;
                        else
                            child = p->rchild;
                        BSNode *tmp = FindNodeFather(tr, x);
                        if (!tmp)
                        {
                            //返回了空值,说明没有父节点,这个单孩子节点是根节点
                            tr = child;
                            std::cout << "删除根孩子节点,更新根节点为: " << tr->data << std::endl;
                        }
                        else
                        {
                            if (tmp->lchild && tmp->lchild == p)
                                tmp->lchild = child;
                            else if (tmp->rchild && tmp->rchild == p)
                                tmp->rchild = child;
                            else
                            {
                                std::cout << "-----代码写错了,删除单孩子出现了不可能出现的情况-----";
                            }
                        }
                        free(p);
                        VisitBSTree(tr);
                        std::cout << std::endl;
                        return true;
                    }
                    else
                    {
                        std::cout << "-----代码写错了,删除出现了不可能出现的情况-----";
                    }
                    return false;
                }
                s.pop();
                p = p->rchild;
            }
        }
        return false; //没有这个节点,直接返回了
    }
    
    

    碎碎念

    实现大概花了4个小时,比较慢,有些地方实在不能立刻理解,好在最后全部实现了 = = 。

    写得不错的参考:

    动态规划 - 最优二叉搜索树

    展开全文
  • //算法7.6 二叉排序树创建 //算法 7.7 二叉排序树的删除 #include<stdio.h> #include<stdlib.h> #define ENDFLAG '#' //char a[10]={'5','6','7','2','1','9','8','10','3','4','#'};//全局变量 ...

    此代码可以正常运行,下附有运行区

    //算法7.4 二叉排序树的递归查找
    //算法7.5 二叉排序树的插入
    //算法7.6 二叉排序树的创建
    //算法 7.7 二叉排序树的删除
    #include<stdio.h>
    #include<stdlib.h>
    #define ENDFLAG '#'
    //char a[10]={'5','6','7','2','1','9','8','10','3','4','#'};//全局变量
    typedef struct ElemType{	
    	char key;
    }ElemType;
    
    typedef struct BSTNode{
    	ElemType data;	//结点数据域
    	BSTNode *lchild,*rchild;	//左右孩子指针
    }BSTNode,*BSTree;
    
    
    //算法7.4 二叉排序树的递归查找
    BSTree SearchBST(BSTree T,char key) {
      //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
      //若查找成功,则返回指向该数据元素结点的指针,否则返回空指针
      if((!T)|| key==T->data.key) return T;       	            	//查找结束
      else if (key<T->data.key)  return SearchBST(T->lchild,key);	//在左子树中继续查找
      else return SearchBST(T->rchild,key);    		   			//在右子树中继续查找
    } // SearchBST
    
    
    
    //算法7.5 二叉排序树的插入
    void InsertBST(BSTree &T,ElemType e ) {
      //当二叉排序树T中不存在关键字等于e.key的数据元素时,则插入该元素
      if(!T) {                				//找到插入位置,递归结束
    		 BSTree S = new BSTNode;            		//生成新结点*S
             S->data = e;                  		//新结点*S的数据域置为e   
             S->lchild = S->rchild = NULL;	//新结点*S作为叶子结点
             T =S;            				//把新结点*S链接到已找到的插入位置
      }
      else if (e.key< T->data.key) 
          InsertBST(T->lchild, e );			//将*S插入左子树
      else if (e.key> T->data.key) 
          InsertBST(T->rchild, e);			//将*S插入右子树
    }// InsertBST
    
    
    
    //算法7.6 二叉排序树的创建
    void CreateBST(BSTree &T ) {
      //依次读入一个关键字为key的结点,将此结点插入二叉排序树T中
      T=NULL;
      ElemType e;
      scanf("%c",&e.key);       
      while(e.key!=ENDFLAG){   	//ENDFLAG为自定义常量,作为输入结束标志
        InsertBST(T, e);          	//将此结点插入二叉排序树T中
        scanf("%c",&e.key);			
      }//while            
    }//CreatBST
    
    void DeleteBST(BSTree &T,char key) {
      //从二叉排序树T中删除关键字等于key的结点
      BSTree p=T;BSTree f=NULL;                     			//初始化
      BSTree q;
      BSTree s;
      /*------------下面的while循环从根开始查找关键字等于key的结点*p-------------*/
      while(p){                  
       if (p->data.key == key) break;  	      	//找到关键字等于key的结点*p,结束循环
       f=p;                                			//*f为*p的双亲结点
       if (p->data.key> key)  p=p->lchild;     	//在*p的左子树中继续查找
       else p=p->rchild;  	                  		//在*p的右子树中继续查找
      }//while
    if(!p) return;                         		//找不到被删结点则返回
    
    /*―考虑三种情况实现p所指子树内部的处理:*p左右子树均不空、无右子树、无左子树―*/
    if ((p->lchild)&& (p->rchild)) {     		//被删结点*p左右子树均不空
         q = p;
    	 s = p->lchild;
         while (s->rchild)                			//在*p的左子树中继续查找其前驱结点,即最右下结点
           {q = s; s = s->rchild;}	         		//向右到尽头
         p->data = s->data;               			//s指向被删结点的“前驱”
         if(q!=p){
    		 q->rchild = s->lchild;     	//重接*q的右子树
    	 }
         else q->lchild = s->lchild;        		//重接*q的左子树
         delete s;
      }//if
    else{
    	if(!p->rchild) {               		//被删结点*p无右子树,只需重接其左子树
    		  q = p; p = p->lchild; 
    	  }//else if
    	else if(!p->lchild) {               		//被删结点*p无左子树,只需重接其右子树
    		 q = p; p = p->rchild;
    	  }//else if
    	/*――――――――――将p所指的子树挂接到其双亲结点*f相应的位置――――――――*/
    	  if(!f) T=p;                       			//被删结点为根结点
    	  else if (q==f->lchild) f->lchild = p;   	//挂接到*f的左子树位置
    	  else f->rchild = p;                 		//挂接到*f的右子树位置
    	  delete q;
    	}
    }//DeleteBST
    
    //算法 7.7 二叉排序树的删除
    
    //中序遍历
    void InOrderTraverse(BSTree &T)
    {
    	if(T)
    	{
    	InOrderTraverse(T->lchild);
    	printf("%c",T->data.key);
    	InOrderTraverse(T->rchild);
    	}
    }
    
    void main()
    {
    	BSTree T;
    	printf("请输入若干字符,用回车区分,以#结束输入\n");
    	CreateBST(T);
    	printf("当前有序二叉树中序遍历结果为\n");
    	InOrderTraverse(T);
    	printf("\n");
    	char key;//待查找或待删除内容
    	printf("请输入待查找字符\n");
    	getchar();
    	scanf("%c",&key);
    	BSTree result=SearchBST(T,key);
    	if(result)
    	{printf("找到字符:%c\n",key);}
    	else
    	{printf("未找到%c\n",key);}
    	printf("请输入待删除的字符\n");
    	getchar();
    	scanf("%c",&key);
    	DeleteBST(T,key);
    	printf("当前有序二叉树中序遍历结果为\n");
    	InOrderTraverse(T);
    	printf("\n");
    }
    
    
    

    在这里插入图片描述

    展开全文
  • Python实现二叉排序树/二叉查找树/二叉搜索树的遍历、查找、删除结点

    基本概述

    • 如何更加高效的完成对数据的查询和添加操作,例如↓↓↓
      在这里插入图片描述
    • 之前解决方案的优缺点
      在这里插入图片描述
    • 树结构解决方案:二叉排序树
      在这里插入图片描述

    二叉排序树的创建和遍历

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
            
    class BinarySortTree(object):
        def __init__(self):
            self.root = None
    
        # 添加结点
        def add(self, val):  
            node = TreeNode(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                # 判断传入结点的值和当前子树结点的值关系
                if node.val < temp_node.val:
                    if temp_node.left is None:
                        temp_node.left = node
                        return
                    else:
                        queue.append(temp_node.left)
                if node.val >= temp_node.val:
                    if temp_node.right is None:
                        temp_node.right = node
                        return
                    else:
                        queue.append(temp_node.right)
    
        # 中序遍历
        def in_order(self, node):
            if node is None:
                return
            self.in_order(node.left)
            print(node.val, end=" ")
            self.in_order(node.right)
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        t.in_order(t.root)
    '''输出结果
    1,3,5,7,9,10,12
    刚好是升序
    '''
    

    二叉排序树的删除

    删除时会遇到的情况

    • 要处理的各种情况
      在这里插入图片描述

    • 第一种情况:删除叶子结点
      在这里插入图片描述

    • 第二种情况:删除只有一棵子树的结点
      在这里插入图片描述

    • 第三种情况:删除有两课子树的结点
      在这里插入图片描述
      (1)上图为,target_node的右子树只有一个结点,那它就是最小的
      在这里插入图片描述
      (2)下图,假设当target_node的右子树,还有一个11,那么11就是最小的,需要把11的值放到target_node的位置
      在这里插入图片描述

    先实现查找要删除的结点

    '''上面代码一样,先省略'''
        def search(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要查找的值
            :return: 找到返回该node,没找到返回None
            '''    
            if node is None:
                return None
            if node.val == val:
                return node
            if val < node.val:
                return self.search(node.left, val)
            else:
                return self.search(node.right, val)
                
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        search_node =t.search(t.root, 3) # 3
        if search_node: # 只为测试用
        	print(search_node.val)
        else:
        	print(search_node)
    

    查找要删除节点的父结点

    '''上面代码一样,先省略'''
        # 查找结点的父结点
        def parent(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要找的父结点的值
            :return: 如果找到返回该父结点,如果没有返回None
            '''
            if node is None:  # 如果要找的值遍历完二叉树还不存在,由此退出并返回None
                return None
            if self.root.val == val:  # 根结点没有父结点
                return None
            # 如果当前结点的左子结点或者右子结点存在,并且值就是要找的,直接返回它的父结点
            if (node.left and node.left.val == val) or (node.right and node.right.val == val):
                return node
            else:
                # 如果要找的结点值小于父结点且它的左子结点存在,向左递归
                if val < node.val and node.left:
                    return self.parent(node.left, val)
                # 如果要找的结点值大于父结点且它的右子结点存在,向左递归
                elif node.val < val and node.right:
                    return self.parent(node.right, val)
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9]
        for item in note_array:
            t.add(item)
        # t.in_order(t.root)
        # print(t.search(t.root, 3))
        parent_node = t.parent(t.root, 1)  # 3
        if parent_node: # 只为输出测试
            print(parent_node.val)
        else:
            print(parent_node)
    

    完整实现二叉排序树的删除结点操作

    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinarySortTree(object):
        def __init__(self):
            self.root = None
    
        # 添加结点
        def add(self, val):  
            node = TreeNode(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                # 判断传入结点的值和当前子树结点的值关系
                if node.val < temp_node.val:
                    if temp_node.left is None:
                        temp_node.left = node
                        return
                    else:
                        queue.append(temp_node.left)
                if node.val >= temp_node.val:
                    if temp_node.right is None:
                        temp_node.right = node
                        return
                    else:
                        queue.append(temp_node.right)
    
        # 中序遍历
        def in_order(self, node):
            if node is None:
                return
            self.in_order(node.left)
            print(node.val, end=" ")
            self.in_order(node.right)
    
        # 删除节点
        def del_node(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要删除结点的值
            :return:
            '''
            if node is None:
                return
            # 先去找到要删除的结点
            target_node = self.search(node, val)
            if target_node is None:  # 如果没有找到要删除的结点
                return
            # 如果发现当前这棵二叉排序树只有一个结点
            if node.left is None and node.right is None:
                self.root = None # 根结点直接置空
                return
            # 去找到target_node的父结点
            parent = self.parent(node, val)
            # 删除的结点是叶子结点
            if target_node.left is None and target_node.right is None:
                # 判断target_node 是父结点的左子结点,还是右子结点
                if parent.left and parent.left.val == val:  # target_node 是左子结点
                    parent.left = None
                elif parent.right and parent.right.val == val:  # target_node 是右子结点
                    parent.right = None
            elif target_node.left and target_node.right:  # 删除有两颗子树的结点
                min_val = self.del_right_tree_min(target_node.right)
                target_node.val = min_val
            else:  # 删除只有一颗子树的结点
                if target_node.left:  # 如果要删除的结点target_node有左子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:  # target_node是parent左子结点
                            parent.left = target_node.left
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.left
                    else:
                        self.root = target_node.left
                else:  # 如果要删除的结点target_node有右子结点
                    if parent: # 如果target_node有父结点
                        if parent.left.val == val:
                            parent.left = target_node.right
                        else:  # parent.right.val == val,即是target_node是parent右子结点
                            parent.right = target_node.right
                    else:
                        self.root = target_node.right
    
        # 查找结点
        def search(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要查找的值
            :return: 找到返回该值,没找到返回None
            '''
            if node is None:
                return None
            if node.val == val:
                return node
            if val < node.val:
                return self.search(node.left, val)
            else:
                return self.search(node.right, val)
    
        # 查找结点的父结点
        def parent(self, node, val):
            '''
            :param node: 传入根结点
            :param val: 传入要找的父结点的值
            :return: 如果找到返回该父结点,如果没有返回None
            '''
            if node is None:  # 如果要找的值遍历完二叉树还不存在,由此退出并返回None
                return None
            if self.root.val == val:  # 根结点没有父结点
                return None
            # 如果当前结点的左子结点或者右子结点存在,并且值就是要要找的,直接返回它的父结点
            if (node.left and node.left.val == val) or (node.right and node.right.val == val):
                return node
            else:
                # 如果要找的结点值小于父结点且它的左子结点存在,向左递归
                if val < node.val and node.left:
                    return self.parent(node.left, val)
                # 如果要找的结点值大于父结点且它的右子结点存在,向左递归
                elif node.val < val and node.right:
                    return self.parent(node.right, val)
    
        def del_right_tree_min(self, node):
        	# 从target_node的右子树出发,查找它的左边最小结点,并返回删除结点的值
        	# 作用1:返回以node为根结点的二叉排序树的最小结点
        	# 作用2:删除 node 为根结点的二叉排序树的最小结点
            temp_node = node
            # 循环的查找左结点,直到找到最小值
            while temp_node.left:
                temp_node = temp_node.left
            # 这时 target就指向了最小结点
            # 调用删除方法,删除最小结点
            self.del_node(self.root, temp_node.val) # 注意传入的还是跟结点,从根结点开始查找
            return temp_node.val
    
    
    if __name__ == '__main__':
        t = BinarySortTree()
        note_array = [7, 3, 10, 12, 5, 1, 9, 2]
        for item in note_array:
            t.add(item)
        '''# 测试:删除叶子结点
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.in_order(t.root) # 1 3 7 10
        '''
    
        '''# 测试:删除只有一颗子树的结点
        t.del_node(t.root, 1)
        t.in_order(t.root) # 2 3 5 7 9 10 12 
        '''
        # 测试:删除有两颗子树的结点
        # t.del_node(t.root, 7)
        # t.in_order(t.root) # 1 2 3 5 9 10 12
        # t.del_node(t.root, 10)
        # t.in_order(t.root)  # 1 2 3 5 7 9 12
        # t.in_order(t.root)
    
        # 连续删除任意结点测试:
        t.del_node(t.root, 2)
        t.del_node(t.root, 5)
        t.del_node(t.root, 9)
        t.del_node(t.root, 12)
        t.del_node(t.root, 7)
        # t.del_node(t.root, 3)
        # t.del_node(t.root, 10)
        # t.del_node(t.root, 1)
        t.in_order(t.root)
    

    在这里插入图片描述

    展开全文
  • 从今天起,就给大家分享二叉排序树代码啦,首先给大家简单讲解一下相关概念。 二叉排序树也称为二叉查找树,二叉排序树是一棵空树或具有如下性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点...
  • 以下是C++控制台程序,实现了二叉排序树创建和遍历,仅是练习的小程序,分享一下。#include "stdafx.h"#include &lt;iostream&gt;using namespace std;//二叉树节点struct BiTree { int data; ...
  • 创建二叉排序树;判断一颗二叉树是否为二叉排序树;完整代码和PPT演示
  • 一、二叉排序树概述 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。对于二叉排序树的任何...2.1 创建和遍历二叉排序树 【案例描述】 给定如下数组: arr = {7, 3, 10, 12,
  • //二叉排序数(二叉搜索,二叉查找) #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> using namespace std; #define end 32767 // 定义结束标志 //结点结构 typedef struct BiTNode { int data...
  • 创建二叉排序树,先序遍历,中序遍历,判断是否存在关键点 这是所要创建的二叉排序树,a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8},请先在草稿纸上画出图形,再看程序 代码实现: #include #include typedef ...
  • 给定一个数列,创建二叉排序树(BST) 遍历二叉排序树(中序遍历) 删除二叉排序树的节点 其中,二叉排序树的删除节点步骤较为繁琐,思路总结如下: 一.如果要删除的节点是叶子节点 1.找到要删除节点:targetNode; ...
  • 文章目录二叉排序树 BST性质:二叉排序树的查找二叉排序树的插入二叉排序树的创建二叉排序树的删除平衡二叉查找树 AVL性质分类LL原树:插入结点:右单旋转:代码实现:RR原树:插入结点:左单旋转:代码实现:LR原树...
  • 文章目录二叉搜索树/二叉排序树/二叉查找树.1 定义.2 性质二叉搜索树创建二叉搜索树查找.1 查找步骤.2 查找性能分析二叉树插入与删除 二叉搜索树/二叉排序树/二叉查找树 .1 定义 二叉排序树(Binary Sort Tree)...
  • 二叉排序树

    千次阅读 2019-07-19 21:33:05
    文章目录二叉排序树的定义结点定义二叉排序树的操作创建查找插入删除 二叉排序树的定义 二叉排序树,又叫二叉查找树,如果非空,则具有以下性质: 若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值;...
  • 二叉排序树查找算法代码 什么是二叉排序树:首先是一棵二叉树,或者为空,或者满足以下条件: 1,左子树不空,所有左子树值都小于根节点; 2,右子树不空,所有右子树值都大于根节点; 3,根节点的左右子树也是...
  • 二叉排序树概述: 二叉排序树:BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比...二叉排序树创建和遍历(以中序遍历为例) public clas...
  • 二叉排序树 二叉排序树(Binary sort tree,BST),又叫二叉查找树、二叉搜索树,或者是一棵空树;或者是具有下列性质的二叉树: ​ (1)若它的左子树不为...关于二叉排序树节点的代码实现: public class TreeNode { p
  • 代码里有二叉排序树插入操作递归算法,二叉排序树插入操作非递归算法,二叉排序树删除操作,创建二叉排序树,二叉排序树查找递归算法,二叉排序树查找非递归算法
  • 二叉排序树 1、二叉排序树的介绍
  • 二叉排序树及其C代码

    2015-03-12 20:18:40
    1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:  (1)若它的左子树非空,则左子树上所有结点的值均...
  • 二叉排序树 二叉排序树又称“二叉查找树”、“二叉搜索树”。 二叉排序树:或者是一棵空树,或者是具有下列性质的二叉树: 1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2. 若它的右子树...
  • 二叉排序树1、定义2、性质3、操作3.1 查找 1、定义 \quad \quad二叉排序树又称二叉搜索树、二叉查找树。 \quad \quad二叉排序树或是空树,或是满足以下性质的二叉树: (1)若其左子树非空,则左子树上所有结点的值...
  • 什么是二叉排序树 二叉排序树,又称二叉查找树,是二叉树的一种。它要求: 如根结点上有左结点,则左结点的值一定小于根结点 如根结点上有右结点,则右结点的值一定大于根结点 创建结点类Node 创建结点类Node用于...
  • 二叉排序树创建和遍历排序二叉排序树创建和遍历排序 二叉排序树创建和遍历排序 直接看代码的注解详细说明 1:先创建二叉树的节点 //创建Node节点 class Node{ int value;//节点值 Node left; //左节点 ...
  • /*所谓二叉排序树,即左子树的值小于根节点,右子树的值大于根节点;中序遍历的结果从左到右为升序*/ typedef struct node { int data;  struct node *lchild;  struct node *rchild; }node; /*查找x*/ ...
  • 二叉排序树-BST: (Binary Sort(Search) Tree), 对于二叉排序树的任何一个非叶子节点,要求左子...其实,二叉排序树创建比较简单,其实就是一个个节点加上,怎么将节点往树上加呢? 与父子树进行进行比较,比父子树...
  • 数据结构 二叉排序树前言概念介绍二叉排序树存在意义的思考操作以及代码展示插入元素查找元素删除元素二叉排序树的优缺点及解决方法优点缺点解决方案 前言 今天在学习红黑树的时候,看到了引导课拿二叉排序树举例,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,099
精华内容 6,839
关键字:

创建二叉排序树代码