Tree Traversal
Tree traversal is a process of visiting each node in the tree exactly once in some order.
树的遍历有2种方式,Breadth-first(广度优先)
和Depth-first(深度优先)
。
Breadth-first(广度优先)
按照广度优先,对二叉树的遍历方式主要是Level-order(层序遍历)
。
Level-order(层序遍历)
层序遍历即对一个二叉树每层从上到下,从左到右进行遍历。
上图层序遍历顺序即为F D J B E G K A C I H
.
实现
用队列可以实现层序遍历。因为队列有First-In-First-Out(FIFO)原则,我们可以先让root进入队列,在访问节点时,让其左右节点进入队列。
实现层序遍历的代码如下:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13
| #include<queue> void LevelOrder(BstNode* root) { if (root == NULL)return; queue<BstNode*> Q; Q.push(root); while (!Q.empty()) { BstNode* current = Q.front(); cout << current->data << " "; if (current->left != NULL)Q.push(current->left); if (current->right != NULL)Q.push(current->right); Q.pop(); } }
|
Depth-first(深度优先)
深度优先有三个排序方法,Preorder(前序)
、Inorder(中序)
和Postorder(后序)
。
类型 |
Order |
Preorder |
<root><left><right>(DLR) |
Inorder |
<left><root><right>(LDR) |
Postorder |
<left><right><root>(LRD) |
上图三种不同方式的排列顺序分别为:
Preorder: F D B A C E J G I H K
Inorder: A B C D E F G H I J K
Postorder: A C B E D H I G K J F
实现
三种顺序都可以用递归来简洁地写出,代码如下:
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| void Preorder(BstNode* root) { if (root == NULL)return; printf("%d ", root->data); Preorder(root->left); Preorder(root->right); } void Inorder(BstNode* root) { if (root == NULL)return; Inorder(root->left); printf("%d ", root->data); Inorder(root->right); } void Postorder(BstNode* root) { if (root == NULL)return; Postorder(root->left); Postorder(root->right); printf("%d ", root->data); }
|
最后附上完整代码,输出树的高度,层序遍历,前序,中序,后序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
| #include<iostream> #include<queue> using namespace std; struct BstNode { int data; BstNode* left; BstNode* right; }; void LevelOrder(BstNode* root) { if (root == NULL)return; queue<BstNode*> Q; Q.push(root); while (!Q.empty()) { BstNode* current = Q.front(); cout << current->data << " "; if (current->left != NULL)Q.push(current->left); if (current->right != NULL)Q.push(current->right); Q.pop(); } printf("\n"); } void Preorder(BstNode* root) { if (root == NULL)return; printf("%d ", root->data); Preorder(root->left); Preorder(root->right); } void Inorder(BstNode* root) { if (root == NULL)return; Inorder(root->left); printf("%d ", root->data); Inorder(root->right); } void Postorder(BstNode* root) { if (root == NULL)return; Postorder(root->left); Postorder(root->right); printf("%d ", root->data); } BstNode* GetNewNode(int data) { BstNode* NewNode = new BstNode(); NewNode->data = data; NewNode->left = NewNode->right = NULL; return NewNode; } BstNode* Insert(BstNode* root,int data) { if (root == NULL) root = GetNewNode(data); else if (data <= root->data) { root->left = Insert(root->left, data); } else root->right = Insert(root->right, data); return root; } int max(int a, int b) { if (a > b)return a; else return b; } int FindHeight(BstNode* root) { if (root == NULL) { return -1; } return max(FindHeight(root->left), FindHeight(root->right)) + 1; } int main() { BstNode* root = NULL; root = Insert(root,3); root = Insert(root, 6); root = Insert(root, 2); root = Insert(root, 1); root = Insert(root, 7); root = Insert(root, 5); root = Insert(root, 8); root = Insert(root, 4); printf("Height of tree is %d\n", FindHeight(root)); cout << "LevelOrder:"; LevelOrder(root); cout << "Preorder:"; Preorder(root); cout << endl; cout << "Inorder:"; Inorder(root); cout << endl; cout << "Postorder:"; Postorder(root); return 0; }
|