鏈表聲明：

//基本結(jié)構(gòu)聲明 #include<iostream> #include<queue> #include<stack> #include<cstdio>#define NoInfo 0 // 0表示沒有結(jié)點(diǎn) using namespace std; typedef int ElementType; typedef struct TNode* Position; typedef Position BinTree; //二叉樹鏈表結(jié)構(gòu) struct TNode{ElementType Data; //結(jié)點(diǎn)數(shù)據(jù) BinTree Left; //左子樹 BinTree Right; //右子樹 };　　 View Code

1.先序建立二叉樹

//先序建立二叉樹 BinTree CreateBinTree(){ElementType data;scanf("%d",&data);if(data==NoInfo) return NULL;BinTree P;P=new TNode;P->Data=data;P->Left=CreateBinTree();P->Right =CreateBinTree();return P; } View Code

2.層序建立二叉樹

//層序建立二叉樹 BinTree CreateBinTree(){ElementType data;BinTree BT,T;queue<BinTree> q;//創(chuàng)建隊(duì)列scanf("%d",&data);if(data!=NoInfo){BT=new TNode;BT->Data =data;BT->Left =BT->Right =NULL;q.push(BT);}else return NULL;//第一個數(shù)據(jù)為0則返回空樹while(!q.empty()){T=q.front();//取出結(jié)點(diǎn) q.pop();scanf("%d",&data);//讀入T的左孩子 if(data==NoInfo) T->Left =NULL;else{T->Left =new TNode;T->Left ->Data=data;T->Left ->Left=T->Left ->Right=NULL;q.push(T->Left );}scanf("%d",&data);//讀入T的右孩子 if(data==NoInfo) T->Right =NULL;else{T->Right =new TNode;T->Right ->Data=data;T->Right ->Left=T->Right ->Right=NULL;q.push(T->Right );}}return BT; } View Code

3.遞歸先序遍歷

void PreorderTraversal_1(BinTree BT){if(BT){printf("%d",BT->Data );PreorderTraversal_1(BT->Left );PreorderTraversal_1(BT->Right );} } View Code

4.非遞歸先序遍歷

void PreorderTraversal_2(BinTree BT){BinTree T=BT;stack<BinTree> s;while(T||!s.empty()){while(T){printf("%d",T->Data );s.push(T);T=T->Left ;}T=s.top();s.pop();T=T->Right ;} } View Code

5.遞歸中序遍歷

void InorderTraversal_1(BinTree BT){if(BT){InorderTraversal_1(BT->Left );printf("%d",BT->Data );InorderTraversal_1(BT->Right );} } View Code

6.非遞歸中序遍歷

//非遞歸中序遍歷 void InorderTraversal_2(BinTree BT){BinTree T=BT;stack<BinTree> s;while(T||!s.empty()){while(T){s.push(T);T=T->Left ;}T=s.top();s.pop();printf("%d",T->Data );T=T->Right ;} } View Code

7.遞歸后序遍歷

//遞歸后序遍歷 void PostorderTraversal_1(BinTree BT){if(BT){PostorderTraversal_1(BT->Left );PostorderTraversal_1(BT->Right );printf("%d",BT->Data );} } View Code

8.非遞歸后序遍歷

//非遞歸后序遍歷 void PostorderTraversal_2(BinTree BT){BinTree T,Pre=NULL;stack<BinTree> s;s.push(BT);while(!s.empty()){T=s.top();if( (T->Left ==NULL&&T->Right ==NULL) || (Pre!=NULL&& (T->Left==Pre ||T->Right==Pre ) ) ){printf("%d",T->Data );s.pop();Pre=T;}else{if(T->Right !=NULL) s.push(T->Right );if(T->Left !=NULL) s.push(T->Left );}} } View Code

9.層序遍歷

void LevelorderTravelsal(BinTree BT){queue<BTree> q;BinTree T;if(!BT) return;q.push(BT);while(!q.empty()){T=q.front();q.pop();printf("%d ",T->Data);if(T->Left ) q.push(T->Left );if(T->Right ) q.push(T->Right );} } View Code

10.二叉樹高度

//二叉樹高度 int GetHeight(BinTree BT){if(BT) return max(GetHeight(BT->Left),GetHeight(BT->Right ))+1;else return 0;//空樹高度為0 } View Code

