「算法」⼆叉树的四种遍历⽅式和⼀些题⽬
⽂章⽬录
⼆叉树的基本概念
⼆叉树（binary tree）是 个结点的有限集合，该集合或者为空集（称为空⼆叉树），或者由⼀个根结点以及两棵互不相交的、分别称为根节点的左⼦树和右⼦树的⼆叉树组成。每个根节点最多只有两个⼦节点的就叫做⼆叉树。⼆叉树的特点
每个结点最多有两棵⼦树，所以⼆叉树中不存在度⼤于 2 的结点。注意不是只有两棵⼦树，⽽是最多有。没有⼦树或者有⼀棵⼦树都是可以的。左⼦树和右⼦树是有顺序的，次序不能任意颠倒。
即使树中某结点只有⼀棵⼦树，也要区分它是左⼦树还是右⼦树。
完全⼆叉树
对于⼀棵具有 n 个节点的⼆叉树按照层序编号，如果编号为 的节点与同样深度的满⼆叉树中编号为 i 的节点在⼆叉树中
位置完全相同，则这棵⼆叉树称为”完全⼆叉树“。如下图：
把完全⼆叉树的节点与同样深度的满⼆叉树各个节点进⾏编号⽐较，所有节点出现的位置相同，则是完全⼆叉树。所以，满⼆叉树⼀定是⼀棵完全⼆叉树，⽽完全⼆叉树不⼀定是满⼆叉树。
完全⼆叉树的深度： ([ ]表⽰向下取整）完全⼆叉树的特点：叶⼦节点只能出现在最下两层。
最下层的叶⼦⼀定集中左部连续位置。倒数第⼆层，若有叶⼦节点，⼀定都在右部连续位置。如果结点度为1，则该结点只有左孩⼦，即不存在右⼦树的情况。
同样节点的⼆叉树，完全⼆叉树的深度最⼩。
⼆叉树的存储结构
1、⼆叉树顺序存储结构
⼆叉树的顺序存储结构就是⽤⼀维数组存储⼆叉树中的结点，井且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系。顺序存储⼀般只⽤于完全⼆叉树。
2、⼆叉链表
⼆叉树每个结点最多有两个孩⼦，所以为官设计⼀个数据域和两个指针域，我们称这样的链表叫做⼆叉链表。
n (n >=0)i (1<=i <=n )h =[log (n +21)]+1
typedef struct BiTNode
{hyper
TElemType data;//结点数据
struct BiTNode *lchild,*rchild;//左右孩⼦结点
} BiTNode,*BiTree;
⼆叉树的遍历
⼆叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问⼆叉树中所有结点，使得每个结点被访问⼀次且仅被访问⼀次。
前序遍历
四级成绩什么时间公布
规则是若⼆叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左⼦树，再前序遍历右⼦树。
递归实现：
void PreOrderTraver(BiTree T)
{
if(T ==NULL)
return;
cout << T->val;
PreOrderTraver(T->lchild);
PreOrderTraver(T->rchile);
}
⾮递归实现：
使⽤栈来实现前序遍历，⾸先将根节点压⼊栈中，然后打印栈顶元素。⼊栈和出栈的顺序是相反的，所以我们先将根节点的右⼦节点压⼊栈中，然后将左⼦节点也压⼊栈中，打印栈顶元素。操作完元素后让栈顶元素出栈，在压⼊该元素节点的右、左⼦节点，以此操作即可得出⼆叉树的前序遍历元素。
void PreOrderTraver(BiTree T)
{
if(T ==NULL)
return;
stack<BiTree*> bi_tree;
bi_tree.push(T->data);// 先将根节点压⼊栈中
while(!pty()){
BiTree* top = p();
cout << top->val;// 对栈顶元素操作
bi_tree.pop();// 栈顶元素出栈
if(top->rchild !=NULL)// 压⼊该元素节点的右⼦节点
bi_tree.push(top->rchild);
if(top->lchild !=NULL)// 压⼊该元素节点的左⼦节点
bi_tree.push(top->lchild);
}
}
中序遍历
若树为空，则空操作返回。否则从根节点开始（并不是先访问根节点），中序遍历根节点的左⼦树，然后访问根节点，最后中序遍历右⼦树。
递归实现：
void InOrderTraver(BiTree T)
{
if(T ==NULL)
return;
InOrderTraver(T->lchild);
cout << T->val;
InOrderTraver(T->rchild);
}
⾮递归实现：
使⽤栈来实现⼆叉树的中序遍历，先将根节点压⼊栈中，然后⼀直遍历左⼦节点并压⼊栈中。完成之后将栈顶元素节点出栈并操作，再将出栈的这个节点的右⼦节点压⼊栈中，重复上述操作。
void InOrderTraver(TreeNode* root)
{
if(root ==nullptr)
return;
stack<TreeNode*> bi_tree;
while(!pty()|| root !=nullptr){
while(root !=nullptr){// 遍历左⼦节点并压⼊栈中
bi_tree.push(root);
root = root->left;
}
root = p();// 栈顶元素出栈
bi_tree.pop();
cout << root->val;// 操作元素
root = root->right;// 将右⼦节点压⼊栈中
}
}
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶⼦后结点的⽅式遍历访问左右⼦树，最后是访问根结点。
递归实现：
void PostOrderTraver(BiTree T)
{
if(T ==NULL)
return;
PostOrderTraver(T->lchild);
PostOrderTraver(T->rchild);
cout << T->val;
}
⾮递归实现：
使⽤两个栈来实现⼆叉树的后序遍历，我们很容易得到⼀种遍历⽅式：“根节点 -> 右⼦节点 -> 左⼦节点”，这种遍历⽅式是后序遍历的反序。根据栈 LIFO 的特性就可以实现后序遍历。
因此我们使⽤⼀个辅助栈来保存⽗节点，使⽤另⼀个栈保存我们需要的遍历结果的反序。
void postOrderTraver(TreeNode* root)
{
if(root ==nullptr)
return;
stack<TreeNode*> res;
泰坦尼克号歌词stack<TreeNode*> tmp;
tmp.push(root);
while(!pty()){
TreeNode* top = p();
tmp.pop();
if(top->left !=nullptr)
tmp.push(top->left);
if(top->right !=nullptr)
tmp.push(top->right);
res.push(top);
}
while(!pty()){
top = p();
cout << top->val;
res.pop();
}
}
层序遍历
规则是若树为空，则空操作返回，否则从树的第⼀层，也就是根结点开始访问，从上⽽下逐层遍历，在同⼀层中，按从左到右的顺序对结点逐个访问。即对⼆叉树的⼴度优先搜索（BFS）。
对于层序遍历，我们可以借助队列 queue 容器来实现，⾸先压⼊根节点，每次遍历我们⽤队列⾸元素遍历其左⼦节点并⼊队，然后遍历其右⼦节点并⼊队，最后将队⾸元素打印并出队，⼀次迭代直到队列为空。
void levelOrderTraver(TreeNode* root)
{
queue<TreeNode*> level_node;
女孩英语名字大全
if(root ==nullptr)
return;
level_node.push(root);
heatherwhile(!pty()){
TreeNode* front = level_node.front();
if(front->left !=nullptr)piece什么意思
level_node.push(front->left);
if(front->right !=nullptr)
parasomnialevel_node.push(front->right);
cout << front->val;
level_node.pop();
}
cout << endl;
}
⼆叉树的相关题⽬
1. 重建⼆叉树
题⽬描述：输⼊⼆叉树的前序遍历和中序遍历结果，重建⼆叉树。
算法分析：如前序遍历序列 {1, 2, 4, 7, 3, 5, 6, 8} 和中序遍历序列 {4, 7, 2, 1, 5, 3, 8, 6}，根据前序遍历特点，⼆叉树根节点为 1，在中序遍历序列中找到根节点 1，则根节点的前三个节点为左⼦树节点，后⾯的节点为右⼦树节点。根据中序遍历得到的结果，在前序遍历序列中根节点 1 后⾯的三个节
点即为左⼦树节点。
BinaryTreeNode*Construct(int* preorder,int* inorder,int length)
{
if(preorder ==nullptr|| inorder ==nullptr|| length <=0)
return nullptr;
return ConstructCore(preorder, preorder + length -1,
inorder, inorder + length -1);
}
BinaryTreeNode*ConstructCore(int* stratPreorder,int* endPreorder
int* startInorder,int* endInorder)
{
/
/ 前序遍历第⼀个数字就是根节点的值，初始化⼀个⼆叉树
int rootValue = startPreorder;
BinaryTreeNode* root =new BinaryTreeNode();
root->m_value = rootValue;
root->m_pLeft = root->m_pRight =nullptr;
山东中医药大学怎么样
if(startPreorder == endPreorder){
if(startInorder == endInorder &&
*startPreorder ==*startInorder)
return root;
el
throw std::exception("Invalid input.");
}
// 在中序遍历序列中找到根节点的值
int* rootInorder = startInorder;
while(rootInorder <= endInorder &&*rootInorder != rootValue)
++rootInorder;
flagyl
if(rootInorder == endInorder &&*rootInorder != rootValue)
throw std::exception("Invalid input.");
int leftLength = rootInorder - startInorder;
int*leftPreorderEnd = startPreorder + leftLength;
if(leftLength >0){
// 构建左⼦树
root->m_pLeft =ConstructCore(startPreorder +1,
leftPreorderEnd, startInorder, rootInorder -1);
印度留学中介}
if(leftLength < endPreorder - startPreorder){
// 构建右⼦树
root->m_pRight =ConstructCore(leftPreorderEnd +1,
endPreorder, rootInorder +1, endInorder);
}
return root;
}
2. ⼆叉树的下⼀个节点
题⽬描述：给定⼀个⼆叉树和其中的⼀个节点，找到中序遍历序列的下⼀个节点。树中节点有两个指向左右⼦节点的指针，和⼀个指向⽗节点的指针。
算法分析：分为三种情况：1）⼀个节点如果有右⼦树，则下⼀个节点就是它的右⼦树中最左⼦节点；2）节点没有右⼦树，且它是⽗节点的左⼦节点，则下⼀个节点就是它的⽗节点；3）节点没有右⼦树，且是⽗节点的右⼦节点，这种情况⽐较复杂，我们需要沿指向它⽗节点的指针⼀直向上遍历，直到找到⼀个节点是其⽗节点的左⼦节点，则这个节点的⽗节点就是下⼀个节点。
