二叉樹的遞歸演算法
1. 二叉樹先序遍歷遞歸演算法和非遞歸演算法本質區別
在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此時棧已空，就有問題
}
pBiNode = pBiNode->rchild;
}
return 0;
}
2. 先序遍歷二叉樹的遞歸演算法怎樣理解（嚴蔚敏主編）
先序調用的時候，遞歸函數，先序函數會一直遞歸，直到t->next為空，即t為葉節點，需要注意的是當t->next 為空時，函數的實參沒有傳過去，所以t指向葉結點的父節點，更要注意的是，先序調用的遞歸函數還沒執行完，在先序調用的最里層，要執行這個函數的最後一個語句，即先序訪問右子樹。
在了解遞歸函數時，要注意函數是一層一層執行的，把沒有調用的函數看作哦是第一層，第一次調用的時候，，勢必會第二次遇到調用函數，變成第二層，，，，
3. 求統計二叉樹葉子結點數的遞歸演算法
···cpp
由於不知道你的存儲方式，假設你是指針存，用孩子兄弟表示法。
（偽）代碼：
structnode{
data{
...
}val;
node*fchild,*brother;
}
voidgetnum(nodex){
if(x.fchild==nu)ans++;
else{
getnum(*x.fchild);
getnum(*x.brother);
}
}就這樣
4. 二叉樹中序遍歷遞歸演算法
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍歷二叉樹
這段程序我全有，具體如下：
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree //定義二叉樹
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//
BiNode * new()//為新結點開辟空間
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)//創建新有子樹
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)//創建新結點
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)//輸出
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍歷
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍歷
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}
5. 有關二叉樹遞歸的演算法
靠，縮進全被網路搞亂了，自己排版
#include <iostream>
using namespace std;
//二叉樹節點
struct BiTreeNode{
int data;
BiTreeNode *left;
BiTreeNode *right;
};
//寫一個類，方便二叉樹的建立和刪除
class BiTree{
private:
void deleteAllNode(BiTreeNode *root);
public:
BiTreeNode *root;
BiTree();
~BiTree();
void CreateTree();
void deleteLeaves(BiTreeNode *root);
bool DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather);
void FindMaxValue(BiTreeNode *currentNode, int *maxValue);
void ExchangeLeftAndRight(BiTreeNode *currentNode);
void OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather); //不好意思，用了拼音
};
BiTree::BiTree()
{
root = NULL;
}
BiTree::~BiTree()
{
deleteAllNode(root);
}
void BiTree::deleteAllNode(BiTreeNode *root)
{
if (root == NULL) return;
deleteAllNode(root->left);
deleteAllNode(root->right);
cout << root->data << ' '; //用來查看當前節點是不是被刪除。
delete root;
}
//手動建立一個二叉樹用於測試
// 1
// / \
// 2 3
// \ /
// 4 5
void BiTree::CreateTree()
{
if (root) return;
root = new BiTreeNode;
root->data = 1;
root->left = new BiTreeNode;
root->left->data = 2;
root->right = new BiTreeNode;
root->right->data = 3;
BiTreeNode *p;
p = root->left;
p->left = NULL;
p->right = new BiTreeNode;
p->right->data = 4;
p->right->left = p->right->right = NULL;
p= root->right;
p->left = new BiTreeNode;
p->left->data = 5;
p->left->left = p->left->right = NULL;
p->right = NULL;
}
//用遞歸演算法刪除葉子
void BiTree::deleteLeaves(BiTreeNode *root)
{
if (root == NULL) return;
if (!root->left && !root->right) return; //表示是根節點(或者出錯，跑到葉子節點了，這種情況應該不會)，不刪除
if (root->left) //當前節點有左子樹
{
if (root->left->left || root->left->right) //左子樹不是葉子
deleteLeaves(root->left);
else //當前節點的左子節點是葉子
{
delete root->left;
root->left = NULL;
}
}
if (root->right)
{
if (root->right->left || root->right->right)
deleteLeaves(root->right);
else //當前節點的右子節點是葉子
{
delete root->right;
root->right = NULL;
}
}
}
int depth = 0; //一個用來存儲深度的全局變數，雖然在實際編程中這樣用不好
//但一切為了方便。
//節點p的深度,遞歸法
bool BiTree::DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)
{
if (currentNode == NULL) return false;
if (currentNode == p) //當前節點為要找的節點
{
depth = depthOfFather + 1;
return true;;
}
if (DepthOfTheNode(currentNode->left, p, depthOfFather+1)) //找當前節點的左子樹
return true;
else
return DepthOfTheNode(currentNode->right, p, depthOfFather+1);
}
//用遞歸找最大值，最大值存儲在maxValue所指的內存 ,這里使用前序遍歷
void BiTree::FindMaxValue(BiTreeNode *currentNode, int *maxValue)
{
if (currentNode == NULL) return;
*maxValue = *maxValue > currentNode->data ? *maxValue : currentNode->data;
FindMaxValue(currentNode->left, maxValue); //遍歷左子樹
FindMaxValue(currentNode->right, maxValue);
}
//交換左右，用前序遍歷
void BiTree::ExchangeLeftAndRight(BiTreeNode *currentNode)
{
if (currentNode == NULL) return;
BiTreeNode *temp;
temp = currentNode->left;
currentNode->left = currentNode->right;
currentNode->right = temp;
ExchangeLeftAndRight(currentNode->left);
ExchangeLeftAndRight(currentNode->right);
}
//以前序次序輸出一棵二叉樹所有結點的數據值及結點所在層次
void BiTree::OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)
{
if (currentNode == NULL) return;
cout << "節點：" << currentNode->data;
cout << "\t深度：" << depthOfFather+1 << endl;
OutputValueAndDepthByQIANXU(currentNode->left, depthOfFather+1);
OutputValueAndDepthByQIANXU(currentNode->right, depthOfFather+1);
}
int main()
{
BiTree bt;
bt.CreateTree();
//求p的深度
bt.DepthOfTheNode(bt.root, bt.root->left->right, 0);
cout << "深度:" << depth << endl;
//找最大值
int maxValue;
bt.FindMaxValue(bt.root, &maxValue);
cout << "最大值為：" << maxValue << endl;
//交換左右節點
bt.ExchangeLeftAndRight(bt.root);
//以前序次序輸出一棵二叉樹所有結點的數據值及結點所在層次
bt.OutputValueAndDepthByQIANXU(bt.root, 0);
//刪除葉子節點
bt.deleteLeaves(bt.root);
return 0;
}
6. 設二叉樹的存儲結構為二叉鏈表，編寫有關二叉樹的遞歸演算法：
給了一個程序給你參考，有前中後序遍歷，實現了前5個功能。
提示：8功能可以用任意一種遍歷方法，在程序中，將列印字元的部分換成自己的判斷程序即可。
6功能用後續遍歷，當遍歷到任意一節點時，判斷其孩子是不是葉子，是就刪除。
7功能參考求廣度的實現】
9功能參考6功能，用前序遍歷也可以
10功能也參考求廣度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE 12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍歷
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//創建堆棧
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆棧
top = stack;
p = t;
while (p || top>stack)//p不為NULL，堆棧不空
if (p)
{
*top++ = p;//p入堆棧
p = p->lchild;
}
else
{
p = *--top;//p出棧
if (p) printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍歷
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//後序遍歷
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍歷求結點的深度和度為0，1,2的結點數，結果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍歷用的數據
BiTree **stack, **top, *p;
//求深度的數據
int curDeep, MostDeep;
//創建堆棧
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆棧
top = stack;
p = t;
//初始化數據
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍歷循環
while (p || top>stack)//p不為NULL，堆棧不空
if (p)
{
*top++ = p;//p入堆棧
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出棧
curDeep--;
//if (p) printf("%d ", p->data); //Visit結點
//計算個結點的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序遞歸求廣度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求廣度的程序，返回值為廣度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
7. 編寫一個復制一棵二叉樹的遞歸演算法……
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,同學，拿分來吧~
8. 關於遞歸演算法求二叉樹深度演算法
u,v 分別求出當前節點左子樹和右子樹的深度（高度），
然後當前節點的 深度就等於左右子樹裡面較大的那個+1.
if (u>n) return (u+1)
return (v+1)
這句就是返回較深的+1.
u=height(T->lchild);
v=height(T->rchild);
這兩句就是遞歸的調用，求深度了。
if (T==NULL) return 0;
這個就是終止條件了，如果沒有子節點就返回。
9. 用遞歸演算法先序中序後序遍歷二叉樹
1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
棗蘆 printf(「%d 」, BT->Data); //對節點做些訪問比如列印
PreOrderTraversal(BT->Left); //訪問左兒子
PreOrderTraversal(BT->Right); //訪問右兒子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d ", BT->Data);
InOrderTraversal(BT->Right);
}
}
3、後序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
(9)二叉樹的遞歸演算法擴展閱讀：
注意事項
1、前序遍歷
從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。
2、中序遍歷
從整棵凳滑帶二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若讓襲LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。
3、後序遍歷
將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。