首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 一棵二叉树的头节点是不停的变换，而我有要对树操作，请问如何处理？谢谢大家！ [无满意答案结贴,结贴人:kinsion]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    • 揭帖率：
    发表于：2007-12-07 17:10:15 楼主
    我的问题是，我在处理一棵二叉树的时候。譬如进行添加，删除。但有要保持树的平衡性，所以要不断的维持平衡，所以树的头节点不停的变换，我该如何处理呢，我处理树每次都要用树的头节点，应该设一个没用的头节点作为，但我不知道如何处理，大家指教一下。
    100  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iambic
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 4

      3

      3
    发表于：2007-12-07 17:18:241楼 得分:0
    把根节点放到一个struct中保存起来，把这个struct作为你的树接口。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-07 17:21:382楼 得分:0
    不好意思，还有一点，我的删除函数只有一个参数，没有两个哦
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-07 17:26:143楼 得分:0
    我真正的根节点也要参与树的平衡，而你所说的把那个根节点保存起来，那又如何和真正的根节点联系起来，譬如我要对树进行旋转，我如何操作呢？
    我的新的真正的根节点又如何和保存的哪个节点联系起来呢？谢谢！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • guosha
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-08 09:58:104楼 得分:0
    一个笨方法，对每次增加或删除后的元素集合都去生成一棵平衡树。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • happy__888
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 11

      9

      3
    发表于：2007-12-10 19:06:355楼 得分:0
    1楼的说过了

    假如你原来的二叉树是用 Tree结构来表示的, 现在你新建立一个结构,叫做MyTree
    strct Mytree {
      Tree * pRoot;  // 用来保存你的变化后的根节点
      Tree * pTree;  // 根节点
    }
    原来对Tree的操作继续, 无非是每次变化后, 把根节点回填到这个Mytree里面而已

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • yu_xm
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-10 20:00:006楼 得分:0
    可以通过随机选取右子树的最小元素或左子树的最大值来代替被删除元素来消除这种不平衡
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-12 10:58:137楼 得分:0
    非常感谢5楼！
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-12 11:26:378楼 得分:0
    5楼的能不能给我具体的例子。小弟悟性不高，理解不够透彻。多谢
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • kinsion
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2007-12-12 11:37:539楼 得分:0
    我的添加和删除不能返回头节点，而是返回布尔型的，着如何操作呢？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • happy__888
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：

    • 11

      9

      3
    发表于：2008-01-13 15:39:4910楼 得分:0
    1 改一下返回, 如果成功返回头节点, 不成功返回NULL指针


    2 你所说的平衡树的要求, 什么是平衡,如何确定这个平衡, 这个过成当中,必然会涉及到确认根节点的问题
      只要确认了哪个是根节点, 记录回去就是了

    3 例子, 给不了, 不知道你的具体需求
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tjltail
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-01-13 15:46:5411楼 得分:0
    C/C++ code
    typedef enum
{
    _LEFT_LEFT,  //the new node insert in the left tree of the left node
    _LEFT_RIGHT, //the new node insert in the left tree of the right node 
    _RIGHT_RIGHT,//the new node insert in the right tree of the right node
    _RIGHT_LEFT, //the new node insert in the right tree of the left node
    _BALANCE     //the tree is balance
}_NOBALANCE_TYPE;


template<class typeKey>
class CAvlTreeIndex
{
    typedef CAvlTreeNode<typeKey> node;
private:
    node* head;  //the head node of the a v l tree
public:
    CAvlTreeIndex(){}
    explicit CAvlTreeIndex(typeKey value)
    {
        head = new node(value);
    }
    // insert one node into the a v l tree
    void insert_Node(typeKey value);
    //delete a node whose value is value from the a v l tree
    void delete_Node(typeKey value);
    //get the location of the node whose value is value 
    //if the node is in the a v l tree ,return the node 
    //else return null
    CAvlTreeNode<typeKey>* find_key_inTree(typeKey value)const;
    bool is_key_inTree(typeKey value) const;
    //find the parent of the node which will be inserted    
    inline CAvlTreeNode<typeKey>* getParent_InsertNode(typeKey value ,bool& isInLeftChild) const;
    //after insert the node ,adjust the tree to balance
    inline void adjust_avl_tree(node* parent ,bool isLeftNode ,bool increase = true);
    //deal with the condition of left - left
    inline void rotate_cond_ll(node* rotate_node);
    //deal with the condition of left - right
    inline void rotate_cond_lr(node* rotate_node);
    //deal with the condition of right - left
    inline void rotate_cond_rl(node* rotate_node);
    //deal with the condition of right - right
    inline void rotate_cond_rr(node* rotate_node);

    void print()
    {
        print(head);
    }
    void print(node* head)
    {
        if(head != 0)
        {
            print(head->left_child_node);
            cout<<head->value_node<<" "<<head->deepth<<endl;
            print(head->right_child_node);
        }
    }
    ~CAvlTreeIndex(); 
};
#endif


    这个是我写的avl树的一个例子，其实很简单的，只保留一个head节点，当head节点变化的时候，将head的值重新赋值就可以了
    比如其中的一个函数：
    C/C++ code
    ///////////////////rotate_cond_ll//////////////
