5.数据结构-c/c++二叉树详解(上篇)（遍历方法，完全二叉树）

目录

一. 二叉树的基本介绍

1.2 满二叉树

1.3 完全二叉树

1.4 搜索二叉树

1.5 平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

2.2 创建一个新的节点

2.3 构建一颗树

2.5 销毁一棵树

三.二叉树的前序，中序，后序，层序遍历方法

3.1 前序遍历

3.2 中序遍历

3.3 后序遍历

3.4 层序遍历

四.下篇内容（算法面试题）

---

一. 二叉树的基本介绍

        二叉树是一种每一个节点最多只有两个子树的树结构。

树的5种基本结构如下图

几种特殊的二叉树结构

1.2 满二叉树

        二叉树的每一层是满的，节点数量为2*h-1        h为树的高度

下图两种树都为满二叉树

1.3 完全二叉树

        在一颗二叉树中，只有最后两层节点的度小于2，且所有的叶子节点都依次集中在左侧

1.4 搜索二叉树

在一颗二叉树中，该树可以为空。如果不为空，则要满足下列条件

1.树中的每一个子树的左子树都小于其根节点

2.树中每一颗子树的右子树都大于其根节点

3.所有子树都是二叉搜索树

1.5 平衡二叉搜索树

       1. 二叉搜索树的左右子树高度差不超过1

       2.左右子树都是二叉搜索树

       3.节点中包含平衡因子

满足以上三点的二叉搜索树就是平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

//定义节点
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

2.2 创建一个新的节点

//创建一个新节点
BTNode* CreatNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));assert(node);//更新节点的值，并将左右指针置空node->data = x;node->left = nullptr;node->right = nullptr;return node;
}

2.3 构建一颗树

	//根据需求依次构建节点并连接即可BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');BTNode* F = CreatNode('F');BTNode* G = CreatNode('G');A->left = B;A->right = C;B->left = D;B->right = E;C->left = F;C->right= G;

2.5 销毁一棵树

利用前序遍历，依次释放每一个节点即可

//销毁一棵树//使用后续销毁
void TreeDestory(BTNode* root)
{if (root == NULL)return;TreeDestory(root->left);TreeDestory(root->right);free(root);
} 

三.二叉树的前序，中序，后序，层序遍历方法

3.1 前序遍历

利用递归思想，要访问一棵树的所有节点，访问根节点后，访问子树的节点

//前序遍历
void PrevOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}cout << root->data << " ";	//访问根节点PrevOrder(root->left);		//访问左子树PrevOrder(root->right);		//访问右子树
}

3.2 中序遍历

//中序遍历
void InOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//中序遍历前访问左子树，再访问根节点，最后访问右子树InOrder(root->left);		//访问左子树cout << (char)root->data << " ";	//访问根节点InOrder(root->right);		//访问右子树
}

3.3 后序遍历

//后序遍历
void NextOrder(BTNode* root)
{if (root == nullptr){cout << "NULL ";return;}//后序遍历先访问左子树，在访问右子树。最后访问根节点NextOrder(root->left);		//访问左子树NextOrder(root->right);		//访问右子树cout << (char)root->data << " ";	//访问根节点
}

3.4 层序遍历

利用队列的先进先出特点。

将一层的节点都放入队列中，然后依次访问队首的数据并将其左右子节点放入队列中

如下图

代码 

//层序遍历(广度优先遍历)，该遍历需要我们使用到队列先进先出的特点
void TreeLeverOrder(BTNode* root)
{if (root == nullptr){return;}queue<BTNode*> q;q.push(root);while (!q.empty()){BTNode* front = q.front();if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}cout << (char)q.front()->data << " ";q.pop();}cout << endl;
}

四.下篇内容（算法面试题）

求二叉树 第k层的节点

查找一个节点是否在二叉树中

求二叉树节点的个数

求二叉树叶子节点的个数

求树的深度

判断一棵树是否为完全二叉树