menu 首页 标签 归档 视频 关于
数据结构-二叉排序树(三)

一言加载中...

什么是二叉排序树?

二叉排序树。又称二叉查找树,对于一个非空的二叉排序树:

  • 若左子树不为空,则左子树的值均小于根节点的值;
  • 若右子树不为空,则右子树的值均大于根节点的值;
  • 使用中序遍历,即可将数据从小到大输出;

二叉排序树的功能实现理论

插入数据

  • 复制一个新的根节点CurrRoot(防止直接对根节点进行操作)
  • 如果currRoot为空,那么将添加的新节点赋值给CurrRoot节点
  • 如果CurrRooot不为空:比较CurrRoot节点与NewNode(新节点)值的大小
    • 如果 CurrRoot的值大于NewNode(新节点)的值。判断CurrRoot的LeftChild是否为空:
      • 如果CurrRoot的LeftChild节点为空,则将NewNode的值赋值给CurrRoot的LeftChild节点;
      • 如果CurrRoot的LeftChild节点非空,则将CurrRoot的LeftChild节点作为CurrRoot节点,继续遍历,直到找到合适的位置
    • 如果 CurrRoot的值小于等于NewNode(新节点)的值。判断CurrRoot的RightChild是否为空:
      • 如果CurrRoot的RightChild节点为空,则将NewNode的值赋值给CurrRoot的RightChild节点;
      • 如果CurrRoot的RightChild节点非空,则将CurrRoot的RightChild节点作为CurrRoot节点,继续遍历,直到找到合适的位置

删除数据

对叶子节点进行删除

delete

删除方式:直接进行删除

以删除51为例:

  1. 判断51是父节点的左孩子还是右孩子;
  2. 这里知道51是父节点47的右子节点
  3. 47节点的rightChild=null

对仅有左子树或者右子树的既然点进行删除

delete single son

删除35节点思想:

让35节点的子节点37的父节点指向35节点的父节点47;让35的父节点47的左子节点指向35的右子节点

删除99节点思想:

让99节点的子节点93的父节点指向99节点的父节点88;让99的父节点88的右子节点指向99的左子节点

对左右节点都有的节点进行删除

删除47节点思想:

  1. 将47节点的右子节点51作为临时根节点
  2. while循环得到当前子树的最小节点(当前根节点的左子节点的左子节点)
  3. 将47节点的值替换成48节点的值
  4. 将叶子节点48删除

二叉排序树的实现

树的节点类:TreeNode

class TreeNode
{
    public TreeNode Parent;
    public TreeNode leftChild;
    public TreeNode rightChild;
    public int data;

    private TreeNode() { }
    public TreeNode(int item)
    {
        this.data = item;
    }
}

排序二叉树

class LinkTree
{
    TreeNode root = null;

    public void Add(TreeNode item){...}

    /// 查找是否含有某元素
    /// <param name="item">要查找的元素</param>
    /// <returns>该元素的节点</returns>
    public TreeNode Find(int item)&#123;...&#125;

    public bool Delete(int item)
    &#123;
        TreeNode node = root;
        while(true)
        &#123;
            if (node == null) return false;
            if(node.data==item)
            &#123;
                Delete(node);
                return true;
            &#125;
            if (node.data > item)
                node = node.leftChild;
            else
                node = node.rightChild;
        &#125;

    &#125;
    private void Delete(TreeNode node)&#123;... &#125;
    
    /// 中序
    /// <param name="tree"></param>
    public void InOrderTraverse()
    &#123;
        InOrderTraverse(root);
    &#125;
    private void InOrderTraverse(TreeNode tree)
    &#123;
        if (tree == null) return;

        InOrderTraverse(tree.leftChild);
        Console.Write(tree.data + " ");
        InOrderTraverse(tree.rightChild);
    &#125;

添加节点

public void Add(TreeNode item)
&#123;
    if (root == null)
        root = item;
    else
    &#123;
        TreeNode current = root;
        while(true)
        &#123;
            if(current.data>item.data)
            &#123;
                if (current.leftChild == null)
                &#123;
                    current.leftChild = item;
                    item.Parent = current;
                    break;
                &#125;
                else
                &#123;
                    current = current.leftChild;
                &#125;
            &#125;
            else  //current.data<=item.data
            &#123;
                if(current.rightChild==null)
                &#123;
                    current.rightChild = item;
                    item.Parent = current;
                    break;
                &#125;
                else
                &#123;
                    current = current.rightChild;
                &#125;
            &#125;
        &#125;
    &#125;
&#125;

节点的查找

 public TreeNode Find(int item)
&#123;
    TreeNode node = root;
    while (true)
    &#123;
        if (node == null) return null;
        if (node.data == item) return node;
        else if (node.data > item)
            node = node.leftChild;
        else
            node = node.rightChild;
    &#125;
&#125;

删除节点

private void Delete(TreeNode node)
&#123;
    //如果要删除的节点是叶子节点
    if(node.leftChild==null && node.rightChild==null)
    &#123;
        //如果该节点为根节点
        if (node.Parent == null)   //说明是根节点
            root = null;
        else if(node.Parent.leftChild==node)    //要删除的是左叶子结点
        &#123;
            node.Parent.leftChild = null;
        &#125;
        else if(node.Parent.rightChild==node)   //要删除的是右叶子结点
        &#123;
            node.Parent.rightChild = null;
        &#125;
        return;
    &#125;
    //左子节点为空 && 右子节点不为空
    if(node.leftChild==null && node.rightChild!=null)
    &#123;
        if (node.Parent.leftChild == node)
        &#123;
            node.rightChild.Parent = node.Parent;
            node.Parent.leftChild = node.rightChild;
        &#125;
        else
        &#123;
            node.rightChild.Parent = node.Parent;
            node.Parent.rightChild = node.rightChild;
        &#125;
        return;
    &#125;
    //左子节点不为空 && 右子节点为空
    if (node.leftChild!=null && node.rightChild==null)
    &#123;
        if (node.Parent.leftChild == node)
        &#123;
            node.rightChild.Parent = node.Parent;
            node.Parent.leftChild = node.rightChild;
        &#125;
        else if(node.Parent.rightChild == node)
        &#123;
            node.leftChild.Parent = node.Parent;
            node.Parent.rightChild = node.leftChild;
        &#125;
        return;
    &#125;

    TreeNode curr = node.rightChild;
    while(curr.leftChild==null)
    &#123;
        curr = curr.leftChild;
    &#125;
    node.data = curr.data;
    curr.Parent.leftChild = null;
    return;
&#125;

result

TonyChenn
2018-10-20
学算法好心累,心疼我的头发crying...
写博客不易,请我喝杯咖啡?

评论

arrow_upward