钟祥网站建设,aspcms网站打开慢,网站建设兼职挣多少钱,邢台吧 百度贴吧文章目录 一.什么是树二.什么是二叉树三.二叉树的访问次序四.特殊的二叉树五.求结点个数六.平衡二叉树总结 一.什么是树 树是由一个集合以及在该集合上定义的一种关系构成的。 集合中的元素称为树的节点#xff0c;所定义的关系称为父子关系。 父子关系在树的节点之间建立了一… 文章目录 一.什么是树二.什么是二叉树三.二叉树的访问次序四.特殊的二叉树五.求结点个数六.平衡二叉树总结 一.什么是树 树是由一个集合以及在该集合上定义的一种关系构成的。 集合中的元素称为树的节点所定义的关系称为父子关系。 父子关系在树的节点之间建立了一个层次结构。 在这种层次结构中有一个节点具有特殊的地位这个节点称为该树的根节点或称为树根。 结点 结点是数据结构中的基础是构成复杂数据结构的基本组成单位。 结点的度 结点拥有的子树数目称为结点的度。 二.什么是二叉树 二叉树是n(n0)个结点的有限集合该集合或者为空集称为空二叉树或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。 特点 1.每一个节点最多有两棵子数及二叉树不存在度大于二的节点 2.二叉树的子树有左右之分其子树的次序不能够颠倒 3.任何一个二叉树都有三部分根节点左子树右子树 结构
typedef int BTDataType;
typedef struct Binary TreeNode
{struct Binary TreeNode* left;//左孩子struct Binary TreeNode* right;//右孩子BTDataType data;//数据
}BTNode;
三.二叉树的访问次序
3.1前序遍历 (根结点 左子树 右子树)
主要是利用了函数递归的方法去遍历,先根节点左子树右子树不断地去调用自己
void PreOrder(BTNode* root)
{if (root NULL)return;printf(%d, root-data);//根PreOrder(root-left);//左子树PreOrder(root-right);//右子树}
3.2中序遍历和后序遍历
void MidOrder(BTNode* root)
{if (root NULL)return;MidOrder(root-left);//左子树printf(%d, root-data);//根MidOrder(root-right);//右子树
}void afterOrder(BTNode* root)
{if (root NULL)return;afterOrder(root-left);//左子树afterOrder(root-right);//右子树printf(%d, root-data);//根
}
3.3层序遍历
前中后序遍历其实也叫深度优化遍历序遍历叫广度优化遍历
我们利用队列来实现层序遍历 核心思路上一层带下一层的 先创造一个队列如果跟节点不为空的话把根节点放入这个队列中循环的判断条件被列中没有元素就停下来有元素就继续去队列投元素放入树的头然后再删去队列这个元素然后把删去元素所对应的左子树和右子树放入一层一层的遍历 void LeveOrder(BTNode* root)
{//创建队列Queue q;Queue Init(q);//如果根节点不为空在队列里放入if (root ! NULL){QueuePush(q, root);}while (!QueueEmpty(q)){//删去元素所对应的左子树和右子树放入一层一层的遍历BTNode* front QueueFront(q);QueuePop(q);printf(%c, front-data);if (front-left ! NULL){QueuePush(q, front-left);}if (front-right ! NULL){QueuePush(q, front-right);}}printf(\n);QueueDestory(q);
}
四.特殊的二叉树
4.1满二叉树 假设一个满二叉树的高为h则它的总结点个数为N,则高为2^02^1....2^(h-1)Nhlog2N1) 4.2完全二叉树 特征1.前n-1层是满的。2.最后一层不满但最后一层从左往右都是连续的 特别公式对于任何一颗二叉树如果度为零的叶子节点个数为n0度为二的分支节点个数为n2则n0n21。 例存在一个2n个结点的完全二叉树则它的叶子结点大小的个数为__ 完全二叉树度为1的结点个数要么是1个要么没有。设度为0的结点为x0度为1的为x1度为二的为x2,所以说套入两个公式x0x1x22nx0x21.可以算出2x0x1-12n又因为完全二叉树所以x1为0或者1带入可得n或者2n1/2 五.求结点个数 其实二叉树还有一个平衡结构叫做平衡二叉树需要非常灵活的掌握函数递归和分治的思想所以我们先来利用递归和分治思想来求一下结点 5.1求叶子结点的个数
利用递归和分治的思想
int TreeLeafsize(BTNode* root)
{if (root NULL)return 0;//如果左子树和右子树都为空说明找到了一个叶子结点返回1if (root-left NULL root-right NULL)return 1;//利用函数递归的思路先左子树在右return TreeLeafsize(root-left) TreeLeafsize(root-right);
}5.2求总结点个数
void Treesize(BTNode* root, int* psize)
{if (root NULL){return;}//是结点就加加else{(*psize);}//也是递归分治先左子树在右子树Treesize(root-left,psize);Treesize(root-right,psize);
}
六.平衡二叉树 定义平衡二叉树也叫AVL树它或者是一颗空树或者具有以下性质的二叉排序树它的左子树和左子树的高度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树。 6.1二叉树的深度 分治思路:如果为空高度直接为零非空就分解子问题先求左右指数的深度我的深度等于左右质数深度大的大小加1。 int maxDepth(BTNode* root)
{if (root NULL)return 0;int leftDepth maxDepth(root-left);int rightDepth maxDepth(root-right);//左边的深度如果大于右边的话就加1反之右边加1return leftDepth rightDepth ? leftDepth 1 : rightDepth 1;
}
6.2平衡树的判断 bool isBalaned(BTNode* root)
{//第一种情况如果为空的话就是的if (root NULL)return true;//利用深度函数来求出左右子树的深度int leftDepth maxDepth(root-left);int rightDepth maxDepth(root-right);//利用递归判断高度差的绝对值不超过1左右都要是平衡二叉递归return abs(leftDepth - rightDepth) 2 isBalaned(root-left) isBalaned(root-right);
} 总结
这只是初次学习二叉树它的内容可不只有这些还要深度的还需要不断的学习积累才可实现
