数据结构与算法-第12章二叉树和其他树-002克隆二叉树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法-第12章二叉树和其他树-002克隆二叉树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1956字,纯文字阅读大概需要3分钟。
内容图文
![数据结构与算法-第12章二叉树和其他树-002克隆二叉树](/upload/InfoBanner/zyjiaocheng/1061/6fdb0e9792174f618ba8beab363b699b.jpg)
例子中二叉树用链表示
1.后序遍历克隆和前序遍历克隆
1 package chapter12Tree; 2 3 // In writing the cloning codes, we assume that we are not to 4 // make clones of the elements in the nodes. Only the tree structure is to be cloned. 5 // In case the elements are also to be cloned, then we must replace all occurrences 6 // of element by code to first cast element into a CloneableObject, 7 // and then invoke the method clone on the reulting object. 8 public class BinaryTreeCloning 9 { 10 /** preorder cloning 11 * @return root of clone */ 12 public static BinaryTreeNode preOrderClone(BinaryTreeNode t) 13 { 14 if (t != null) 15 {// nonempty tree 16// make a clone of the root17 BinaryTreeNode ct = new BinaryTreeNode(t.element); 1819// now do the subtrees20 ct.leftChild = preOrderClone(t.leftChild); // clone left subtree21 ct.rightChild = preOrderClone(t.rightChild); // clone right subtree22return ct; 23 } 24else25returnnull; 26 } 2728/** postorder cloning 29 * @return root of clone */30publicstatic BinaryTreeNode postOrderClone(BinaryTreeNode t) 31 { 32if (t != null) 33 {// nonempty tree 34// clone left subtree35 BinaryTreeNode cLeft = postOrderClone(t.leftChild); 3637// clone right subtree38 BinaryTreeNode cRight = postOrderClone(t.rightChild); 3940// clone root41returnnew BinaryTreeNode(t.element, cLeft, cRight); 42 } 43else44returnnull; 45 } 46} 4748class BinaryTreeNode { 49int element; 50 BinaryTreeNode leftChild, rightChild; 5152// constructors53 BinaryTreeNode() {} 5455 BinaryTreeNode(int element) { 56this.element = element; 57this.rightChild = null; 58this.leftChild = null; 59 } 60 BinaryTreeNode(int element, BinaryTreeNode rc, BinaryTreeNode lc) { 61this.element = element; 62this.rightChild = rc; 63this.leftChild = lc; 64 } 65 }
The recursion stack space needed by both the preorder and postorder copy methods is O(h)
, where h
is the height of the binary tree being cloned
原文:http://www.cnblogs.com/shamgod/p/5295544.html
内容总结
以上是互联网集市为您收集整理的数据结构与算法-第12章二叉树和其他树-002克隆二叉树全部内容,希望文章能够帮你解决数据结构与算法-第12章二叉树和其他树-002克隆二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。