结点设置

既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义，为了避免过多重复的代码，下面的问题都统一使用该结点类型。

typedef char BTDataType;//结点中存储的元素类型（以char为例）typedef struct BTNode
{BTDataType data;//结点中存储的元素类型struct BTNode* left;//左指针域（指向左孩子）struct BTNode* right;//右指针域（指向右孩子）
}BTNode;

二叉树的遍历

前序、中序以及后序遍历 递归实现

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

// 二叉树前序遍历 
void PreOrder(BTNode* root)
{if (root == nullptr){return;}//根->左子树->右子树printf("%c ", root->data);PreOrder(root->left);PreOrder(root->right);
}// 二叉树中序遍历
void InOrder(BTNode* root)
{if (root == nullptr){return;}//根->左子树->右子树PreOrder(root->left);printf("%c ", root->data);PreOrder(root->right);
}
// 二叉树后序遍历
void PostOrder(BTNode* root)
{if (root == nullptr){return;}//根->左子树->右子树PreOrder(root->left);PreOrder(root->right);printf("%c ", root->data);
}

前序遍历递归图解

前序、中序以及后序遍历 非递归实现

144.
二叉树的前序遍历

思路：

1. 根节点入栈.
2. 栈顶元素入存入vector,根节点出栈.
3. 右孩子入栈
4. 左孩子入栈

因为我们要求:
先访问左孩子,再访问右孩子.
而栈是后进先出的结构,所以:
右孩子先入栈,左孩子后入栈.

步骤示例图:

代码：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*> s;if(root == nullptr)return {};s.push(root);//根节点先入栈while(!s.empty())//当栈为空时,结束{TreeNode* ret = s.top();v.push_back(ret->val);//出栈前,先将栈顶元素存入vectors.pop();//栈顶元素出栈//栈顶元素的右左子树入栈if(ret->right)s.push(ret->right);if(ret->left)s.push(ret->left);}return v;}
};

94.
二叉树的中序遍历

思路:
有了前面的前序遍历的思想,对于中序遍历,需要注意的是存入容器(这里是vector)的时机.

左路节点依次入栈.(与前序对比:此时入栈并没有入容器.)
栈顶元素入容器,栈顶元素出栈,栈顶元素的右子树子问题解决.

代码：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> s1;vector<int> v1;TreeNode*  cur=root;while(cur||!s1.empty()){//沿着左子树一直入节点while(cur){s1.push(cur);cur=cur->left;}TreeNode* top = s1.top();if(top==nullptr)break;v1.push_back(top->val);//栈顶元素出栈s1.pop();//右子树 以子问题的方式解决if(top->right)cur=top->right;}return v1;}
};

145. 二叉树的后序遍历

思路 ：

对于后序遍历,同样注意存入容器的时机,应当是左子树和右子树都访问完毕,才能够访问根节点.

注意点:

(1)访问结点之前,需要先判断右子树是否已经被访问.

如何判断根节点的右子树已经有没有访问?
答案: 上一个存入的结点是自己右子树,则右子树已经被访问.
上一个结点不是自己的右子树,则右子树未被访问.

代码：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> v;TreeNode* prev = nullptr;TreeNode* cur = root;while(cur || !s.empty()){while(cur){s.push(cur);cur = cur->left;}TreeNode* top = s.top();//top的结点右为空 or 上一个访问的结点是他的右孩子//说明不用访问 或者 已经访问过了if(top->right == nullptr || top->right == prev){s.pop();prev = top;v.push_back(top->val);}else{cur = top->right;}}return v;}
};

层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

思路（借助一个队列）：
 1.先把根入队列，然后开始从队头出数据。
 2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
 3.重复进行步骤2，直到队列为空为止。

// 层序遍历
void LevelOrder(BTNode* root)
{std::queue<BTNode*> q;if (root != nullptr)q.push(root);while (q.empty()){BTNode* front = q.front();q.pop();printf("%c ", front->data);//打印出队的元素if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}}
}

结点的个数

求解树的结点总数时，可以将问题拆解成子问题：
 1.若为空，则结点个数为0。
 2.若不为空，则结点个数 = 左子树结点个数 + 右子树结点个数 + 1（自己）。

代码：

// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{return root == nullptr ? 0 : BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

叶子结点的个数

子问题拆解：
 1.若为空，则叶子结点个数为0。
 2.若结点的左指针和右指针均为空，则叶子结点个数为1。
 3.除上述两种情况外，说明该树存在子树，其叶子结点个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数。

代码：

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == nullptr)//空树无叶子结点return 0;if (root->left == nullptr && root->right == nullptr)//是叶子结点return 1;//叶子结点的个数 = 左子树的叶子结点个数 + 右子树的叶子结点个数return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

第k层结点的个数

思路：
 相对于根结点的第k层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。

代码：

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (k < 1 || root == nullptr)//空树或输入k值不合法return 0;if (k == 1)//第一层结点个数return 1;//相对于父结点的第k层的结点个数 = 相对于两个孩子结点的第k-1层的结点个数之和return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

值为x的结点

子问题：
 1.先判断根结点是否是目标结点。
 2.再去左子树中寻找。
 3.最后去右子树中寻找。

代码：

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return nullptr;if (root->data == x)return root;BTNode* rleft = BinaryTreeFind(root->left, x);//在左子树中找if (rleft)return rleft;BTNode* rright = BinaryTreeFind(root->right, x);//在右子树中找if (rright)return rright;return nullptr;//根结点和左右子树中均没有找到
}

树的最大深度

子问题：
 1.若为空，则深度为0。
 2.若不为空，则树的最大深度 = 左右子树中深度较大的值 + 1。

代码：

//树的最大深度
int BinaryTreeMaxDepth(BTNode* root)
{//树的最大深度 = 左右子树中深度较大的值 + 1return root == nullptr ? 0 : (std::max(BinaryTreeMaxDepth(root->left) + 1, BinaryTreeMaxDepth(root->right) + 1));
}

二叉树的销毁

二叉树的销毁，与其他数据结构的销毁类似，都是一边遍历一边销毁。但是二叉树需要注意销毁结点的顺序，遍历时我们应该选用后序遍历，也就是说，销毁顺序应该为：左子树->右子树->根。
 我们必须先将左右子树销毁，最后再销毁根结点，若先销毁根结点，那么其左右子树就无法找到，也就无法销毁了。

代码：

//二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{if (root == NULL)return;BinaryTreeDestroy(root->left);//销毁左子树BinaryTreeDestroy(root->right);//销毁右子树free(root);//释放根结点
}