做网页设计网站有哪些,中信建设有限责任公司是央企吗,小程序定制开发和模板有什么区别,wordpress淘宝客建站教程视频一、红黑树
红黑树是一种自平衡的二叉搜索树#xff0c;它通过约束节点的颜色和结构来保持平衡。红黑树是由 Rudolf Bayer 在1972年发明的#xff0c;被认为是一种优秀的平衡树结构#xff0c;广泛应用于各种数据结构和算法中。
1.红黑树的性质 1. 每个结点是红的或者黑的…一、红黑树
红黑树是一种自平衡的二叉搜索树它通过约束节点的颜色和结构来保持平衡。红黑树是由 Rudolf Bayer 在1972年发明的被认为是一种优秀的平衡树结构广泛应用于各种数据结构和算法中。
1.红黑树的性质 1. 每个结点是红的或者黑的 2. 根结点是黑的 3. 每个叶子结点是黑的因为这条性质一般用叶子结点在代码中被特殊表示 4. 如果一个结点是红的则它的两个儿子都是黑的不存在相邻红色 5. 从任一节点到叶子节点所包含的黑色节点数目相同即黑高度相同 6. 最长路径长度不超过最短路径长度的2倍2n-1一条黑红黑红…一条全黑 2.红黑树和AVL树 所以红黑树的查询效率略低与AVL的查询红黑树和AVL插入的速度差不多红黑树删除的速度比AVL快因为AVL删除最多需要log(N)次旋转 3.红黑树的应用场景 c stl map,set红黑树的封装进程调度cfs用红黑树存储进程的集合把调度的时间作为key那么树的左下角时间就是最小的内存管理每次使用malloc的时候都会分配一块小内存出来那么这么块就是用红黑树来存如何表述一段内存块呢用开始地址长度来表示所以key-开始地址val-大小epoll中使用红黑树管理socketfdnginx中使用红黑树管理定时器中序遍历第一个就是最小的定时器 二、代码实现
1.结构体定义 红黑树是一种特殊的二叉树所以其实现和二叉树类似。但需要加上color用来标记颜色。实现如下 #define RED 0
#define BlACK 1typedef int KEY_TYPE;typedef struct _rbtree_node {unsigned char color;//颜色struct _rbtree_node *left;//左子树struct _rbtree_node *right;//右子树struct _rbtree_node *parent;//父结点KEY_TYPE key;void *value;} rbtree_node;//红黑树结点typedef struct _rbtree {rbtree_node *root;//根结点rbtree_node *nil;//通用叶子结点
} rbtree;//红黑树
2.红黑树的左旋和右旋 左旋动三个方向改6个指针。 左旋如上图所示 我们需要改的方向为 1.between E and S和S 2.E和S 3.S和parents 右旋和左旋原理一样不做过多赘述。 代码实现如下
//左旋leftRotate(T,x)---中右-左中
//降低X结点的高度提高X结点右结点即Y的高度。
void _left_rotate(rbtree *T, rbtree_node *x) {rbtree_node *y x-right;//1x-right y-left;//x的右子树指向y的左子树if (y-left ! T-nil) {y-left-parent x;//y的左子树的父节点指向x}//2y-parent x-parent;//y的父结点指向x的父结点if (x-parent T-nil) {//如果x是根结点T-root y;} else if (x x-parent-left) {x-parent-left y;//本来指向x结点的父指针改成指向y} else {x-parent-right y;}//3y-left x;//y的左子树指向x结点x-parent y;//x的父节点指向y
}//右旋
//copy左旋的代码
//left改成rightright改成left
//x改成yy改成x
void _right_rotate(rbtree *T, rbtree_node *y) {rbtree_node *x y-left;//1y-left x-right;if (x-right ! T-nil) {x-right-parent y;}//2x-parent y-parent;if (y-parent T-nil) {T-root x;} else if (y y-parent-right) {y-parent-right x;} else {y-parent-left x;}//3x-right y;y-parent x;
}
3.红黑树插入结点与插入维护红黑树的三种情况
1插入结点 插入这个结点之前原来的红黑树是满足红黑树性质的插入就是不断的对比key最终找到位置。 那么我们需要考虑一个问题那就是插入的结点应该上什么色 我们通过性质发现 如果新结点是黑色违背了第5条性质 如果新结点是红色可能违背第4条性质 第四条性质我们可以通过旋转与上色的方式修复所以在我们插入结点的时候我们始终认为新结点是红色。 代码实现如下
//因为传入的key可能是字符可能是整形所以要提取出来
//这里可以看出其实可以封装成一个模板
int key_compare(KEY_TYPE a, KEY_TYPE b) {//这里假设是intif (a b) {return 1;} else if (a b) {return -1;} else {return 0;}
}
void rbtree_insert(rbtree *T, rbtree_node *z) {//找位置rbtree_node *x T-root;rbtree_node *y T-nil;//y是x的父节点while (x ! T-nil) {//二分找位置y x;if (key_compare(z-key, x-key) 0) {x x-left;} else if (key_compare(z-key, x-key) 0) {x x-right;} else {//如果key相等看自己的业务情景//重复插入可以不修改直接退出可以修改valreturn;}}//插入z-parent y;if (y T-nil) {T-root z;} else if (key_compare(z-key, y-key) 0) {y-left z;} else {y-right z;}z-left T-nil;z-right T-nil;z-color RED;//维护红黑树rbtree_insert_fixup(T, z);
}
2插入结点后维护红黑树 我们知道新增结点是红色如果新结点是父节点也是红色那么就需要维护红黑树了。 此时有几种情况 1.父结点是爷结点是左子树 1叔结点是红色的 i将叔结点和父结点变黑爷结点变红 ii将当前结点变成爷结点因为爷结点是红爷结点的父节点也可能是红所以要递归维护 2叔结点是黑色的且新结点是左子树 i将父结点变成黑色爷结点变成红色 ii以爷结点为中心右旋 3叔结点是黑色的且新结点是右子树 i以父结点为中心左旋 ii将父结点变黑色爷结点变红色 (iii) 以爷结点为中心右旋 2.父结点是爷结点是右子树 1叔结点是红色的 i将叔结点和父结点变黑爷结点变红 ii将当前结点变成爷结点因为爷结点是红爷结点的父节点也可能是红所以要递归维护 2叔结点是黑色的且新结点是左子树 i以父结点为中心右旋 ii将父结点变黑色爷结点变红色 (iii) 以爷结点为中心左旋 3叔结点是黑色的且新结点是右子树 i将父结点变成黑色爷结点变成红色 ii以爷结点为中心左旋 //修复第4条性质
void rbtree_insert_fixup(rbtree *T, rbtree_node *z) {while (z-parent-color RED) {//父结点是红色的需要调整if (z-parent z-parent-parent-left) {//如果父结点是爷结点是左子树rbtree_node *y z-parent-parent-right;//叔结点if (y-color RED) {//叔结点是红色的//先变色叔,父变黑z-parent-color BLACK;y-color BLACK;//爷结点变红z-parent-parent-color RED;//下面的调整完了调整上面z z-parent-parent;} else {//叔父结点是黑色if (z z-parent-right) {//新节点是在右边z z-parent;rbtree_left_rotate(T, z);}z-parent-color BLACK;z-parent-parent-color RED;rbtree_right_rotate(T, z-parent-parent);}} else {// 如果父结点是爷结点是右子树rbtree_node *y z-parent-parent-left;//叔父结点if (y-color RED) {//叔父结点是红色的//先变色叔,父变黑z-parent-color BLACK;y-color BLACK;//爷结点变红z-parent-parent-color RED;//下面的调整完了调整上面z z-parent-parent;} else {//叔父结点是黑色if (z z-parent-left) {//新节点是在左边z z-parent;rbtree_right_rotate(T, z);}z-parent-color BLACK;z-parent-parent-color RED;rbtree_left_rotate(T, z-parent-parent);}}}//最后别忘了根节点始终是黑色T-root-color BLACK;
}
4.红黑树删除结点与删除维护红黑树的四种情况
(1)删除结点 我们定义 覆盖结点z被指定删除的结点实际上被覆盖删除结点y实际上被删除的结点一般是后继结点轴心结点x维护红黑树的结点 红黑树删除结点根据改结点的左右子树分为三种情况 没有左右子树有且仅有一个子树左右子树都有 对不同情况的处理 情况1直接删除该结点情况2将该结点的唯一子树挂到父结点上然后删除该结点 情况3找一个删除结点y后继结点覆盖 指定结点z然后删除 删除结点y对于这个删除结点y来说它的情况一定是情况1或情况2 rbtree_node *rbtree_mini(rbtree *T, rbtree_node *x) {while (x-left ! T-nil) {x x-left;}return x;
}//找后继结点
rbtree_node *rbtree_successor(rbtree *T, rbtree_node *x) {rbtree_node *y x-parent;//右子树不为空则找右子树中最左的元素if (x-right ! T-nil) {return rbtree_mini(T, x-right);}//找到结点第一个父结点while ((y ! T-nil) (x y-right)) {x y;y y-parent;}return y;
}//覆盖结点z
//删除结点y
//轴心结点x
rbtree_node *rbtree_delete(rbtree *T, rbtree_node *z) {rbtree_node *y T-nil;rbtree_node *x T-nil;if ((z-left T-nil) || (z-right T-nil)) {y z;//如果没有孩子或只有一个} else {//如果有两个子树则找后继y rbtree_successor(T, z);}//一般x是y的右子树找到轴心结点if (y-left ! T-nil) {x y-left;} else if (y-right ! T-nil) {x y-right;}//将该结点的唯一子树挂到父结点上然后删除该结点x-parent y-parent;if (y-parent T-nil) {//根结点T-root x;} else if (y y-parent-left) {y-parent-left x;} else {y-parent-right x;}//进行覆盖操作if (y ! z) {z-key y-key;z-value y-value;}//黑色才需要调整if (y-color BLACK) {rbtree_delete_fixup(T, x);}return y;
}
(2)维护红黑树 删除一个结点该结点是什么颜色的时候才需要维护红黑树呢 如果是红色没有违反任何性质。所以如果是红色直接删除即可无需维护如果是黑色黑色被删除那么必定违反第5条性质破坏了黑高所以我们需要针对这一情况进行维护 如果当前结点是父结点的左子树的情况可以归纳出来四种情况。 当前结点是父结点的左子树的情况 1. 当前结点的兄弟结点是红色的 i兄弟节点变成黑色 ii父节点变成红色 iii父节点做左旋 iiii将兄弟结点调整为父节点的右子树 2. 当前结点的兄弟结点是黑色的而且兄弟结点的两个孩子结点都是黑色的 i兄弟节点变成红色 ii轴心结点变为父节点 3. 当前结点的兄弟结点是黑色的而且兄弟结点的左孩子是红色的右孩子是黑色的 i将左孩子涂黑 ii将兄弟节点变红 iii对兄弟节点右旋 iiii将兄弟结点调整为父节点的右子树 iiiii现在情况3就会变成情况4接着做情况4的步骤 4. 当前结点的兄弟结点是黑色的而且兄弟结点的左孩子是黑色的右孩子是红色的 i将兄弟节点换成父节点的颜色 ii把父节点和兄弟节点的右孩子涂黑 iii对父节点做左旋 iiii设置x指针指向根节点 当前结点是父结点的右子树的情况 1. 当前结点的兄弟结点是红色的 i兄弟节点变成黑色 ii父节点变成红色 iii父节点做右旋 iiii将兄弟结点调整为父节点的左子树 2. 当前结点的兄弟结点是黑色的而且兄弟结点的两个孩子结点都是黑色的 i兄弟节点变成红色 ii轴心结点变为父节点 3. 当前结点的兄弟结点是黑色的而且兄弟结点的左孩子是黑色的右孩子是红色的 i将右孩子变黑 ii将兄弟节点变红 iii对兄弟结点左旋 iiii将兄弟结点调整为父节点的左子树 (iiiii现在情况3就会变成情况4接着做情况4的步骤 4. 当前结点的兄弟结点是黑色的而且兄弟结点的左孩子是红色的右孩子是黑色的 i将兄弟节点换成父节点的颜色 ii把父节点和兄弟节点的左孩子变黑 iii对父节点做右旋 iiii将轴心结点调整为根结点 void rbtree_delete_fixup(rbtree *T, rbtree_node *x) {//如果x是红色变成黑色如果x是黑色需要调整while ((x ! T-root) (x-color BLACK)) {//当前结点是父结点的左子树if (x x-parent-left) {//兄弟节点rbtree_node *w x-parent-right;// 情况1兄弟节点为红色if (w-color RED) {// 兄弟节点变成黑色w-color BLACK;// 父节点变成红色x-parent-color RED;// 父节点做左旋rbtree_left_rotate(T, x-parent);//将兄弟结点调整为父节点的右子树w x-parent-right;}// 情况2兄弟节点是黑色的且兄弟的左孩子和右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {// 兄弟节点变成红色w-color RED;// 轴心结点变为父节点x x-parent;} else {// 情况3x的兄弟节点是黑色的兄弟的左孩子是红色右孩子是黑色if (w-right-color BLACK) {// 将左孩子涂黑w-left-color BLACK;// 将兄弟节点变红w-color RED;// 对兄弟节点右旋rbtree_right_rotate(T, w);// 重新设置x的兄弟节点w x-parent-right;}// 情况4x的兄弟节点是黑色x的兄弟节点的右孩子是红色的// 将兄弟节点换成父节点的颜色w-color x-parent-color;// 把父节点和兄弟节点的右孩子涂黑x-parent-color BLACK;w-right-color BLACK;// 对父节点做左旋rbtree_left_rotate(T, x-parent);// 设置x指针指向根节点x T-root;}} else {//当前结点是父结点的右子树//兄弟节点rbtree_node *w x-parent-left;//情况1兄弟结点为红色if (w-color RED) {// 兄弟节点变成黑色w-color BLACK;// 父节点变成红色x-parent-color RED;// 父节点做右旋rbtree_right_rotate(T, x-parent);//将兄弟结点调整为父节点的左子树w x-parent-left;}// 情况2兄弟节点是黑色的且兄弟的左孩子和右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {// 兄弟节点变成红色w-color RED;// 轴心结点变为父节点x x-parent;} else {// 情况3x的兄弟结点是黑色的兄弟的左孩子是黑色右孩子是红色if (w-left-color BLACK) {//将右孩子变黑w-right-color BLACK;//将兄弟节点变红w-color RED;//对兄弟结点左旋rbtree_left_rotate(T, w);//将兄弟结点调整为父节点的左子树w x-parent-left;}// 情况4x的兄弟结点是黑色的兄弟的左孩子是红色右孩子是黑色// 将兄弟节点换成父节点的颜色w-color x-parent-color;// 把父节点和兄弟节点的左孩子变黑x-parent-color BLACK;w-left-color BLACK;// 对父节点做右旋rbtree_right_rotate(T, x-parent);//将轴心结点调整为根结点x T-root;}}}// 继承节点变为黑色为了弥补失去的黑高x-color BLACK;
} 三、完整代码及测试用例
#include stdio.h
#include stdlib.h
#include string.h#define RED 0
#define BLACK 1typedef int KEY_TYPE;typedef struct _rbtree_node {unsigned char color;//颜色struct _rbtree_node* left;//左子树struct _rbtree_node* right;//右子树struct _rbtree_node* parent;//父结点KEY_TYPE key;void* value;} rbtree_node;//红黑树结点typedef struct _rbtree {rbtree_node* root;//根结点rbtree_node* nil;//通用叶子结点null
} rbtree;//红黑树//函数声明
void rbtree_delete_fixup(rbtree* T, rbtree_node* x);
void rbtree_insert_fixup(rbtree* T, rbtree_node* z);//左旋leftRotate(T,x)---中右-左中
//需要改变6根指针
//降低X结点的高度提高X结点右结点即Y的高度。
void rbtree_left_rotate(rbtree* T, rbtree_node* x) {rbtree_node* y x-right;//1x-right y-left;//x的右子树指向y的左子树if (y-left ! T-nil) {y-left-parent x;//y的左子树的父节点指向x}//2y-parent x-parent;//y的父结点指向x的父结点if (x-parent T-nil) {//如果x是根结点T-root y;}else if (x x-parent-left) {x-parent-left y;//本来指向x结点的父指针改成指向y}else {x-parent-right y;}//3y-left x;//y的左子树指向x结点x-parent y;//x的父节点指向y
}//右旋
//copy左旋的代码
//left改成rightright改成left
//x改成yy改成x
void rbtree_right_rotate(rbtree* T, rbtree_node* y) {rbtree_node* x y-left;//1y-left x-right;if (x-right ! T-nil) {x-right-parent y;}//2x-parent y-parent;if (y-parent T-nil) {T-root x;}else if (y y-parent-right) {y-parent-right x;}else {y-parent-left x;}//3x-right y;y-parent x;
}//因为传入的key可能是字符可能是整形所以要提取出来
//这里可以看出其实可以封装成一个模板
int key_compare(KEY_TYPE a, KEY_TYPE b) {//这里假设是intif (a b) {return 1;}else if (a b) {return -1;}else {return 0;}
}
//插入结点
void rbtree_insert(rbtree* T, rbtree_node* z) {//找位置rbtree_node* x T-root;rbtree_node* y T-nil;//y是x的父节点while (x ! T-nil) {//二分找位置y x;if (key_compare(z-key, x-key) 0) {x x-left;}else if (key_compare(z-key, x-key) 0) {x x-right;}else {//如果key相等看自己的业务情景//重复插入可以不修改直接退出可以修改valreturn;}}//插入z-parent y;if (y T-nil) {T-root z;}else if (key_compare(z-key, y-key) 0) {y-left z;}else {y-right z;}z-left T-nil;z-right T-nil;z-color RED;//维护红黑树rbtree_insert_fixup(T, z);
}//修复第4条性质
//插入节点之后如果破坏了红黑树的性质需要修复
void rbtree_insert_fixup(rbtree* T, rbtree_node* z) {//父结点是红色的需要调整while (z-parent-color RED) {if (z-parent z-parent-parent-left) {//如果父结点是爷结点是左子树rbtree_node* y z-parent-parent-right;//叔结点if (y-color RED) {//叔结点是红色的//先变色叔,父变黑z-parent-color BLACK;y-color BLACK;//爷结点变红z-parent-parent-color RED;//下面的调整完了调整上面z z-parent-parent;}else {//叔父结点是黑色if (z z-parent-right) {//新节点是在右边z z-parent;rbtree_left_rotate(T, z);}z-parent-color BLACK;z-parent-parent-color RED;rbtree_right_rotate(T, z-parent-parent);}}else {// 如果父结点是爷结点是右子树rbtree_node* y z-parent-parent-left;//叔父结点if (y-color RED) {//叔父结点是红色的//先变色叔,父变黑z-parent-color BLACK;y-color BLACK;//爷结点变红z-parent-parent-color RED;//下面的调整完了调整上面z z-parent-parent;}else {//叔父结点是黑色if (z z-parent-left) {//新节点是在左边z z-parent;rbtree_right_rotate(T, z);}z-parent-color BLACK;z-parent-parent-color RED;rbtree_left_rotate(T, z-parent-parent);}}}//最后别忘了根节点始终是黑色T-root-color BLACK;
}rbtree_node* rbtree_mini(rbtree* T, rbtree_node* x) {while (x-left ! T-nil) {x x-left;}return x;
}//找后继结点
rbtree_node* rbtree_successor(rbtree* T, rbtree_node* x) {rbtree_node* y x-parent;//右子树不为空则找右子树中最左的元素if (x-right ! T-nil) {return rbtree_mini(T, x-right);}//找到结点第一个父结点while ((y ! T-nil) (x y-right)) {x y;y y-parent;}return y;
}//覆盖结点z
//删除结点y
//轴心结点x
rbtree_node* rbtree_delete(rbtree* T, rbtree_node* z) {rbtree_node* y T-nil;rbtree_node* x T-nil;if ((z-left T-nil) || (z-right T-nil)) {y z;//如果没有孩子或只有一个}else {//如果有两个子树则找后继y rbtree_successor(T, z);}//一般x是y的右子树找到轴心结点if (y-left ! T-nil) {x y-left;}else if (y-right ! T-nil) {x y-right;}//将该结点的唯一子树挂到父结点上然后删除该结点x-parent y-parent;if (y-parent T-nil) {//根结点T-root x;}else if (y y-parent-left) {y-parent-left x;}else {y-parent-right x;}//进行覆盖操作if (y ! z) {z-key y-key;z-value y-value;}//黑色才需要调整if (y-color BLACK) {rbtree_delete_fixup(T, x);}return y;
}void rbtree_delete_fixup(rbtree* T, rbtree_node* x) {//如果x是红色变成黑色如果x是黑色需要调整while ((x ! T-root) (x-color BLACK)) {//当前结点是父结点的左子树if (x x-parent-left) {//兄弟节点rbtree_node* w x-parent-right;// 情况1兄弟节点为红色if (w-color RED) {// 兄弟节点变成黑色w-color BLACK;// 父节点变成红色x-parent-color RED;// 父节点做左旋rbtree_left_rotate(T, x-parent);//将兄弟结点调整为父节点的右子树w x-parent-right;}// 情况2兄弟节点是黑色的且兄弟的左孩子和右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {// 兄弟节点变成红色w-color RED;// 轴心结点变为父节点x x-parent;}else {// 情况3x的兄弟节点是黑色的兄弟的左孩子是红色右孩子是黑色if (w-right-color BLACK) {// 将左孩子涂黑w-left-color BLACK;// 将兄弟节点变红w-color RED;// 对兄弟节点右旋rbtree_right_rotate(T, w);// 重新设置x的兄弟节点w x-parent-right;}// 情况4x的兄弟节点是黑色x的兄弟节点的右孩子是红色的// 将兄弟节点换成父节点的颜色w-color x-parent-color;// 把父节点和兄弟节点的右孩子涂黑x-parent-color BLACK;w-right-color BLACK;// 对父节点做左旋rbtree_left_rotate(T, x-parent);// 设置x指针指向根节点x T-root;}}else {//当前结点是父结点的右子树//兄弟节点rbtree_node* w x-parent-left;//情况1兄弟结点为红色if (w-color RED) {// 兄弟节点变成黑色w-color BLACK;// 父节点变成红色x-parent-color RED;// 父节点做右旋rbtree_right_rotate(T, x-parent);//将兄弟结点调整为父节点的左子树w x-parent-left;}// 情况2兄弟节点是黑色的且兄弟的左孩子和右孩子都是黑色if ((w-left-color BLACK) (w-right-color BLACK)) {// 兄弟节点变成红色w-color RED;// 轴心结点变为父节点x x-parent;}else {// 情况3x的兄弟结点是黑色的兄弟的左孩子是黑色右孩子是红色if (w-left-color BLACK) {//将右孩子变黑w-right-color BLACK;//将兄弟节点变红w-color RED;//对兄弟结点左旋rbtree_left_rotate(T, w);//将兄弟结点调整为父节点的左子树w x-parent-left;}// 情况4x的兄弟结点是黑色的兄弟的左孩子是红色右孩子是黑色// 将兄弟节点换成父节点的颜色w-color x-parent-color;// 把父节点和兄弟节点的左孩子变黑x-parent-color BLACK;w-left-color BLACK;// 对父节点做右旋rbtree_right_rotate(T, x-parent);//将轴心结点调整为根结点x T-root;}}}// 继承节点变为黑色为了弥补失去的黑高x-color BLACK;
}rbtree_node* rbtree_search(rbtree* T, KEY_TYPE key) {rbtree_node* node T-root;while (node ! T-nil) {if (key node-key) {node node-left;}else if (key node-key) {node node-right;}else {return node;}}return T-nil;
}void rbtree_traversal(rbtree* T, rbtree_node* node) {if (node ! T-nil) {rbtree_traversal(T, node-left);printf(key:%d, color:%d\n, node-key, node-color);rbtree_traversal(T, node-right);}
}int main() {int keyArray[20] { 24, 25, 13, 35, 23, 26, 67, 47, 38, 98, 20, 19, 17, 49, 12, 21, 9, 18, 14, 15 };rbtree* T (rbtree*)malloc(sizeof(rbtree));if (T NULL) {printf(malloc failed\n);return -1;}T-nil (rbtree_node*)malloc(sizeof(rbtree_node));T-nil-color BLACK;T-root T-nil;rbtree_node* node T-nil;int i 0;for (i 0; i 20; i) {node (rbtree_node*)malloc(sizeof(rbtree_node));node-key keyArray[i];node-value NULL;rbtree_insert(T, node);}rbtree_traversal(T, T-root);printf(****************************************\n);for (i 0; i 20; i) {rbtree_node* node rbtree_search(T, keyArray[i]);rbtree_node* cur rbtree_delete(T, node);free(cur);rbtree_traversal(T, T-root);printf(----------------------------------------\n);}
}
