这里我们将看到一个有趣的问题。我们有一棵二叉树。我们必须以逆时针的方式遍历树。遍历的顺序如下所示 −
遍历序列是 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7
算法
antiClockTraverse(root)
Begin i := 1, j := height of the tree flag := false while i <= j, do if flag is false, then print tree elements from right to left for level i flag := true i := i + 1 else print tree elements from left to right for level j flag := false j := j - 1 end if doneEnd
示例
#includeusing namespace std;class Node { public: Node* left; Node* right; int data; Node(int data) { //constructor to create node this->data = data; this->left = NULL; this->right = NULL; }};int getHeight(Node* root) { if (root == NULL) return 0; //get height of left and right subtree int hl = getHeight(root->left); int hr = getHeight(root->right); return 1 + max(hl, hr); //add 1 for root}void printLeftToRight(class Node* root, int level) { if (root == NULL) return; if (level == 1) cout <data < 1) { printLeftToRight(root->left, level - 1); printLeftToRight(root->right, level - 1); }}void printRightToLeft(struct Node* root, int level) { if (root == NULL) return; if (level == 1) cout <data < 1) { printRightToLeft(root->right, level - 1); printRightToLeft(root->left, level - 1); }}void antiClockTraverse(class Node* root) { int i = 1; int j = getHeight(root); int flag = 0; //flag is used to change direction while (i left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->left = new Node(6); root->right->right = new Node(7); root->left->left->left = new Node(8); root->left->left->right = new Node(9); root->left->right->left = new Node(10); root->left->right->right = new Node(11); root->right->left->left = new Node(12); root->right->left->right = new Node(13); root->right->right->left = new Node(14); root->right->right->right = new Node(15); antiClockTraverse(root);}
输出
1 8 9 10 11 12 13 14 15 3 2 4 5 6 7
以上就是二叉树的逆时针螺旋遍历？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444073.html
微信扫一扫 
支付宝扫一扫 
