行业数据分析网站_国内免费b2b平台_网站推广的意义和方法_优化关键词哪家好

二叉树分类

满二叉树

这棵树深度为k，有2^k-1个节点。

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。

注意：完全二叉树一定是从左到右连续的，不可以中断！！！

二叉树存储方式 

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

二叉树的遍历 

1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
2. 广度优先遍历：一层一层的去遍历

 

• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
  • 层次遍历（迭代法）

深度优先遍历的三种方式区分就是看“中”的位置，前序就是中在前，中序就是中在中，后序就是中在后。

（1）之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

（2）而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

二叉树定义代码

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

这个结构体定义跟链表很像，相比链表多了一个指向而已~