数据结构基础内容 - 树
作者:
gnn
,
2023-10-18 08:09:38
,
所有人可见
,
阅读 116
//节点定义
struct TreeNode
{
int val;
TreeNode * left;
TreeNode * right;
TreeNode() : val(0), left(nullptr), right(nullptr){}
TreeNode(int x) : val(x), left(nullptr), right(nullptr){}
TreeNode(int x, TreeNode *left, TreeNode * right) : val(int x), left(left), right(right){}
};
//前序遍历
void preorder(TreeNode *root)
{
if(!root) return;
cout << root -> val << ' ';
preorder(root -> left);
preorder(root -> right);
}
//非递归前序遍历
void preorder2(TreeNode *root)
{
stack<TreeNode*> s;
s.push(root);
while(!s.empty())
{
TreeNode *t = s.top();
s.pop();
cout << t -> val << ' ';
if(t -> right) s.push(t -> right);
if(t -> left) s.push(t -> left);
}
}
//中序遍历
void inorder(TreeNode *root)
{
if(!root) return;
inorder(root -> left);
cout << root -> val << ' ';
inorder(root -> right);
}
//非递归中序遍历
void inorder2(TreeNode *root)
{
stack<TreeNode*> s;
TreeNode* curr = root;
while(curr || !s.empty())
{
//当前节点左子节点全部入栈(即找到第一个没有左子节点的节点)
while(curr)
{
s.push(curr);
curr = curr -> left;
}
//从栈中弹出一个节点计算
curr = s.top();
s.pop();
//输出节点
cout << curr -> val << " ";
// 使当前节点指向右子节点
curr = curr -> right;
}
}
//后序遍历
void postorder(TreeNode *root)
{
if(!root) return;
postorder(root -> left);
postorder(root -> right);
cout << root -> val << ' ';
}
//非递归后序遍历
void postorder2(TreeNode* root)
{
stack<TreeNode*> s;
TreeNode* curr = root;
TreeNode* prev = NULL;
while(curr || !s.empty())
{
while(curr)
{
s.push(curr);
curr = curr -> left;
}
curr = s.top();
if(!curr -> right || curr -> == prev)
{
s.pop();
cout << curr -> val << " ";
prev == curr;
curr = nullptr;
}
else curr = curr -> right;
}
}
//层次遍历
void leverOrder(TreeNode *root)
{
queue<TreeNode*> q;
q.push(root);
while(!q.empty())
{
TreeNode *t = q.front();
q.pop();
cout << t -> val << ' ';
if (t -> left) q.push(t -> left);
if(t -> right) q.push(t -> right);
}
}