二叉树操作源代码大全.docx
- 文档编号:4287882
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:8
- 大小:16.57KB
二叉树操作源代码大全.docx
《二叉树操作源代码大全.docx》由会员分享,可在线阅读,更多相关《二叉树操作源代码大全.docx(8页珍藏版)》请在冰点文库上搜索。
二叉树操作源代码大全
二叉树操作源代码大全
二叉链表的结构定义
#include
#include
typedefstructtree
{
void*data_p; //兼容所有类型
structtree*left;
structtree*right;
}tree_t;
初始化一个节点,初值置为data
inttree_make_node(tree_t**root,void*data)
{
*root=(tree_t*)malloc(sizeof(tree_t));
if(*root==NULL)
{
printf("mallocerror\n");
return-1;
}
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data_p=data;
return0;
}
将new_node插入树中作为where_to的左孩子,返回新插入结点的指针
tree_t*tree_insert_left(tree_t*new_node,tree_t*where_to)
{
if(new_node!
=NULL)
{
tree_t*tmp;
tmp=where_to->left;
where_to->left=new_node;
new_node->left=tmp;
}
returnnew_node;
}
将new_node插入树中作为where_to的右孩子,返回新插入结点的指针
tree_t*tree_insert_right(tree_t*new_node,tree_t*where_to)
{
if(new_node!
=NULL)
{
tree_t*tmp;
tmp=where_to->right;
where_to->right=new_node;
new_node->right=tmp;
}
returnnew_node;
}
删除entry结点的左,右子树
voidtree_del_left(tree_t*entry)
{
entry->left=NULL;
free(entry);
}
voidtree_del_right(tree_t*entry)
{
entry->right=NULL;
free(entry);
}
前序遍历二叉树
voidtree_pre_order(tree_t*root)
{
if(root!
=NULL)
{
VISIT(root);
tree_pre_order(root->left);
tree_pre_order(root->right);
}
}
/*
非递归思路:
先遍历左子树,遍历过程中
那个访问遍历结点,并将其入栈,返回时
退出当前栈顶元素遍历其其右子树
*/
voidtree_pre_order_norec(tree_t*root)
{
tree_t*stack[MAX_ELE];
inttop=0;
while(root!
=NULL||top!
=0)
{
if(root!
=NULL)
{
VISIT(root);
stack[top++]=root;//入栈
root=root->left;
}
else
{
root=stack[--top];//出栈
root=root->right;
}
}
}
中序遍历二叉树
voidtree_in_order(tree_t*root)
{
if(root!
=NULL)
{
tree_in_order(root->left);
VISIT(root);
tree_in_order(root->right);
}
}
/*
非递归思路:
先遍历左子树,并将遍历结点入栈,返回时
退出当前栈顶元素并访问,再遍历其其右子树
*/
voidtree_in_order_norec(tree_t*root)
{
tree_t*stack[MAX_ELE];
inttop=0;
while(root!
=NULL||top!
=0)
{
if(root!
=NULL)
{
stack[top++]=root;
root=root->left;
}
else
{
root=stack[--top];
VISIT(root);
root=root->right;
}
}
}
后序遍历二叉树
voidtree_pos_order(tree_t*root)
{
if(root!
=NULL)
{
tree_pos_order(root->left);
tree_pos_order(root->right);
VISIT(root);
}
}
/*
思路:
先遍历左子树,并将遍历结点入栈,返回时
去栈顶元素,如果该元素的右子树已经被访问(flag为1),
访问该结点,否则标记flag为1
*/
voidtree_pos_order_norec(tree_t*root)
{
typedefstruct
{
tree_t*node;
intflag;//该结点的右子树是否被访问
}pos_order;
pos_orderstack[MAX_ELE];
inttop=0;
while(root!
=NULL||0)
{
if(root!
=NULL)
{
stack[top].node=root;
stack[top].flag=0;
top++;
root=root->left;
}
else
{
pos_ordertmp=stack[top-1];
if(tmp.flag==0)//没有访问其右子树,访问之
{
stack[top-1].flag=1;
root=tmp.node->right;
}
else//如果已经出栈访问了其右子树,访问该结点
{
VISIT(tmp.node);
top--;
}
}
}
}
层序遍历二叉树
voidtree_layer_order(tree_t*root)
{
tree_t*queue[MAX_ELE];
intfront=0;
intrear=0;
if(root==NULL)return;
queue[rear++]=root;
while(front!
=rear)
{
root=queue[front++];
VISIT(root);
if(root->left!
=NULL)
queue[rear++]=root->left;
if(root->right!
=NULL)
queue[rear++]=root->right;
}
}
打印二叉树,逆时针旋转90读,遍历顺序为右根左,参数n为层数
voidtree_print(tree_t*root,intn)
{
if(root!
=NULL)
{
tree_print(root->right,n+1);
for(inti=-1;i { printf("--"); } VISIT(root); printf("\n"); tree_print(root->left,n+1); } } 释放以root为根的二叉树 voidtree_free(tree_t*root) { if(root! =NULL) { tree_free(root->left); tree_free(root->right); free(root); } } 测试实例: 建立二叉树,并以各种方式遍历 intmake_tree(tree_t**root) { char*node="ABCDEFGH"; tree_make_node(root,(void*)(&node[0]));//根结点A tree_t*tmp; tree_t*p; tree_make_node(&tmp,(void*)(&node[1]));//B作为A的左子树 p=tree_insert_left(tmp,*root); tree_make_node(&tmp,(void*)(&node[3]));//D作为B的左子树 p=tree_insert_left(tmp,p); tree_make_node(&tmp,(void*)(&node[5]));//F作为D的右子树 p=tree_insert_right(tmp,p); tree_make_node(&tmp,(void*)(&node[7]));//H作为F的左子树 p=tree_insert_left(tmp,p); tree_make_node(&tmp,(void*)(&node[2]));//C作为A的右子树 p=tree_insert_right(tmp,*root); tree_make_node(&tmp,(void*)(&node[4]));//E作为C的右子树 p=tree_insert_right(tmp,p); tree_make_node(&tmp,(void*)(&node[6]));//G作为E的左子树 p=tree_insert_left(tmp,p); return0; } intmain() { tree_t*root; make_tree(&root); tree_print(root,0); printf("\n\n"); printf("前序遍历序列\n"); tree_pre_order(root); printf("\n"); tree_pre_order_norec(root); printf("\n\n"); printf("中序遍历序列\n"); tree_in_order_norec(root); printf("\n"); tree_in_order(root); printf("\n\n"); printf("后序遍历序列\n"); tree_pos_order(root); printf("\n"); tree_pos_order_norec(root); printf("\n\n"); printf("层序遍历序列\n"); tree_layer_order(root); printf("\n\n"); return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 操作 源代码 大全
![提示](https://static.bingdoc.com/images/bang_tan.gif)