二叉樹復制的演算法

A. 編寫復制一棵二叉樹的遞歸演算法，我的演算法正確嗎

#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;
}

B. 編寫一個復制一棵二叉樹的遞歸演算法……

void CopyTree(BiTree S,BiTree &T){
if (!s) T=NULL;
else{
CopyTree(S->lchild,lptr);//復制左扒納培子樹到lptr
CopyTree(S->rchild,rptr);//茄虛復制右子樹到rptr
T=(BiTree)malloc(sizeof（BiNode));
T->data=S->data;
T->lchild=lptr;T->春唯rchild=rptr;
}//else
}//CopyTree
hiahia,同學，拿分來吧~

C. 二叉樹以二叉鏈表存儲，試定義二叉鏈表的結構，並編寫復制一棵二叉樹的演算法。

用遞歸實現：
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);
}
}

D. 計算機二級二叉樹演算法

1、二叉樹的概念

二叉樹是一種特殊的樹形結構，每個結點最多隻有兩棵子樹，且有左右之分不能互換，因此，二叉樹有五種不同的形態。

2、二叉樹的性質

性質1 在二叉樹的第k層上，最多有2^(k-1)(k≥1）個結點。

性質2 深度為m的二叉樹最多有2^m-1個結點。

性質3 在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多一個。

性質4 具有n個結點的二叉樹，其深度不小於[log2n]+1,其中[log2n]表示為log2n的整數部分。

E. 請利用棧的基本操作寫出復制二叉樹的非遞歸演算法

//非遞歸方法
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;
}
這個應該沒問題了，

F. 二叉樹各種計算公式總結有哪些

二叉樹各種計算公式總結有n個節點的二叉樹一共有2n除以n乘以 n+1這種，n層二叉樹的第n層最多為2乘n減1個。二叉樹節點計算公式 N 等於n0加n1加n2，度為0的葉子節點比度為2的節點數多一個。N等於1乘n1加2乘n2加1。具有n個節點的完全二叉樹的深度為log2n加 1。

二叉樹的含義

二叉樹是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其演算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個最多隻能有兩棵子樹，且有左右之分。

二叉樹是n個有限元素的集合，該集合或者為空，或者由一個稱為根的元素及兩個不相交的，被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。

G. 復制二叉樹的非遞歸演算法.演算法思想和演算法實現.

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寫成指針就可以使用...