《数据结构与算法》——二叉树
1.视频一共介绍了三种储存方式，父母，孩子，以及父母和孩子。利用父母储存法，在每一个节点都保存了父母的地址，所以根据儿子节点我们可以快速地找到它的父母；同理，孩子储存法和父母孩子储存法则能快速地找到该节点的孩子，或者孩子和父母。2.满二叉树：节点个数n和深度k满足n=2^k-1,即除了叶子其他节点都有两个子节点。
完全二叉树：根据层编号后，编号与满二叉树一致。
——>满二叉树是一种特殊的完全二叉树
——>完全二叉树的度为0的节点个数n0，度为2的节点个数n2,满足n0=n2+1。
3.完全二叉树根据层编号后，满足
——>是i父母节点，若i*2>n，则该节点没有左节点；若i*2+1>n，则该节点没有子节点
4.二叉树的遍历
1）前序遍历:若二叉树为空，则返回；否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树
2）后序遍历：从左到右先子叶后节点的方式遍历访问左右子树，最后访问根节点。
3）中序遍历：从根节点开始，先中序遍历左子树，然后访问根节点，最后再中序遍历右子树。
4）层序遍历：从根节点开始，从上往下，从左往右逐层遍历
5.二叉树的建立和遍历
1）建立:定义一个有着两个指针的结构体，利用递归的方法，将数据不断地从上到下，从左到右地储存在二叉树中完成建立
2）遍历：根据根节点，我们可以利用四种遍历方式，用递归的方式实现遍历#include<cstdlib>
#include<cstdio>
#include<iostream>
using namespace std;
class bitree
{
public:
char data;
bitree *l, *r;
};
void Create(bitree *&p)
{
char c;
scanf_s("%c", &c);
if (' ' == c)
{
p = NULL;
return;
}
else
{
p = new bitree;
p->data = c;
Create(p->r);
Create(p->l);
}
}
void TreeTravel(bitree *p,int level)
{
if (p != NULL)
{
printf("%c is in the level %d\n", p->data, level);
TreeTravel(p->l, level + 1);
TreeTravel(p->r, level + 1);
}
}
int main()
{
bitree *root=NULL;
Create(root);
TreeTravel(root, 1);
system("PAUSE");
}
页:
[1]