二叉树及其线索化

二叉树及其线索化

概念

1、结点的度：结点拥有的子树个数 2、树的度：树内各结点度的最大值 3、叶结点(终端结点)：度为0的结点 4、分支结点：度大于0的结点 5、满二叉树：所有的分支结点都存在左右孩子，左右的叶子结点都在同一层的二叉树 6、完全二叉树：对一棵具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点中位置完全相同，那此树就是一棵满二叉树(结点只能从左到右，从上往下生长) 7、平衡二叉树：如果某二叉树中任意结点的左右子树的深度相差不超过1 ，那么它就是一棵平衡二叉树

性质

1、在二叉树的第i层最多有2^(i-1)个结点 2、深度为k的二叉树最多有2^k-1个结点 3、对任何一颗二叉树，若有n0个叶结点，度为2的结点数位n2，则n0 = n2 + 1 (树枝数 = n0 + n1 + n2 -1 = n1 + 2*n2) 4、具有n个结点的完全二叉树的深度为[log2n] + 1(2为底，n的对数) 5、对一棵有n个结点的完全二叉树按层编号(从0开始)： A.若 i = 0，则结点 i 为二叉树的根；若 i > 0, 则其双亲为[(i-1) / 2] B.若 2 * i +1 > n，则结点 i 无左孩子，否则其左孩子是结点 2 * i + 1 C.若 2 * i +2 > n，则结点 i 无右孩子，否则其右孩子是结点 2 * i + 2

遍历二叉树

先序遍历：根左右

先序代码：

void PreOrderTraverse(Node* node){ if(node == NULL) return ; cout<data<<" "; PreOrderTraverse(node->lchild); PreOrderTraverse(node->rchild);}

中序遍历：左根右

中序代码：

void InOrderTraverse(Node* node){ if(node == NULL) return ; InOrderTraverse(node->lchild); cout<data; InOrderTraverse(node->rchild);}

后序遍历：左右根

后序代码：

void PostOrderTraverse(Node* node){ if(node == NULL) return ; PostOrderTraverse(node->lchild); PostOrderTraverse(node->rchild); cout<data;}

层次遍历：从上到下，从左到右

1、把根节点A放入队列，此时队列为：A，队列头指针指向A，也就是队列第一个元素2、把当前队列头指针所指元素的左右儿子放入队列，即将B C放入队列，此时队列为A B C ，队列头指针向后移一格，此时指向B3、不断重复2步骤。此时把B的左右儿子取出来放入队尾，队列变为A B C D， 队列头指针后移，指向C。把C的左右儿子取出来放入队尾，队列变为A B C D E F 队列头指针后移，指向D。把D的左右儿子取出来放入队尾，队列变为A B C D E F G H 队列头指针后移，指向E。把E的左右儿子取出来放入队尾，队列变为A B C D E F G H I 4、结束条件，队列头指针和为指针重合时，输出最后一个元素，算法结束！也就是说，把这个队列从头到尾输出一遍，就是按层遍历，这个队列是动态的，只要有子节点，子节点就会不停的加入队尾，但总有子节点没有的时候，所以，队列尾指针肯定有不再移动的时候，而头指针一直在一步一步向下移，总会有首尾指针重合的时候，即标志着算法结束。

层次遍历代码：

