表結構樹演算法

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

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

❷ 對以孩子鏈表表示的樹編寫計算樹的深度的演算法

typedef struct TreeNode
{
TreeNode *child;
TreeNode *sibling;
int data;
}TreeNode;
//這是用了遞歸的思想，需要仔細體會
int GetChildeSiblingTreeDegree(TreeNode *root)
{
//如果當前樹的根節點沒有孩子和兄弟，那麼，該樹的度就是0
if (root->child == NULL && root->sibling == NULL)
{
return 0;
}
//如果該樹只有兄弟，則該樹的度就等效於對他的兄弟分支的子樹求度
else if( root->sibling != NULL)
{
return GetChildeSiblingTreeDegree(root->sibling);
}
//如果該樹只有孩子，那麼先求出該根節點的度，然後再對它孩子分支子樹求度，兩者取較大者，即該樹的度
else if(root->child != NULL)
{
int rootDegree = 1;
TreeNode *p = root->child;

while(p->sibling != NULL)
{
p = p->sibling;
rootDegree++;
}

int childTreeDegree = GetChildeSiblingTreeDegree(root->child);

return rootDegree > childTreeDegree ? rootDegree : childTreeDegree;
}
}

❸ 以二叉連表做存儲結構，試編寫按層次順序遍歷二叉樹的演算法

//二叉樹，按層次訪問
//引用如下地址的思想，設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;

void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}

}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//構造成滿二叉樹，利於查看結果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;

createBTree(&(*tree)->left);

createBTree(&(*tree)->right);

}
}

void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}

void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}

visitBTree(q);
}
}

❹ 以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的演算法

樹的高度：對非空二叉樹，其深度等於左子樹的最大深度加1。

Int Depth(BinTree *T){int dep1,dep2;

if(T==Null) return(0);

else{dep1=Depth(T->lchild);

dep2=Depth(T->rchild);

if(dep1>dep2) return(dep1+1);

else return(dep2+1);}

樹的寬度：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反復，直到隊列為空。

int Width(BinTree *T){intfront=-1,rear=-1;

/*隊列初始化*／int flag=0,count=0,p;

/* pint CountNode (BTNode *t)

//節點總數{int num;if (t == NULL)num = 0;

elsenum = 1 + CountNode (t->lch) + CountNode (t->rch);

return (num);}void CountLeaf (BTNode *t)

//葉子節點總數{if (t != NULL){if (t->lch == NULL && t->rch == NULL)count ++;

// 全局變數CountLeaf (t->lch);CountLeaf (t->rch);}}。

(4)表結構樹演算法擴展閱讀

方法：

求二叉樹的高度的演算法基於對二叉樹的三種遍歷，可以用後序遍歷的演算法加上記錄現在的高度和已知的最高的葉子的高度，當找到一個比已知高度還要高的葉子，刷新最高高度。

最後遍歷下來就是樹的高度，至於後序遍歷的演算法，是一本數據結構或者演算法的書中都有介紹和參考代碼