A. 二叉樹以鏈表的方式存儲,設計演算法輸出二叉樹中所有的葉子節點,同時給出每個葉子節點到根節點的路徑的長度
建立頭指針 h,和指向當前節點的指針 p = h;
按 先序 或 中序 遍歷該2叉樹.
當碰到葉子節點 c 時:
p->rchild = c;
p = c;
遍歷結束,返回h
*****************************
struct Node{
DateType date;
struct Node *lchild,*rchild
}*h,*p;
main()
{
*h = (Node *)malloc(sizeof(Node));
*p = h;
Node *tree;
/*取得2叉樹*/
...
/*遍歷*/
PreOderTraverse(tree);
p = h->rchild;
free(h);
/*輸出p*/
...
}
PreOrderTraverse(Node node)
{
if(node == null) return;
if(node->lchild == null && node->rchild == null)
{p->rchild = node;
p = node;
return;
}
PreOrderTraverse(node->lchild)
PreOrderTraverse(node->rchild)
}
B. 二叉樹是非線性數據結構，所以
二叉樹是非線性數據結構，所以（C、它能採用順序存儲結構和鏈式存儲結構存儲）。
一般而言，完全二叉樹（包括滿二叉樹）使用順序存儲，普通二叉樹一般用二叉鏈表或者三叉鏈表存儲。
二叉樹是n個有限元素的集合，該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成，是有序樹。當集合為空時，稱該二叉樹為空二叉樹。在二叉樹中，一個元素也稱作一個結點。
(2)樹鏈表存儲方式擴展閱讀：
若對一棵有n個節點的完全二叉樹進行順序編號（1≤i≤n），那麼，對於編號為i（i≥1）的節點：
當i=1時，該節點為根，它無雙親節點。
當i>1時，該節點的雙親節點的編號為i/2。
若2i≤n，則有編號為2i的左節點，否則沒有左節點 。
若2i+1≤n，則有編號為2i+1的右節點，否則沒有右節點。
C. 順序存儲是二叉樹常用的存儲結構嗎
二叉樹的存儲結構
二叉樹是非線性結構，即每個數據結點至多隻有一個前驅，但可以有多個後繼。它可採用順序存儲結構和鏈式存儲結構。
1．順序存儲結構
二叉樹的順序存儲，就是用一組連續的存儲單元存放二叉樹中的結點。因此，必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法從樹根起，自上層至下層，每層自左至右地給所有結點編號,缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為k且只有k個結點的右單支樹需要2k-1個結點存儲空間。依據二叉樹的性質，完全二叉樹和滿二叉樹採用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節省存儲空間，又可以利用數組元素的下標值確定結點在二叉樹中的位置，以及結點之間的關系。圖5-5(a)是一棵完全二叉樹，圖5-5（b）給出的圖5-5(a)所示的完全二叉樹的順序存儲結構。
(a) 一棵完全二叉樹 (b) 順序存儲結構
圖5-5 完全二叉樹的順序存儲示意圖
對於一般的二叉樹，如果仍按從上至下和從左到右的順序將樹中的結點順序存儲在一維數組中，則數組元素下標之間的關系不能夠反映二叉樹中結點之間的邏輯關系，只有增添一些並不存在的空結點，使之成為一棵完全二叉樹的形式，然後再用一維數組順序存儲。如圖5-6給出了一棵一般二叉樹改造後的完全二叉樹形態和其順序存儲狀態示意圖。顯然，這種存儲對於需增加許多空結點才能將一棵二叉樹改造成為一棵完全二叉樹的存儲時，會造成空間的大量浪費，不宜用順序存儲結構。最壞的情況是右單支樹，如圖5-7 所示，一棵深度為k的右單支樹，只有k個結點，卻需分配2k－1個存儲單元。
(a) 一棵二叉樹 (b) 改造後的完全二叉樹
(c) 改造後完全二叉樹順序存儲狀態
圖5-6 一般二叉樹及其順序存儲示意圖
(a) 一棵右單支二叉樹 (b) 改造後的右單支樹對應的完全二叉樹
(c) 單支樹改造後完全二叉樹的順序存儲狀態
圖5-7 右單支二叉樹及其順序存儲示意圖
結構5-1二叉樹的順序存儲
#define Maxsize 100 //假設一維數組最多存放100個元素
typedef char Datatype; //假設二叉樹元素的數據類型為字元
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;
2．鏈式存儲結構
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。
通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。其結點結構為：
其中，data域存放某結點的數據信息；lchild與rchild分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符號∧或NULL表示）。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為二叉鏈表，如圖5-8所示。
(a) 一棵二叉樹 (b) 二叉鏈表存儲結構
圖5-8 二叉樹的二叉鏈表表示示意圖
為了方便訪問某結點的雙親，還可以給鏈表結點增加一個雙親欄位parent,用來指向其雙親結點。每個結點由四個域組成，其結點結構為：
這種存儲結構既便於查找孩子結點，又便於查找雙親結點；但是，相對於二叉鏈表存儲結構而言，它增加了空間開銷。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為三叉鏈表。
圖5-9給出了圖5-8 (a)所示的一棵二叉樹的三叉鏈表表示。
圖5-9二叉樹的三叉鏈表表示示意圖
盡管在二叉鏈表中無法由結點直接找到其雙親，但由於二叉鏈表結構靈活，操作方便，對於一般情況的二叉樹，甚至比順序存儲結構還節省空間。因此，二叉鏈表是最常用的二叉樹存儲方式。
結構5-2二叉樹的鏈式存儲
#define datatype char //定義二叉樹元素的數據類型為字元
typedef struct node //定義結點由數據域，左右指針組成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;
D. 二叉樹只能採用二又鏈表來存儲.，這個是否正確，為什麼
不是的.
二叉鏈表只是最直觀的一種存儲方式.而事實上,大部分的情況都不會使用二叉鏈表.除了一些動態調整樹的演算法比如平衡樹.
更為普遍的存儲方式是用線性表來儲存二叉樹.這種方式下,線性表N存儲的節點是N div 2的兒子節點.
E. 二叉樹的二叉鏈表存儲結構如何實現
大概這個樣子，這個是我以前寫的二叉搜索樹：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data,rep;
struct node *left,*right;
} node;
node* insert(node *tree,int x);
int search(node *tree,int x);
node* del(node *tree,int x);
int main()
{
char str[20],ch;
int x;
struct node *tree = NULL;
gets(str);
while (strcmp(str,"quit"))
{
if (!strcmp(str,"insert"))
{
scanf("%d",&x);
tree = insert(tree,x);
}
else if (!strcmp(str,"delete"))
{
scanf("%d",&x);
tree = del(tree,x);
}
else if (!strcmp(str,"search"))
{
scanf("%d",&x);
if (search(tree,x))
puts("Found!");
else
puts("Not Found!");
}
else
puts("There is an error!");
ch = getchar();
gets(str);
}
return 0;
}
node* insert(node *tree,int x)
{
if (tree == NULL)
{
tree = (struct node *)malloc(sizeof(struct node *));
tree->data = x;
tree->rep = 1;
tree->left = (struct node *)malloc(sizeof(struct node *));
tree->right = (struct node *)malloc(sizeof(struct node *));
tree->left = NULL;
tree->right = NULL;
}
else if (tree->data == x)
tree->rep++;
else if (x < tree->data)
tree->left = insert(tree->left,x);
else if (x > tree->data)
tree->right = insert(tree->right,x);
return tree;
}
int search(node *tree,int x)
{
if (tree == NULL)
return 0;
else if (tree->data == x)
return 1;
else if (x < tree->data)
return search(tree->left,x);
else if (x > tree->data)
return search(tree->right,x);
}
node* del(node *tree,int x)
{
struct node *p,*q;
if (tree == NULL) {}
else if (x < tree->data)
tree->left = del(tree->left,x);
else if (x > tree->data)
tree->right = del(tree->right,x);
else if (tree->data == x)
{
if (tree->rep > 1)
tree->rep--;
else
{
if (tree->left == NULL)
return tree->right;
else if (tree->right == NULL)
return tree->left;
else
{
p = tree->left;
q = tree;
while (p->right)
{
q = p;
p = p->right;
}
tree->data = p->data;
tree->rep = p->rep;
q->right = p->left;
}
}
}
return tree;
}
F. 樹的鏈表存儲和順序存儲有什麼區別
順序存儲指的是存儲在數組中,用數組來模擬鏈表的指針
用數組的下標表示指針,或者乾脆聲明一個結構體(模擬指針 , 節點值)數組 ,來表示樹;
鏈式存儲就是用鏈表了,
他們都屬於線性表的范疇
G. 二叉樹以二叉鏈表方式存儲,以後序遍歷或層次遍歷的方式求各結點中最大元素的值
以下的函數以後序遍歷的方法求解
void findMax(BtNode *root, int &maxValue)
{
if(root == NULL)
{
return; // 若當前節點指針為空，則直接返回
}
findMax(root->leftChild, maxValue); // 先遍歷左子樹
findMax(root->rightChild, maxValue); // 再遍歷右子樹
if(maxValue < root->data)
{
maxValue = root->data; // 將當前節點的值與maxValue比較，如果大於maxValue，則將maxValue改為當前節點的值
}
}