當前位置:首頁 » 操作系統 » 二叉樹的復制演算法

二叉樹的復制演算法

發布時間: 2022-09-01 01:42:14

❶ 二叉鏈表表示二叉樹,復制一顆二叉樹,如何用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書

熱點內容
安卓怎麼傳視頻 發布:2025-07-08 04:03:26 瀏覽:913
oracle測試sql 發布:2025-07-08 03:16:54 瀏覽:974
php壁紙源碼 發布:2025-07-08 03:04:26 瀏覽:321
android應用層 發布:2025-07-08 02:42:32 瀏覽:301
大唐存儲銷量 發布:2025-07-08 02:41:11 瀏覽:582
腳本怎麼打開 發布:2025-07-08 02:41:06 瀏覽:822
貴州電信iPtv升級伺服器地址 發布:2025-07-08 02:38:48 瀏覽:412
電腦怎麼鏈接本地伺服器 發布:2025-07-08 02:34:22 瀏覽:147
android調試webview 發布:2025-07-08 02:26:28 瀏覽:358
壓縮袋鞋子 發布:2025-07-08 02:21:30 瀏覽:752