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

⑵ 求統計二叉樹葉子結點數的遞歸演算法

···cpp

由於不知道你的存儲方式，假設你是指針存，用孩子兄弟表示法。

（偽）代碼：

structnode{
data{
...
}val;
node*fchild,*brother;
}
voidgetnum(nodex){
if(x.fchild==nu)ans++;
else{
getnum(*x.fchild);
getnum(*x.brother);
}
}

就這樣

⑶ 二叉樹演算法是什麼

二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。

二叉樹的第i層至多有2^（i 1）個結點；深度為k的二叉樹至多有2^k 1個結點；對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1。二叉樹演算法常被用於實現二叉查找樹和二叉堆。

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作「左子樹」(left subtree)和「右子樹」(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

(3)5個結點二叉樹的遞歸演算法擴展閱讀：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

1、空二叉樹——(a)

2、只有一個根結點的二叉樹——(b);

3、右子樹為空的二叉樹——(c);

4、左子樹為空的二叉樹——(d);

5、完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

⑷ 求統計二叉樹葉子結點數的遞歸演算法

public static<T> int numOfLeavesInRecursion(BinaryTreeNode<T> root){ // 獲取二叉樹葉子節點的個數的遞歸演算法

if(root == null)

return 0;

if(root.getLeft() == null && root.getRight() == null)

return 1;

return numOfLeavesInRecursion(root.getLeft())+
numOfLeavesInRecursion(root.getRight());

}

⑸ 1、建立五個樹結點，將其鏈接成一棵二叉樹 2、以遞歸的方式先序遍歷該樹，並輸出每個結點的值

簡單畫出了5種形態

1)a
a
a

2) a
a
a

3) a
a a

4) a
a
a

5) a
a
a

⑹ 數據結構 遞歸演算法統計二叉樹結點個數

int
leafnum(Bnode
*t)
{
int
i,j;
if(
t
==
NULL
)return
0;
else
if(
t->lchild
==
NULL
&&
t->rchild
==
NULL
)
return
1;
else
{
i
=
leafnum(t->lchild);
j
=
leafnum(t->rchild);
return
(i+j);
}
}
??????
這個應該不是你要的，希望對你有所啟發。

⑺ 設二叉樹的存儲結構為二叉鏈表，編寫有關二叉樹的遞歸演算法：

給了一個程序給你參考，有前中後序遍歷，實現了前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;
}

⑻ 關於二叉樹遍歷的遞歸演算法

代碼寫錯了，要是遞歸的話，45行的函數應該是 pretrav;
這是深度遍歷。
邏輯很簡單啊：
比如一個二叉樹：
.............A
.........../...\
..........B.....C
........./.\......\
........D...E......F
......./
......G

第一次函數調用，傳入節點A。
執行到4，左子樹非空，
..調用 trav函數，傳入B，再執行到 第四步 B的左子樹非空，
....調用 trav函數，傳入 D，再執行到第四步 D的左子樹非空
......調用 trav函數，傳入 G。執行到第四步，
......左子空，跳過繼續，執行第五步，
......右子空，跳過繼續。返回到
....D節點的第五步，D的右子空 跳過繼續
..B節點的第五步，B右子非空
....調用 trav函數，傳入E,執行到第四步
....左子空，跳過繼續，執行第五步，
....右子空，跳過繼續。返回到
..B節點返回
A節點第五步，右子非空
..調用trav，傳入C，執行到第四步
..C的左子空，跳過繼續
..C的右子非空，
....調用trav，傳入 F,執行到第四步
....左子空，跳過繼續，執行第五步，
....右子空，跳過繼續。返回到
..c執行完，返回
A執行完，整個遍歷完成，返回

⑼ 先序遍歷二叉樹的遞歸演算法怎樣理解

二叉樹的結點結構是:
1、根結點（存放結點數據）
2、左子樹指針
3、右子樹指計
對二叉樹的遍歷就是訪問各個結點中根結點里存放的數據。例如：
如果結點A有左結點B，右結點C，記作A(B,C)，不同結點我用"\"隔開。那麼有這樣一個(BitTree)二叉樹表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己畫出來，不然我後面白講了。
要想把所有的數據都訪問到則必需按照一定的原則，即當前結點的下一個結點是哪個結點。
無論是先、中還是後序演算法都是先將左結點視為下一個結點，當左結點不存在（即為空時）才將右結點視作下一個結點，如果右結點也不存在就返回當前結點的上層結點再向右訪問，如此類推。
於是對二叉樹的遍歷問題就被抽象成三個基本步驟:
1、訪問根結點。
2、訪問該點的所有左子樹。
3、訪問該點的所有右子樹。
先序遍歷的策略是按123的步驟執行，中序是按213來，後序則是231,它們之間的不同只是「訪問根結點」在這三個步驟中的位置。
看著你剛畫好的那個BitTree跟著我的思路走。在先序遍歷演算法PriorOrder中,先將BitTree的頭結點A傳進來，按步驟123的處理。123是抽象實現，記住所表達的思想，下面是具體實現。為了避免混亂用中文數字記錄步驟。
一、即是讀取結點A的數據內容A（此時A為當前函數處理結點)，將A的右結點C放入棧S中，S中的內容為S（C）[注意這一步是演算法的一個輔助，並不是先向右訪問,下同]，將左結點B傳給PriorOrder處理。此時讀取了A
二、讀取B的內容B（此時B為當前結點），將B的右結點E放入S中，S中的內容為S(C,E),將B的左結點D傳給PriorOrder處理。此時讀取了AB
三、D為當前結點，D的右為空沒有東西放入S，S中的內容仍為S(C,E)，D的左也為空，沒有訪問可訪問的。此時就從S中取出E(因為棧是先進後出的所以取的就是E，此時S中的內容為S(C),正好是上一層沒訪問過的右子樹)，將E傳給PriorOrder處理。此時讀取了AB D
四、E為當前結點，對於結點E類似的有S(C,G),讀取了ABDE,將F傳入PriorOrder
五、F為當前結點，右為空，左也為空，讀取了ABDEF,從棧中取出G傳給PriorOrder處理,S的內容為S(C);
六、類似的讀取了ABDEFG,從S中取出了C，傳給PriorOrder處理。此時S（）。
七、當前結點為C，從將C的右結點放入S，S中內容為S(H),C的左為空，從S取出H，將H傳給PriorOrder處理。此時S為S().於是就讀取了ABDEFGC
八，類似的讀取了ABDEFGCH
九，最後ABDEFGCHF
你再對照的書上的演算法想想，畫畫就應該能明白點。特別要理角的一點是為什麼用遞歸演算法時計算機能按這樣的方式是因為函數調用是「先調用，後執行完」，或者說「後調用，先執行完」。注意我加一個「完」字