树
节点(Node:)
树由一系列的节点组成,每个节点可以包含数据和指向其他节点的链接。
节点通常包含一个数据元素和若干指向其他节点的指针
根节点(Root):
树的顶部节点称为根节点,它是树中没有父节点的唯一节点
子节点(Child):
一个节点的子节点是指由该节点直接指向的节点
叶节点(Leaf):
没有子节点的节点称为叶节点或终端节点
深度(Depth):
节点的深度是从根节点到该节点的路径上的边数。
(广)度:
最大的节点的度
二叉树
每个节点最多有两个子节点的树,通常称为左子节点和右子节点
满二叉树:
在不增加层数的情况下,不能再增加节点了,即为满二叉树
第K层节点个数:
2^(k-1)
K层满二叉树:
总结点数:2^K - 1
完全二叉树:
在满二叉树的基础下,删除节点,只能从右至左,从下到上,删若干个
添加节点,只能从左至右,从上到下,添加若干个。
满二叉树一定是完全二叉树
完全二叉树不一定是满二叉树
二叉树的遍历
前序遍历:先遍历根,再遍历左子树然后再遍历右子树
中序遍历:先遍历左子树,再遍历根,再遍历右子树
后序遍历:先遍历左子树,再遍历右子树,最后遍历根
层序遍历:从上到下,从左至右,逐层遍历
前三种称为深度优先,层序遍历称为广度优先
已知一种排序,不能还原出唯一的二叉树
已知前序+中序 --->唯一的二叉树
已知后序+中序 --->唯一的二叉树
但是知道前序和后序不能还原
二叉树相关练习
1.创建二叉树
TNode_t *create_bin_tree()
{
TDataType data = tree[idx++];
if(data == '#')
{
return NULL;
}
TNode_t *pnode = malloc(sizeof(TNode_t));
if(NULL == pnode)
{
perror("malloc fail");
return NULL;
}
pnode->data = data;
pnode->pl = create_bin_tree();
pnode->pr = create_bin_tree();
return pnode;
}
2.前序遍历
void pre_order(TNode_t *proot)
{
if(NULL == proot)
{
return;
}
printf("%c",proot->data);
pre_order(proot->pl);
pre_order(proot->pr);
}
3.中序遍历
void mid_order(TNode_t *proot)
{
if(NULL == proot)
{
return;
}
mid_order(proot->pl);
printf("%c",proot->data);
mid_order(proot->pr);
}
4.后序遍历
void last_order(TNode_t *proot)
{
if(NULL == proot)
{
return;
}
last_order(proot->pl);
last_order(proot->pr);
printf("%c",proot->data);
}
5.层序遍历
void layer_order(TNode_t *pnode)
{
Queue_t *qnode = create_queue();
if(NULL == qnode)
{
return;
}
push_queue(qnode,(QDataType)pnode);
while(!is_empty_queue(qnode))
{
QDataType outdata;
if(pop_queue(qnode,&outdata) == 0)
{
TNode_t *node = (TNode_t *)outdata;
printf("%c",outdata->data);
if(node->pl)
{
push_queue(qnode,(QDataType)node->pl);
}
if(node->pr)
{
push_queue(qnode,(QDataType)node->pr);
}
}
}
destory_queue(qnode);
}
6.获取二叉树节点数
int get_tree_node(TNode_t *proot)
{
if(NULL == proot)
{
return 0;
}
num++;
get_tree_node(proot->pl);
get_tree_node(proot->pr);
return num;
}
7.获取二叉树层数
int get_tree_fl(TNode_t *proot)
{
if(NULL == proot)
{
return 0;
}
int cntl = get_tree_fl(proot->pl);
int cntr = get_tree_fl(proot->pr);
return cntl > cntr ? cntl + 1 : cntr + 1;
}
//二叉树的相关函数,例如创建二叉树,前序,后序,中序等都是基于一个函数递归调用的思想,原因是,树本身就是一个递归的结构,由根节点和子节点构成,所以写写树相关的代码时离不了相关函数的递归调用。不过值得一提的是,函数的递归调用的执行效率并不高。
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » 树和二叉树
发表评论 取消回复