参考教材: 《2021年王道数据结构复习指导》
$5.3$ 二叉树的遍历和线索二叉树
- 采用$C$++$11$完成习题
- 测试结果将写在注释部分
- 为使代码简介,栈将调用$STL$标准栈
- 源代码下载
$0$.预定义
# include <iostream> # include <ctime> # include <stack> using namespace std; //二叉树节点结构体定义 struct TreeNode { int val; TreeNode*left,*right; TreeNode() { val = 0; left = right = nullptr; } TreeNode(int _val,TreeNode* _left,TreeNode *_right) { val = _val; left = _left; right = _right; } TreeNode(int _val) { val = _val; left = right = nullptr; } void display() { cout<<" address : "<<this<<endl; cout<<" value : "<<val<<endl; cout<<" left-child : "<<left<<endl; cout<<"right-child : "<<right<<endl; } }; //随机产生一个二叉树节点 TreeNode* Random_TreeNode() { TreeNode* node = new TreeNode(rand()%20); return node; } //随机构造一棵二叉树 TreeNode* Random_Tree(int round) { TreeNode * root = Random_TreeNode(); TreeNode *pre = root; for(int i = 0;i < round;i++) { int tag = rand()%2; if(tag) { TreeNode* tmp1 = Random_TreeNode(); TreeNode* tmp2 = Random_TreeNode(); pre->left = tmp1; pre->right = tmp2; pre = (rand()%2)?tmp1:tmp2; } else { TreeNode* tmp1 = Random_TreeNode(); if(rand()%2) pre->left = tmp1; else pre->right = tmp1; pre = tmp1; } } return root; } int main(void) { srand((unsigned)time(0)); //test_chapter5_binary_tree_1(); return 0; }
$1$.编写二叉树三种遍历的非递归形式。
void PreOrder(TreeNode *t) { if(!t) return ; printf("%d ",t->val); PreOrder(t->left); PreOrder(t->right); } void InOrder(TreeNode *t) { if(!t) return ; InOrder(t->left); printf("%d ",t->val); InOrder(t->right); } void PostOrder(TreeNode *t) { if(!t) return ; PostOrder(t->left); PostOrder(t->right); printf("%d ",t->val); } void PreOrderWithStack(TreeNode *t) { stack<TreeNode*> s; while(!s.empty() || t) { while(t) { printf("%d ",t->val); s.push(t); t = t->left; } if(!s.empty()) { t = s.top(); s.pop(); t = t->right; } } cout<<endl; } void InOrderWithStack(TreeNode *t) { stack<TreeNode*> s; while(!s.empty() || t) { while(t) { s.push(t); t = t->left; } if(!s.empty()) { t = s.top(); s.pop(); printf("%d ",t->val); t = t->right; } } cout<<endl; } void PostOrderWithStack(TreeNode *t) { stack<TreeNode*> s; TreeNode* r = nullptr; //r记录访问过的节点 while(!s.empty() || t) { while(t) { s.push(t); t = t->left; } if(!s.empty()) { t = s.top(); //已经走到最左边,回溯上个节点 if(t->right && t->right != r) //如果存在右子树且尚未被访问 { t = t->right; //转向右节点 s.push(t); //入栈 t = t->left; //重新一直向左走到底 } else { s.pop(); //左右均无,则再回溯 printf("%d ",t->val); //同时可以访问此时的子节点 r = t; //记录已经被访问过 t = nullptr; //重置 } } } cout<<endl; } void test_chapter5_binary_tree_1() { TreeNode *root = Random_Tree(10); cout<<"PreOrder in two Ways:"<<endl; PreOrder(root); cout<<endl; PreOrderWithStack(root); cout<<endl; cout<<"InOrder in two Ways:"<<endl; InOrder(root); cout<<endl; InOrderWithStack(root); cout<<endl; cout<<"PosrOrder in two Ways:"<<endl; PostOrder(root); cout<<endl; PostOrderWithStack(root);cout<<endl; } /* * Test Chapter5 Binary Tree 1 Result: * PreOrder in two Ways: * 15 6 7 5 16 1 3 7 12 13 7 14 1 5 * 15 6 7 5 16 1 3 7 12 13 7 14 1 5 * InOrder in two Ways: * 6 15 5 1 7 3 13 1 14 5 7 12 16 7 * 6 15 5 1 7 3 13 1 14 5 7 12 16 7 * PostOrder in two Ways: * 6 7 1 5 14 7 13 12 3 1 16 5 7 15 * 6 7 1 5 14 7 13 12 3 1 16 5 7 15 */
$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$
$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$
$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$
$\textrm{Last Modified: 2021-04-08 19:26}$
退出登录?