树
节点数量 = 边数 + 1
深度/高度
最高
节点深度
从根节点(深度为0)开始,
节点高度
从该节点下面的叶子节点(高度为0)开始数
节点的度
子节点的数量
广度优先遍历 层序遍历
使用队列,初始时将根节点加入,头指针指向根节点,之后的每次都加入头指针所指节点的子节点,并且头指针后移
深度优先遍历
使用栈,先将根节点入栈,之后每次入栈栈顶节点没有入过栈的子节点,如果没有子节点,出栈
二叉树
- 每个节点度/子节点最多为2
- 节点数量 = 边数 + 1====>度为0的节点比度为2的节点多一个
左子树
右子树
完全二叉树
除了最后一层都是满的,最后一层缺少右子树
- 编号为i的子节点: 可以通过父节点的编号计算得到子节点的编号
- 左子树编号: 2 * i
- 右子树编号:2 * i + 1
- 可以用连续空间存储
满二叉树
没有度为1的节点,只有度为0和2的节点
完美二叉树
每一层都是满的
二叉树的实现
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
// 节点保存的值
int val;
// 节点地址
TreeNode *Lnext;
TreeNode *Rnext;
// 节点构造函数
TreeNode(int x) : val(x), Lnext(NULL), Rnext(NULL){};
};
struct BinaryTree
{
TreeNode *RootNode;
public:
BinaryTree(int rootV)
{
RootNode = new TreeNode(rootV);
}
void insert(int val)
{
TreeNode *node = RootNode;
while (true)
{
if (node->Lnext==NULL||node->Rnext==NULL) break;
if (rand()%2) node=node->Lnext;
else node=node->Rnext;
}
if (node->Lnext==NULL)
{
node->Lnext = new TreeNode(val);
} else {
node->Rnext = new TreeNode(val);
}
}
};
void bfs(TreeNode *root)
{
TreeNode* arr[100];
int head,tail=0;
arr[tail++]= root;
while (head < tail)
{
TreeNode *node = arr[head];
cout<<node->val<<" ";
if (node->Lnext) arr[tail++] = node->Lnext;
if (node->Rnext) arr[tail++] = node->Rnext;
head++;
}
}
int tot = 0;
void dfs(TreeNode * root)
{
if (root == NULL) return;
int start , end;
tot+=1;
start = tot;
if (root->Lnext) dfs(root->Lnext);
if (root->Rnext) dfs(root->Rnext);
tot+=1;
end = tot;
printf("%d : [%d-%d]\n",root->val,start,end);
return;
}
void clear(TreeNode *node)
{
if (node==NULL) return;
clear(node->Lnext);
clear(node->Rnext);
free(node);
return;
}
int main()
{
srand(time(nullptr));
BinaryTree * bi = new BinaryTree(1);
for (int i = 2;i < 8;i++) {
bi->insert(i);
}
bfs(bi->RootNode);
cout<<endl;
dfs(bi->RootNode);
return 0;
}