//deal with the condition of left - left
template<class typeKey>
inline void CAvlTreeIndex<typeKey>::rotate_cond_ll(node* rotate_node)
{
    node* left_node = rotate_node->left_child_node;
    node* _temp_node = left_node->right_child_node;

    left_node->right_child_node = rotate_node;
    rotate_node->left_child_node = _temp_node;


    
    if(rotate_node == head)
    {
        head = left_node;
        left_node->parent_node = 0 ;
    }
    else
    {
        bool isleftNode = rotate_node->parent_node->isLeftNode(rotate_node);
        if(isleftNode)    rotate_node->parent_node->left_child_node = left_node;
        else              rotate_node->parent_node->right_child_node = left_node;
        left_node->parent_node = rotate_node->parent_node;
    }

    //adjust the deepth of the rotate node
    rotate_node->adjust_deepth();
    left_node->adjust_deepth();
    if(left_node != head)
    {
        rotate_node->parent_node->adjust_deepth();
    }
    rotate_node->parent_node = left_node;
}

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • chenzhiyubuaa
    • 等级:
    • 可用分等级：
    • 总技术专家分：
    • 总技术专家分排名：
    发表于：2008-01-13 23:50:2812楼 得分:0
    红黑树

    #define BLACK_COLOR 0
    #define RED_COLOR 1

    typedef struct black_red_node{
    int key;
    int color;
    struct black_red_node* left;
    struct black_red_node* right;
    struct black_red_node* parent;
    }BlackRedNode;

    void LeftRotate(BlackRedNode** _Tree, BlackRedNode*const x)
    {
    BlackRedNode* tree = *_Tree;
    BlackRedNode* y = x->right;

    x->right = y->left;
    if (y->left != NULL)
    y->left->parent = x;
    y->parent = x->parent;
    if (y->parent == NULL){
    *_Tree = y;
    } else if (x == x->parent->left){
    x->parent->left = y;
    } else {
    x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
    }

    void RightRotate(BlackRedNode** _Tree, BlackRedNode* const y)
    {
    BlackRedNode* tree = *_Tree;
    BlackRedNode* x = y->left;

    y->left = x->right;
    if (x->right != NULL)
    x->right->parent = y;
    x->parent = y->parent;
    if (x->parent == NULL){
    *_Tree = x;
    } else if (y == y->parent->left){
    y->parent->left = x;
    } else {
    y->parent->right = x;
    }
    x->right = y;
    y->parent = x;
    }

    void BlackRedInsertFixup(BlackRedNode** _Tree, BlackRedNode* z)
    {
    BlackRedNode* tree = *_Tree;
    BlackRedNode* y;

    while (z->parent != NULL && z->parent->color == RED_COLOR){
    if (z->parent == z->parent->parent->left){
    y = z->parent->parent->right;
    if (y != NULL && y->color == RED_COLOR){
    /* case 1 */
    z->parent->color = BLACK_COLOR;
    y->color = BLACK_COLOR;
      z->parent->parent->color = RED_COLOR;
      z = z->parent->parent;
      } else {
      if (z == z->parent->right){
    /* case 2 */
    z = z->parent;
    LeftRotate(_Tree, z);
    }
    /* case 3 */
    z->parent->color = BLACK_COLOR;
    z->parent->parent->color = RED_COLOR;
    RightRotate(_Tree, z->parent->parent);
    }
    } else {
    y = z->parent->parent->left;
    if (y != NULL && y->color == RED_COLOR){
    /* case 1' */
    z->parent->color = BLACK_COLOR;
    y->color = BLACK_COLOR;
    z = z->parent->parent;
    } else {
    if (z == z->parent->left){
    /* case 2' */
    z = z->parent;
    RightRotate(_Tree, z);
    }
    /* case 3' */
    z->parent->color = BLACK_COLOR;
    z->parent->parent->color = RED_COLOR;
    LeftRotate(_Tree, z->parent->parent);
    }
    }
    }
    (*_Tree)->color = BLACK_COLOR;
    }

    void BlackRedInsert(BlackRedNode** _Tree, BlackRedNode* z)
    {
    BlackRedNode* tree = *_Tree;
    BlackRedNode* y = NULL;
    BlackRedNode* x = tree;

    while (x != NULL){
    y = x;
    if (z->key < x->key)
    x = x->left;
    else
    x = x->right;
    }
    z->parent = y;
    if (y == NULL){
    *_Tree = z;
    z->left = NULL;
    z->right = NULL;
    z->color = BLACK_COLOR;
    return;
    }
    else if (z->key < y->key)
    y->left = z;
    else
    y->right = z;
    z->left = NULL;
    z->right = NULL;
    z->color = RED_COLOR;
    BlackRedInsertFixup(_Tree, z);
    }
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved