二叉树的复制算法

❶ 二叉链表表示二叉树，复制一颗二叉树，如何用C语言算法设计，希望答案正确且完整

生成一个二叉树的结点
(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode *GetTreeNode(TElemType item,
BiTNode *lptr , BiTNode *rptr ){
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(1);
T-> data = item;
T-> lchild = lptr; T-> rchild = rptr;
return T;
}
BiTNode *CopyTree(BiTNode *T) {
if (!T ) return NULL;
if (T->lchild )
newlptr = CopyTree(T->lchild);//复制左子树
else newlptr = NULL;
if (T->rchild )
newrptr = CopyTree(T->rchild);//复制右子树
else newrptr = NULL;
newT = GetTreeNode(T->data, newlptr, newrptr);
return newT;
} // CopyTree
希望对你有所帮助，因为我也是这半学期刚学的，嘿嘿

❷ 复制一棵二叉树的算法

我的思路是利用满二叉树的性质来判断。满二叉树一定符合
节点数
=
2的n次方
-1
（n为深度）
所以可以先遍历二叉树，并记录深度和节点数，最后做出判断
#include
void
inorder(bintree
*t,int
currentdeep)
{
if(*t!=null)
{
if(currentdeep>deep)
deep=currentdeep;
/*
如果当前深度大于记录的深度，则更新深度
*/
countnodes++;
/*
节点数加一
*/
inorder(t->lchild,currentdeep+1);
/*
访问当前节点的左孩子，并把当前节点的深度+1传给调用函数
*/
inorder(t->rchild,currentdeep+1);
/*
访问当前节点的右孩子，并把当前节点的深度+1传给调用函数
*/
}
}
main()
{
/*
p
为二叉树的根节点，其定义略
*/
int
currentdeep=1;
/*
currentdeep用于记录当前深度
static
int
deep=0;
/*
静态变量deep用于记录已检索的最大深度
*/
static
int
countnodes=0;
/*
静态变量countnodes用于记录已检索的节点数目
*/
inorder(p,currentdeep);
/*
中序遍历二叉树从而得到二叉树的深度以及节点数目
*/
if(countnodes<(pow(2,deep)-1))
printf("这不是一棵满二叉树。");
else
printf("这是一棵满二叉树。");
/*
利用满二叉树的节点数一定等于2的深度次方减1做出判断
*/
/*
pow函数的作用是求2的deep次方
*/
camb_yang
同学满二叉树为什么就不用判断呢？

❸ 编写复制一棵二叉树的递归算法，我的算法正确吗

#include
using namespace std;

typedef struct TNode//二叉树结构
{
char nodeValue;//结点的值
TNode* left;//左子树
TNode* right;//右子树
}*BiTree;
void CreateBiTree(BiTree &T)//中序遍历方式创建二叉树 ,输入#代表该结点为空
{
char nodeValue;
cin>> nodeValue;
if(nodeValue!='#')//结点非空
{
T=new TNode;
T->nodeValue=nodeValue;
CreateBiTree(T->left);
CreateBiTree(T->right);
}
else T=NULL;

}
int CountLeaf(BiTree T)
{
static int LeafNum=0;//叶子初始数目为0，使用静态变量
if(T)//树非空
{
if(T->left==NULL&&T->right==NULL)//为叶子结点
LeafNum++;//叶子数目加1
else//不为叶子结点
{
CountLeaf(T->left);//递归统计左子树叶子数目
CountLeaf(T->right);//递归统计右子树叶子数目
}
}
return LeafNum;
}
//用来测试的main函数，
int main()
{
BiTree T;
int leafNum;
cout<<"请输入中序遍历的二叉树序列(#号代表该结点为空)：如(ABC##DE#G##F###)"<<endl;
CreateBiTree(T);
leafNum=CountLeaf(T);
cout<<"该二叉树中叶子结点数为："<<leafNum<<endl;
return 0;
}

❹ 二叉树是否相似的证明 复制二叉树的非递归算法

恩

❺ 请利用栈的基本操作写出复制二叉树的非递归算法

//非递归方法
pbinary_tree_node _binary_tree(pbinary_tree_node bt)
{//先序遍历输出一颗树的全部结点值1,2,3
stack<pbinary_tree_node> stack_left,stack_right;
pbinary_tree_node newbt;
if (bt!=NULL)
{
//new root
newbt=new binary_tree_node;
newbt->data=bt->data;
//travel bt and travel newbt at the same time
stack_left.push(bt);
stack_right.push(newbt);
while (!stack_left.empty())
{
pbinary_tree_node pleft=stack_left.top();
pbinary_tree_node pright=stack_right.top();
stack_left.pop();
stack_right.pop();
if (pleft->rchild!=0)
{
stack_left.push(pleft->rchild);
pright->rchild=new binary_tree_node;
pright->rchild->data=pleft->rchild->data;
stack_right.push(pright->rchild);
}
if (pleft->lchild!=0)
{
stack_left.push(pleft->lchild);
pright->lchild=new binary_tree_node;
pright->lchild->data=pleft->lchild->data;
stack_right.push(pright->lchild);
}
}
}
return newbt;
}

//递归方法
void _binary_tree(pbinary_tree_node bt,pbinary_tree_node &newbt)
{
if(bt!=NULL)
{
newbt=(pbinary_tree_node )malloc(sizeof(binary_tree_node));
newbt->data=bt->data;
_binary_tree(bt->lchild,newbt->lchild);
_binary_tree(bt->rchild,newbt->rchild);
}
else
newbt=NULL;
}
这个应该没问题了，

❻ 复制二叉树的非递归算法.算法思想和算法实现.

voidMain()
{
	BNodenode=newBNode(){
		value="1",
		lNode=newBNode(){
			value="1-1"
		},
		rNode=newBNode(){
			value="1-2",
			lNode=newBNode(){
				value="1-2-1",
				rNode=newBNode(){
					value="1-2-1-2"
				}
			},
			rNode=newBNode(){
				value="1-2-2"
			}
		}
	};
	
	BNodeclone=Clone(node);
}

BNodeClone(BNodesource){
	Stack<BNode>stack=newStack<BNode>();
	stack.Push(source);
	
	BNodedest=newBNode();
	Stack<BNode>stackDest=newStack<BNode>();
	stackDest.Push(dest);
	while(stack.Count>0){
		//复制节点的值
		BNodes=stack.Peek();
		BNoded=stackDest.Peek();
		d.value=s.value;

		if(s.lNode!=null){//寻找左子树作为下一个结点
			stack.Push(s.lNode);
			d.lNode=newBNode();
			stackDest.Push(d.lNode);
		}elseif(s.rNode!=null){//没有就找右子树
			stack.Push(s.rNode);
			d.rNode=newBNode();
			stackDest.Push(d.rNode);
		}else{//全没有跳转到父结点的右子树
			while(true){
				stack.Pop();
				stackDest.Pop();
				if(stack.Count<=0)break;
				
				BNodep=stack.Peek();
				if(p.rNode==s){//已经使用过右结点向上继续回溯
					s=p;
				}
				elseif(p.rNode!=null){
					stack.Push(p.rNode);
					d=stackDest.Peek();
					d.rNode=newBNode();
					stackDest.Push(d.rNode);
					break;
				}
				elses=p;
			}
		}
	}
	returndest;
}

//
classBNode{
	publicobjectvalue;
	publicBNodelNode;
	publicBNoderNode;
}

算法思想的话就是构建两个栈用于回溯父结点...

其实递归算法隐藏了栈而已... 手动把这个栈构建出来就算成功了...

以上是一段C#代码示例 java代码应该复制粘贴就能用 C或者C++的话把BNode写成指针就可以使用...

❼ 二叉树以二叉链表存储，试定义二叉链表的结构，并编写复制一棵二叉树的算法。

用递归实现：
void PrintBiTree(BiTree T){
cout<<endl;
LayerTraverse(T,printelem);
cout<<endl;
}
void CopyBiTree(BiTree T,BiTree &M){
if (!T) M=T;
else{
M=new BiTNode;
M->data=T->data;
CopyBiTree (T->lchild,M->lchild);
CopyBiTree(T->rchild,M->rchild);
}
}

❽ 数据结构Java版二叉树的复制算法

韦斯(Mark Allen Weiss)的维斯的数据结构与算法分析有本C语言版的,听说很我用的是C++版的，不过就遇到一个问题，现在我有时要用Java写程序，Mark书