首页 > 其他 > 详细

数据结构学习笔记4.2--插入节点

时间:2014-01-28 08:50:43      阅读:357      评论:0      收藏:0      [点我收藏+]

插入一个节点,首先要找到插入的地方。需要从根节点开始,找到需要插入节点的父节点,

如果插入节点比父节点小,则插入到左子节点处;如果插入节点比父节点大,则插入到右子节点处。

 

图解:根据二叉树的节点的特点,找到插入节点的位置。

bubuko.com,布布扣

 

代码:

bubuko.com,布布扣
    /**
     * 插入节点,跟查找节点代码类似,只是在遇到null时,将节点插入,修改引用
     * @param id key值
     * @param dd value值
     */
    public void insert(int id, double dd)
    {
        // 插入的节点
        Node newNode = new Node();
        newNode.iData = id;
        newNode.dData = dd;

        // 如果根节点为空,则插入节点为根节点
        if (root == null)
        {
            root = newNode;
        }
        else
        {
            // 当前节点,引用会随在查找变化
            // 由于查找要插入的节点是从根基点开始,所以root引用赋值给current
            Node current = root;

            // 父节点
            // 有父节点的引用,才能够给子节点leftChild或者rightChild赋值
            Node parent;
            
            while (true)
            {
                // 保存父节点的引用,因为后面在查找时,current的引用一定会为null,
                // 此时说明已经找到插入节点的位置了
                parent = current;
                
                // 插入节点在左子树
                if (id < current.iData)
                {
                    current = current.leftChild;
                    if (current == null)
                    {
                        parent.leftChild = newNode;
                        return;
                    }
                }
                // 插入节点在右子树
                else
                {
                    current = current.rightChild;
                    if (current == null)
                    {
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }
bubuko.com,布布扣

插入节点与查找类似,区别:

1.需要保存父节点,因为需要用父节点来连接字节点,建立插入节点在整棵树的位置。

2.在判断插入节点在左子树,或者右子树时,current一定为null,此时需要把newNode的引用赋值上去。

3.while循环以true为判断条件,这是很少用的。只要在确定一定都会有return时,才能够使用,不然会陷入死循环。由于二叉树的特点,肯定能找到插入节点的位置(除非内存溢出),

因此,循环里面的return一定可以跳出。

数据结构学习笔记4.2--插入节点

原文:http://www.cnblogs.com/winlrou/p/3535277.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!