void LevelOrderTraverse(Node* root){ if(root == NULL) return ; queue q; q.push(root); while(!q.empty()){ cout<data<<" "; if(q.front()->lchild != NULL){ q.push(q.front()->lchild); } if(q.front()->rchild != NULL){ q.push(q.front()->rchild); } q.pop(); } cout<

注:已知中序遍历和先序遍历结果，或已知中序遍历和后序遍历结果可以还原二叉树

二叉树深度

最简单的方式就是使用递归的方式来遍历二叉树，在递归的处理函数中逐渐增加二叉树的深度

int getDeepth(Node* node){ if(node == NULL) return 0; int left = getDeepth(node->lchild); int right = getDeepth(node->rchild); return left>right ? left+1 : right+1;}

图解(深度为3)：

注：‘#’ 表示此结点为空，向调用处返回0，实际的二叉树如下

判断平衡二叉树

递归地检查二叉树中所有结点的左右子树的深度之差，若都相差不超过1 ，那么它就是一棵平衡二叉树

bool isBalanced(Node* node){ if(node == NULL) return true; int left = getDeepth(node->lchild); int right = getDeepth(node->rchild); int gap = abs(left - right); //对于当前结点而言，左右子树的深度之差大于1，不平衡 if(gap > 1) return false; //对于当前结点而言，左右子树的深度只差不大于1，平衡 //接着检查其左右子树是否平衡 return isBalanced(node->lchild) && isBalanced(node->rchild);}

构造二叉搜索树的insert操作

Node* insert(Node* node, int num){ if(node == nullptr){ node = new Node(num);//当前结点为空，直接构造结点挂上 }else if(node->val > num){ node->left = insert(node->left, num); }else if(node->val < num){ node->right = insert(node->right, num); } //相等直接返回 return node;}

将有序数组转为二叉搜索树

class Solution {public: TreeNode* sortedArrayToBST(vector& nums) { return getBST(nums, 0, nums.size() - 1); } TreeNode* getBST(vector& nums, int l, int r){ if(l > r){ return nullptr; } int mid = (l + r) / 2; TreeNode* node = new TreeNode(nums[mid]); node->left = getBST(nums, l, mid - 1); node->right = getBST(nums, mid + 1, r); return node; }};

面向过程完整代码：

#include#includeusing namespace std;struct Node{ char data; Node* lchild; Node* rchild;}Node;//按先序输入二叉树结点的值//根据输入序列创建二叉树//用双指针是为了将根结点传入，执行函数完成后，还能通过此根结点找到树void CreateTree(Node** node){ char temp; cin>>temp; if(temp == '#') *node = NULL; else{ *node = (Node*)malloc(sizeof(Node)); (*node)->data = temp; CreateTree(&((*node)->lchild)); CreateTree(&((*node)->rchild)); }}//先序遍历void PreOrderTraverse(Node* node){ if(node == NULL) return ; cout<data<<" "; PreOrderTraverse(node->lchild); PreOrderTraverse(node->rchild);}//中序遍历void InOrderTraverse(Node* node){ if(node == NULL) return ; InOrderTraverse(node->lchild); cout<data; InOrderTraverse(node->rchild);}//后序遍历void PostOrderTraverse(Node* node){ if(node == NULL) return ; PostOrderTraverse(node->lchild); PostOrderTraverse(node->rchild); cout<data;}void LevelOrderTraverse(Node* root){ if(root == NULL) return ; queue q; q.push(root); while(!q.empty()){ cout<data<<" "; if(q.front()->lchild != NULL){ q.push(q.front()->lchild); } if(q.front()->rchild != NULL){ q.push(q.front()->rchild); } q.pop(); } cout<lchild); int right = getDeepth(node->rchild); return left>right ? left+1 : right+1;}bool isBalanced(Node* node){ if(node == NULL) return true; int left = getDeepth(node->lchild); int right = getDeepth(node->rchild); int gap = abs(left - right); //对于当前结点而言，左右子树的深度之差大于1，不平衡 if(gap > 1) return false; //对于当前结点而言，左右子树的深度只差不大于1，平衡 //接着检查其左右子树是否平衡 return isBalanced(node->lchild) && isBalanced(node->rchild);}int main(){ Node* root = (Node*)malloc(sizeof(Node)); //测试数据AB#D##C## cout<<"输入数据："; CreateTree(&root); cout<<"先序遍历结果："; PreOrderTraverse(root); cout<

运行结果：

注：创建结果如上图(二叉树深度部分的图)

面向对象版完整代码

#include#includeusing namespace std;typedef struct Node{ char data; struct Node* lchild; struct Node* rchild;}Node;class Tree{ private: Node* root; int tree_deepth; //先序 void Pre(Node* node){ if(node == NULL) return ; cout<data<<" "; Pre(node->lchild); Pre(node->rchild); } //中序 void In(Node* node){ if(node == NULL) return ; In(node->lchild); cout<data; In(node->rchild); } //后序 void Post(Node* node){ if(node == NULL) return ; In(node->lchild); In(node->rchild); cout<data; } //层次 void Level(Node* node){ if(root == NULL) return ; queue q; q.push(root); while(!q.empty()){ cout<data<<" "; if(q.front()->lchild != NULL){ q.push(q.front()->lchild); } if(q.front()->rchild != NULL){ q.push(q.front()->rchild); } q.pop(); } cout<>temp; if(temp == '#') *node = NULL; else{ *node = (Node*)malloc(sizeof(Node)); (*node)->data = temp; CreateTree(&((*node)->lchild)); CreateTree(&((*node)->rchild)); } } int Deepth(Node* node){ if(node == NULL) return 0; int left = Deepth(node->lchild); int right = Deepth(node->rchild); return left>right ? left+1 : right+1; } bool Balanced(Node* node){ if(node == NULL) return true; int left = Deepth(node->lchild); int right = Deepth(node->rchild); int gap = abs(left - right); //对于当前结点而言，左右子树的深度之差大于1，不平衡 if(gap > 1) return false; //对于当前结点而言，左右子树的深度只差不大于1，平衡 //接着检查其左右子树是否平衡 return Balanced(node->lchild) && Balanced(node->rchild); } public: Tree(){ root = (Node*)malloc(sizeof(Node*)); cout<<"输入数据："; CreateTree(&root); } void PreOrderTraverse(){ Pre(root); } void InOrderTraverse(){ In(root); } void PostOrderTraverse(){ Post(root); } void LevelOrderTraverse(){ Level(root); } void CountDeepth(){ tree_deepth = Deepth(root); } int getDeepth(){ CountDeepth(); return tree_deepth; } bool isBalanced(){ return Balanced(root); }};int main(){ //AB#D##C## Tree tree; cout<<"先序遍历结果："; tree.PreOrderTraverse(); cout<<"中序遍历结果："; tree.InOrderTraverse(); cout<<"后序遍历结果："; tree.PostOrderTraverse(); cout<

线索二叉树

将普通二叉树线索化成中序线索二叉树：

线索二叉树的数据结构：

中序线索二叉树的存储结构：

将普通二叉树线索化成先序线索二叉树：

先序线索二叉树的存储结构：

将普通二叉树线索化成后序线索二叉树：

后序线索二叉树的存储结构：

用两个指针，在中序遍历的同时，将二叉树中序线索化：

中序线索化实现代码：

先序线索化实现代码：

后序线索化实现代码：

注： 只有构造先序线索二叉树时，才需要判断左指针是否是真实的结点。因为先序遍历的顺序是【根，左，右】，访问根结点后可能会线索化左指针。改变左指针后，马上再接着访问当前根结点的左孩子，就会访问到当前根结点的父结点，然后又访问回来…，这样死循环下去。

别的顺序线索化二叉树，不需要判断左指针是否是真实的结点。中序线索化时，先访问左孩子，由于左孩子线索化后，会接着访问根结点，不会再往下层访问，所以线索化对中序遍历没有影响。后序线索化同样的分析。

中序线索化二叉树完整代码：

#include#include#include#includeusing namespace std;struct TreeNode { char val; TreeNode *left; TreeNode *right; int ltag; int rtag; TreeNode(char x) : val(x), left(nullptr), right(nullptr), ltag(0), rtag(0) { }};TreeNode* buildTree(vector& preorder, vector& inorder) { if(preorder.size() == 0){ return nullptr; } TreeNode* root = new TreeNode(preorder[0]); auto mid = find(inorder.begin(), inorder.end(), preorder[0]); //指向根结点值的迭代器 char left_nodes = mid - inorder.begin(); //左子树结点数目 vector left_preorder(preorder.begin()+1, preorder.begin()+1+left_nodes); vector right_preorder(preorder.begin()+1+left_nodes, preorder.end()); vector left_inorder(inorder.begin(), mid); vector right_inorder(mid+1, inorder.end()); root->left = buildTree(left_preorder, left_inorder); root->right = buildTree(right_preorder, right_inorder); return root;}void inVisit(TreeNode* cur, TreeNode* &pre){ if(cur->left == nullptr){ cur->left = pre; cur->ltag = 1; } if(pre != nullptr && pre->right == nullptr){ pre->right = cur; pre->rtag = 1; } pre = cur;}void inThread(TreeNode* root, TreeNode* &pre){ if(root != nullptr){ inThread(root->left, pre); inVisit(root, pre); inThread(root->right, pre); }}TreeNode* getInThreadTree(TreeNode* root){ TreeNode* pre = nullptr; if(root != nullptr){ inThread(root, pre); if(pre->right == nullptr){ pre->rtag = 1; //处理遍历的最后一个结点 } } return root;}int main(){ vector preorder = {'A', 'B', 'D', 'G', 'E', 'C', 'F'}; vector inorder = {'D', 'G', 'B', 'E', 'A', 'F', 'C'}; TreeNode* root = buildTree(preorder, inorder); //构造上图的二叉树 TreeNode* inThreadTree = getInThreadTree(root); cout<right->left->right->val<

树的孩子兄弟表示法：

森林与二叉树相互转换：

先将每棵树按照孩子兄弟表示法转换为二叉树，然后把C、D当作B的兄弟结点，挂到B的后子树上，就像这样：

将二叉树按照孩子兄弟表示法还原为森林：

树的先根遍历

先访问根，在从左往后访问子树

树的后根遍历

先从左往后访问子树，最后访问根

因为树中，不管是左孩子还是右孩子对应到孩子兄弟表示法的二叉树中，都是左孩子。所以树中的【左、右、根】对应成了二叉树中的【左、根】，换到下一颗树遍历时，二叉树就变成了右孩子，故 树的后序遍历 = 对应二叉树的中序遍历

树的层次遍历

森林的遍历

森林的先序遍历 = 从左到右对每棵树先序遍历 = 对应二叉树的先序遍历森林的中序遍历 = 从左到右对每棵树后序遍历 = 对应二叉树的中序遍历

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。