11.求二叉樹所有結(jié)點(diǎn)

//求二叉樹所有結(jié)點(diǎn) int CountNode(BinTree BT){if(BT) return CountNode(BT->Left )+CountNode(BT->Right )+1;else return 0; } View Code

12.求二叉樹葉子結(jié)點(diǎn)

void LeaveCount(BinTree BT){if(BT){if(BT->Left ==NULL&&BT->Right ==NULL)count++;LeaveCount(BT->Left );LeaveCount(BT->Right ); } } View Code

?

int LeafcountofBinTree(BinTree BT){if(BT){if(BT->Left ==NULL&&BT->Right ==NULL)return LeafcountofBinTree(BT->Left )+LeafcountofBinTree(BT->Right )+1;}else return 0; } View Code

13.先序輸出二叉樹葉子結(jié)點(diǎn)?

void PreorderPrintLeaves(BinTree BT){if(BT!=NULL){if((BT->Left==NULL)&&(BT->Right==NULL))printf(" %c",BT->Data);PreorderPrintLeaves(BT->Left);PreorderPrintLeaves(BT->Right);} } View Code

14.鏡面反轉(zhuǎn)，將所有非葉結(jié)點(diǎn)的左右孩子對換?

void Inversion(BinTree BT){if(BT){Inversion(BT->Left);Inversion(BT->Right);BinTree temp;temp=BT->Left ;BT->Left =BT->Right ;BT->Right =temp;} } View Code

15.銷毀二叉樹

void DestroyBinTree(BinTree BT){if(BT){DestroyBinTree(BT->Left );DestroyBinTree(BT->Right );delete BT;BT=NULL;} } View Code

16.根據(jù)前序和中序遍歷還原二叉樹?

?1. 根據(jù)前序序列的第一個元素建立根結(jié)點(diǎn)；
2. 在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；
3. 在前序序列中確定左右子樹的前序序列；
4. 由左子樹的前序序列和中序序列建立左子樹；
5. 由右子樹的前序序列和中序序列建立右子樹。

//根據(jù)前序和中序遍歷還原二叉樹 BinTree PreInoRestoreBinTree(int* inorder ,int* preorder, int length) {if(length==0) return NULL;BinTree T=new TNode;int rootIndex;T->Data = *preorder;for(rootIndex=0;rootIndex < length; rootIndex++)if(inorder[rootIndex] == *preorder)break;T->Left = PreInoRestoreBinTree(inorder,preorder +1 , rootIndex);T->Right = PreInoRestoreBinTree(inorder + rootIndex + 1 ,preorder + rootIndex + 1 , length - (rootIndex + 1));return T; } View Code

17.根據(jù)后序和中序遍歷還原二叉樹?

?1. 根據(jù)后序序列的最后一個元素建立根結(jié)點(diǎn)；
2. 在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；
3. 在后序序列中確定左右子樹的后序序列；
4. 由左子樹的后序序列和中序序列建立左子樹；
5. 由右子樹的后序序列和中序序列建立右子樹

BinTree InoPosRestoreBinTree(int *inorder,int *postorder,int length) {if(length==0) return NULL;BinTree T;int rootindex;T =new TNode;T->Data=postorder[length-1];T->Left=T->Right=NULL;for(rootindex=0; rootindex < length; rootindex++)if(inorder[rootindex] == postorder[length-1])break;T->Left =InoPosRestoreBinTree(inorder,postorder,rootindex);T->Right =InoPosRestoreBinTree(inorder+rootindex+1,postorder+rootindex,length-(rootindex+1));return T; } View Code

?17.1 根據(jù)中序和后序輸出前序

#include<iostream> #include<vector> #include<string> using namespace std; string in, post, ans=""; void pre(int root, int l, int r){if(l>r) return ;int i=l;while(in[i] != post[root]) i++;//printf("%d %d %d %d\n",root,l,r,i);ans += post[root];//cout<<"L"<<endl;pre(root-r+i-1, l, i-1);//cout<<"R"<<endl;pre(root-1, i+1, r); } int main(){cin>>in>>post;pre(post.size()-1,0,post.size()-1);cout<<ans<<endl;return 0; } View Code

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/astonc/p/9906518.html

總結(jié)

以上是生活随笔為你收集整理的二叉树的建立和遍历的各种问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。