中海建筑建设有限公司网站,广州网站制作网站,做网站都需要学什么语言,企业建设银行网站登录不了树
节点#xff08;Node#xff1a;#xff09;
树由一系列的节点组成#xff0c;每个节点可以包含数据和指向其他节点的链接。
节点通常包含一个数据元素和若干指向其他节点的指针 根节点#xff08;Root#xff09;#xff1a;
树的顶部节点称为根节点#xff0c…树
节点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;
}
//二叉树的相关函数例如创建二叉树前序后序中序等都是基于一个函数递归调用的思想原因是树本身就是一个递归的结构由根节点和子节点构成所以写写树相关的代码时离不了相关函数的递归调用。不过值得一提的是函数的递归调用的执行效率并不高。
