做门的网站建设,做一静态网站 多少钱,郑州seo野狼,深圳招标信息网01 概念定义#xff1a;二叉树既然叫二叉树#xff0c;顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可以为 0#xff0c;但是度最大为 2 。 一颗二叉树是节点的一个有限集合#xff0c;该集合#xff1a;① 由一个根节点加上两棵被称为左子树和右子树的二叉树组…01 概念 定义二叉树既然叫二叉树顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可以为 0但是度最大为 2 。 一颗二叉树是节点的一个有限集合该集合 ① 由一个根节点加上两棵被称为左子树和右子树的二叉树组成 ② 或者为空观察上图我们可以得出如下结论 ① 二叉树不存在度大于 2 的节点换言之二叉树最多也只能有两个孩子。 ② 二叉树的子树有左右之分分别为左孩子和右孩子。次序不可颠倒因此二叉树是有序树。注意对于任意的二叉树都是由以下几种情况复合而成的02 满二叉树定义一个二叉树如果每一层的结点数都达到了最大值均为2则这个二叉树就可以被称作为 满二叉树 。换言之如果一个二叉树的层数为 h且总结点数为 2的 h 次方 - 1那么它就是一个满二叉树。计算公式 ① 已知层数求总数 ② 已知总数求层数 03 完全二叉树定义对于深度为 h 的有 n 个结点的二叉树当且仅当其每一个结点都与深度为 h 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。前 h - 1 层是满的最后一层不满但最后一层从左到右是连续的。完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。所以满二叉树是一种特殊的完全二叉树每一层节点均为2。常识① 完全二叉树中度为 1 的最多只有 1 个。② 高度为 的完全二叉树节点范围是 04 二叉树的性质四点规则① 若规定根节点的层数为 1 则一颗非空二叉树的第 i 层上最多有 2 的 i - 1 次方个节点。② 若规定根节点的层数为 1 则深度为 h 的二叉树最大节点数是 2 的 h 次方 - 1。③ 对任何一棵二叉树如果度为 0 其叶子结点个数为 n0度为 2 的分支节点个数为 n2则有n0 n2 1。换言之度为 0 的永远比度为 2 的多一个叶子结点。
假设二叉树有 n 个结点从总结点数角度考虑n n0 n1 n2从边的角度考虑n 个结点的任意二叉树总共有 n - 1 条边。因为度为 0 的结点没有孩子故度为 0 的结点不产生边; 度为 1 的结点只有一个孩子故每个度为 1 的结点产生一条边; 度为 2 的结点有 2 个孩子故每个度为 2 的结点产生两条边所以总边数为 n12*n2故从边的角度考虑n - 1 n1 2*n2 n0 n1 n2 n1 2*n2 - 1即n0 n2 1
④ 若规定根节点的层数为 1 具有 n 个节点的满二叉树的深度 h logn 1。对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 1. 若 i 0i 位置节点的双亲序号(i - 1) / 2i 0i 为根节点编号无双亲节点。 2. 若2i 1 n左孩子序号2i 12i 1 n否则无左孩子。 3. 若2i 2 n右孩子序号2i 22i 2 n否则无右孩子。05 二叉树的存储1 数组存储一般情况下使用数组来存储只适合完全二叉树。如果是非完全二叉树会造成空间上的浪费。2 链式存储
typedef struct BinaryTreeNode
{struct BinTreeNode* left; // 左孩子struct BinTreeNode* right; // 右孩子DataType data; // 当前节点值域
}BTree;
06 二叉树的遍历二叉树的遍历一般有四种方法前序遍历中序遍历后序遍历层序遍历。1 前序遍历先遍历根节点再依次遍历左子树右子树。而遍历左子树又要先遍历根节点再依次遍历左子树右子树…直至遍历到空树。
// 递归实现
void PreOrder(BTree*root)
{if (root NULL)return;printf(%d , root-data);//根节点PreOrder(root-left);//左子树PreOrder(root-right);//右子树
}
2 中序遍历先遍历左子树再依次遍历根节点右子树。而遍历左子树又要先遍历左子树再依次遍历根节点右子树…直至遍历到空树。
// 递归实现
void Inorder(BTree*root)
{if (root NULL)return;PreOrder(root-left);//左子树printf(%d , root-data);//根节点PreOrder(root-right);//右子树
}
3 后序遍历先遍历左子树再依次遍历右子树根节点。而遍历左子树又要先遍历左子树再依次遍历右子树根节点…直至遍历到空树。
// 递归实现
void Postorder(BTree*root)
{if (root NULL)return;PreOrder(root-left);//左子树PreOrder(root-right);//右子树printf(%d , root-data);//根节点
}
4 层序遍历层序遍历顾名思义就是一层一层地遍历这时就需要借助一个数据结构队列来辅助实现。
void leverOrder(BTree* root, Queue* pq)
{if (root NULL)return;QueuePush(pq, root);//插入第一个节点while (!QueueEmpty(pq))//队列不为空{BTree* p QueueFront(pq);printf(%d , p-val);QueuePop(pq);if (p-left ! NULL)//带入左孩子{QueuePush(pq, p-left);}if (p-right ! NULL)//带入右孩子{QueuePush(pq, p-right);}}
}
