首页 > 代码库 > 二叉树的创建、遍历
二叉树的创建、遍历
二叉树的创建。这里采用最简单的情况，创建完全二叉树，用数组来保存：
1 struct TreeNode 2 { 3 int val; 4 TreeNode *left, *right; 5 TreeNode(int x): val(x), left(NULL), right(NULL) {}; 6 }; 7 8 void CreatTree(TreeNode *root, int idx, int A[], int n) //root结点已分配，idx为根结点的编号 9 {10 if(2 * idx <= n) //左儿子11 {12 root->left = new TreeNode(A[2 * idx - 1]);13 CreatTree(root->left, 2 * idx, A, n);14 }15 if(2 * idx + 1 <= n) //右儿子16 {17 root->right = new TreeNode(A[2 * idx]);18 CreatTree(root->right, 2 * idx + 1, A, n);19 }20 }
二叉树的销毁：
1 void DestroyTree(TreeNode *root)2 {3 if(root == NULL)4 return;5 DestroyTree(root->left); //先递归删除子树6 DestroyTree(root->right);7 delete root;8 }
二叉树的层次遍历：
1 //层次遍历 2 void BreadthFirstPrint(TreeNode *root) //BFS, 用队列 3 { 4 if(root == NULL) 5 return; 6 queue<TreeNode *> que; 7 que.push(root); 8 9 TreeNode *current = NULL;10 while(!que.empty())11 {12 current = que.front();13 que.pop();14 15 cout << current->val << ‘ ‘;16 17 if(current->left != NULL)18 que.push(current->left);19 if(current->right != NULL)20 que.push(current->right);21 }22 }
二叉树的递归遍历：
1 //先序遍历，递归 2 void PreorderRe(TreeNode *root) 3 { 4 if(root == NULL) 5 return; 6 cout << root->val << ‘ ‘; 7 PreorderRe(root->left); 8 PreorderRe(root->right); 9 }10 11 //中序遍历，递归12 void InorderRe(TreeNode *root)13 {14 if(root == NULL)15 return;16 InorderRe(root->left);17 cout << root->val << ‘ ‘;18 InorderRe(root->right);19 }20 21 //后序遍历，递归版22 void PostorderRe(TreeNode *root)23 {24 if(root == NULL)25 return;26 PostorderRe(root->left);27 PostorderRe(root->right);28 cout << root->val << ‘ ‘;29 }
二叉树的非递归遍历，用栈：
1 //先序遍历，非递归，用栈；也是DFS算法 2 void PreorderStk(TreeNode *root) 3 { 4 if(root == NULL) 5 return; 6 stack<TreeNode *> stk; 7 stk.push(root); 8 9 TreeNode *current = NULL;10 while(!stk.empty())11 {12 current = stk.top();13 stk.pop();14 15 cout << current->val << ‘ ‘;16 17 if(current->right != NULL)18 stk.push(current->right);19 if(current->left != NULL)20 stk.push(current->left);21 }22 }23 24 //中序遍历，用栈，非递归25 void InorderStk(TreeNode *root)26 {27 if(root == NULL)28 return;29 stack<TreeNode *> stk;30 stk.push(root);31 32 TreeNode *current = root->left;33 while(!stk.empty() || current != NULL) //中序遍历，左子树访问完后栈为空，所以同时检测current，此时它指向右子树根34 {35 if(current != NULL) //向左遍历到底36 {37 stk.push(current);38 current = current->left;39 }40 else //左子树为空，访问元素后遍历其右子树41 {42 cout << stk.top()->val << ‘ ‘;43 current = stk.top()->right;44 stk.pop();45 }46 }47 }48 49 //后序遍历，非递归版，用栈50 void PostorderStk(TreeNode *root)51 {52 stack<TreeNode *> ndStk;53 TreeNode *cur = root, *prev = NULL; //维持一个prev指针，指向上一次访问的结点54 55 while(cur != NULL) //先向左遍历到底，入栈56 {57 ndStk.push(cur);58 cur = cur->left;59 }60 61 while(!ndStk.empty())62 {63 cur = ndStk.top();64 if(cur->right == prev) //右子树的根已访问，说明右子树访问完；或者右子树为空，则访问当前结点65 {66 cout << cur->val << ‘ ‘;67 ndStk.pop();68 prev = cur;69 }70 else //访问右子树71 {72 cur = cur->right;73 while(cur != NULL) //与处理根节点时的情况相同，向左遍历到底入栈，prev赋空值74 {75 ndStk.push(cur);76 cur = cur->left;77 }78 prev = NULL;79 }80 }//while81 }
二叉树的非递归遍历，O(1)空间，Morris遍历：
1 //先序遍历，非递归，O(1)空间。Morris遍历 2 void PreorderMrs(TreeNode *root) 3 { 4 TreeNode *p = root; 5 while(p != NULL) 6 { 7 if(p->left != NULL) //找中序遍历的前驱结点 8 { 9 TreeNode *tmp = p->left; 10 while(tmp->right != NULL && tmp->right != p) 11 tmp = tmp->right; 12 if(tmp->right == NULL) //前驱还未做标记，说明当前结点还没访问 13 { 14 tmp->right = p; //标记前驱结点，使其右儿子为当前结点 15 cout << p->val << ‘ ‘; 16 p = p->left; //访问当前节点后访问左子树 17 } 18 else //前驱已做标记，说明当前结点与左子树已访问过 19 { 20 tmp->right = NULL; 21 p = p->right; 22 } 23 } 24 else //左子树为空，访问当前节点后访问右子树 25 { 26 cout << p->val << ‘ ‘; 27 p = p->right; 28 } 29 } 30 } 31 32 //中序遍历，非递归，O(1)空间。Morris遍历。 33 void InorderMrs(TreeNode *root) 34 { 35 TreeNode *p = root; 36 while(p != NULL) 37 { 38 if(p->left != NULL) 39 { 40 TreeNode *tmp = p->left; 41 while(tmp->right != NULL && tmp->right != p) 42 tmp = tmp->right; 43 if(tmp->right == NULL) 44 { 45 tmp->right = p; 46 p = p->left; 47 } 48 else 49 { 50 cout << p->val << ‘ ‘; //和先序Morris的唯一不同点，访问元素的位置不同。当左子树访问完之后再访问当前结点。 51 p = p->right; 52 tmp->right = NULL; 53 } 54 } 55 else 56 { 57 cout << p->val << ‘ ‘; 58 p = p->right; 59 } 60 } 61 } 62 63 //后序遍历，非递归，O(1)空间。Morris遍历。需要两个辅助函数 64 void reverse(TreeNode *start, TreeNode *stop) 65 { 66 TreeNode *prev = start, *cur = start->right, *next; 67 while(prev != stop) 68 { 69 next = cur->right; 70 cur->right = prev; 71 prev = cur; 72 cur = next; 73 } 74 } 75 void printReverseList(TreeNode *start, TreeNode *stop) 76 { 77 TreeNode *p = stop; 78 reverse(start, stop); 79 while(true) 80 { 81 cout << p->val << ‘ ‘; 82 if(p == start) 83 break; 84 p = p->right; 85 } 86 reverse(stop, start); 87 } 88 void PostorderMrs(TreeNode *root) 89 { 90 TreeNode dummy(-1), *p = &dummy; 91 dummy.left = root; //新建一个结点，把root作为左儿子，方便统一处理 92 93 while(p != NULL) 94 { 95 if(p->left != NULL) //找中序遍历的前驱结点 96 { 97 TreeNode *tmp = p->left; 98 while(tmp->right != NULL && tmp->right != p) 99 tmp = tmp->right;100 if(tmp->right == NULL)101 {102 tmp->right = p;103 p = p->left;104 }105 else106 {107 printReverseList(p->left, tmp); //与中序遍历的不同点，逆序输出当前结点的左儿子到前驱之间的路径108 109 tmp->right = NULL;110 p = p->right;111 }112 }113 else114 {115 p = p->right;116 }117 }//while118 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。