在用二叉链表表示的有n个结点的二叉树中,值为非空的链域的个数为多少?答案是n-1,这个是为什么啊,

亲 我认为你没给分的话 应该没人为你回答的 虽然说我不会 但是你问这么多题不给分真的是有一点点点点点 好吧 很抠

给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include
#include
#include
#include
#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 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 memeryn");
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 memeryn");
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 memeryn");
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 memeryn");
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

#include
#include
typedef struct node
{
int data;
node *left;
node *right;
}node;
node* CreateTree(node *root,int n)
{
if(root==NULL)
{
root=(node *)malloc(sizeof(node));
root->data=n;
root->left=NULL;
root->right=NULL;
return root;
}
else if(n>root->data)
{
root->right=CreateTree(root->right,n);
return root;
}
else if(ndata)
{
root->left=CreateTree(root->left,n);
return root;
}

}
void Print(node *root)
{
if(root!=NULL)
{
Print(root->left);
printf("%d ",root->data);
Print(root->right);
}
return;
}
bool search(node* root,int a)
{
node *p=root;
while(p!=NULL)
{
if(a==p->data)
return true;
else if(a>p->data)
p=p->right;
else if(adata)
p=p->left;
}
return false;
}
void del(char *c)
{
int i,j=0,k=0;
bool b=true;
for(i=0;c[i]!=' ';++i)
{
b=true;
k=0;
while(k

最佳的方案是换整机,换CPU没意义478平台已经作古增加投入不值得,所带来的提升回报太小,如果短期内还没有升级平台的计划,建议入二手8600GT或3650PRO AGP版,主流游戏低效果可以坚持一段时间.

正确的是：A
链表是不能采用二分查找的,因为链表不具备随机访问特性.
二分查找的必要条件是：
线性表,有序；

1. 2n n-1 n+1
2. 2的k次方-1
3. 链表

http://www.***.net/Article/kfyy/sjjg/200706/4585.html
所有二叉树的操作实现，你要的都有

typedef struct node
{
char data;
struct node *lchild,*rchild;
}bitree;
bitree *root=NULL;
//创建树
bitree *CreateTree(char *sInPut)
{
bitree *root,*s;
bitree *Q[128];
int front,rear;
root=NULL;
front=1;
rear=0;
char temp[128],*p;
memset(temp,0,128);
strcpy(temp,sInPut);
p=temp;
while(strlen(p)>0)
{
s=NULL;
if(*p!='@')
{
s=(bitree*)malloc(sizeof(bitree));
s->data=*p;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
root=s;
}
else
{
if(s && Q[front])
{
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
}
if(rear%2==1) front++;
}
p+=2;
}
return root;
}
//释放树
void freetree(bitree *root)
{
if(root!=NULL)
{
freetree(root->lchild);
freetree(root->rchild);
free(root);
}
}
//前序遍历
void preorder(bitree *root)
{
if(root!=NULL)
{
printf("%ct",root->data);
preorder(root->lchild,sOutPut);
preorder(root->rchild,sOutPut);
}
}
//中序遍历
void inorder(bitree *root)
{
if(root!=NULL)
{
inorder(root->lchild,sOutPut);
printf("%ct",root->data);
inorder(root->rchild,sOutPut);
}
}
//后序遍历
void postorder(bitree *root)
{
if(root!=NULL)
{
postorder(root->lchild,sOutPut);
postorder(root->rchild,sOutPut);
printf("%ct",root->data);
}
}
//层次遍历
void PrintTree(bitree *root)
{
CString sOutPut;
char temp[128];
bitree *Q[128],*s;
int front,rear;
front=0;
rear=0;
sOutPut.Empty();
Q[rear++]=root;
while(rear>front)
{
printf("%ct",Q[front]->data);
sOutPut=temp;
s=Q[front++];
if(s->lchild!=NULL)
Q[rear++]=s->lchild;
if(s->rchild!=NULL)
Q[rear++]=s->rchild;
}
}
//树叶子数
void countleaf(bitree *root,int &count)
{ if(root!=NULL)
{ if((root->lchild==NULL)&&(root->rchild==NULL))
{ count++;
return;
}
countleaf(root->lchild,count);
countleaf(root->rchild,count);
}
}
//树深度
void treedepth(bitree *root,int l,int &h)
{ if(root!=NULL)
{ l=l+1;
if(l>h) h=l;
treedepth(root->lchild,l,h);
treedepth(root->rchild,l,h);
}
}

int getTotalNum(TreeNode *root)
{
if(root == NULL)
return 0;
else
return 1 + getTotalNum(root->left) + getTotalNum(root->right);
}

n个结点的二叉链表中必定存在n＋1个空链域
因为n个结点的二叉链表中有2n个孩子指针,而n个结点除根结点外,均有一个指针指向它,所以2n-(n-1)=n+1个指针是空的

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。
第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等操作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加time.h里的几个函数，配合使用下就出来了。
#include
#include
// binary search tree
typedef struct BST
{
int data;
struct BST* lhs;
struct BST* rhs;
}BST;
// 插入一个节点
BST* BSTInsertNode(BST* root, int elem)
{
BST* node;
node = (BST*)malloc(sizeof(BST));
node->data = elem;
node->lhs = node->rhs = 0;

if(!root)
return node;

while(1)
{
if(node->data < root->data)
{
if(root->lhs)
root = root->lhs;
else
{
root->lhs = node;
return root->lhs;
}
}
else
{
if(root->rhs)
root = root->rhs;
else
{
root->rhs = node;
return root->rhs;
}
}
}
}
// 获得父节点
BST* BSTGetParentNode(BST* root, BST* node)
{
if(root == node)
return 0;

if(root->lhs && node->data < root->lhs->data)
return BSTGetParentNode(root->lhs, node);
else if(root->rhs && node->data > root->rhs->data)
return BSTGetParentNode(root->rhs, node);
else
return root;
}
// 删除一个节点
BST* BSTDeleteNode(BST* root, BST* node)
{
BST* parent;
BST** whichNode;
BST* temp;

if(root != node)
{

parent = BSTGetParentNode(root, node);
whichNode = parent->lhs == node ? &parent->lhs : &parent->rhs;
}
else
whichNode = &root;
if(!node->lhs && !node->rhs)
*whichNode = 0;
else if(!((node->lhs ? 1 : 0) ^ (node->rhs ? 1 : 0)))
*whichNode = node->lhs ? node->lhs : node->rhs;
else
{
temp = node->rhs;
while(temp->lhs)
temp = temp->lhs;
temp->lhs = node->lhs;
*whichNode = node->rhs;
}
free(node);
return *whichNode;
}
// 删除树
void BSTDeleteTree(BST* node)
{
if(node)
{
BSTDeleteTree(node->lhs);
BSTDeleteTree(node->rhs);
free(node);
}
}
// 建造树，从数组构造
BST* BSTBuildTree(int* beg, int* end)
{
BST* root;

if(beg >= end)
return 0;

root = (BST*)malloc(sizeof(BST));
root->data = *beg++;
root->lhs = root->rhs = 0;

while(beg != end)
BSTInsertNode(root, *beg++);

return root;
}
// 查找节点
BST* BSTSearchNode(BST* root, int elem)
{
if(root)
{
if(elem < root->data)
return BSTSearchNode(root->lhs, elem);
else if(elem > root->data)
return BSTSearchNode(root->rhs, elem);
else
return root;
}
else
return 0;
}
// 获得最小值
BST* BSTGetMinimumNode(BST* root)
{
while(root->lhs)
root = root->lhs;
return root;
}
// 获得最大值
BST* BSTGetMaximumNode(BST* root)
{
while(root->rhs)
root = root->rhs;
return root;
}
// 前序遍历
void BSTPreorderTraverse(BST* node)
{
if(node)
{
printf("%d ", node->data);
BSTPreorderTraverse(node->lhs);
BSTPreorderTraverse(node->rhs);
}
}
// 中序遍历
void BSTInorderTraverse(BST* node)
{
if(node)
{
BSTInorderTraverse(node->lhs);
printf("%d ", node->data);
BSTInorderTraverse(node->rhs);
}
}
// 后序遍历
void BSTPostorderTraverse(BST* node)
{
if(node)
{
BSTPostorderTraverse(node->lhs);
BSTPostorderTraverse(node->rhs);
printf("%d ", node->data);
}
}
// 获得前继值
BST* BSTGetPredecessor(BST* root, BST* node)
{
BST* predecessor;
BST* rightCld;

if(node->lhs)
return BSTGetMaximumNode(node->lhs);

predecessor = rightCld = node;
while((predecessor = BSTGetParentNode(root, predecessor)))
if(predecessor->rhs == rightCld)
return predecessor;
else
rightCld = predecessor;
return 0;
}
// 获得后继值
BST* BSTGetSuccessor(BST* root, BST* node)
{
BST* successor;
BST* leftCld;

if(node->rhs)
return BSTGetMinimumNode(node->rhs);

successor = leftCld = node;
while((successor = BSTGetParentNode(root, successor)))
if(successor->lhs == leftCld)
return successor;
else
leftCld = successor;
return 0;
}
// 获得树高
int BSTGetTreeHeight(BST* root)
{
int l;
int r;
if(root)
{
l = BSTGetTreeHeight(root->lhs);
r = BSTGetTreeHeight(root->rhs);
return 1 + (l > r ? l : r);
}
else
return -1;
}
// 计算子节点数
int BSTGetSubtreeNodeNum(BST* node)
{
if(node)
return BSTGetSubtreeNodeNum(node->lhs)
+ BSTGetSubtreeNodeNum(node->rhs)
+ 1;
else
return 0;
}
// 用于打乱数组，交换
inline void Swap(int* a, int* b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// 用于打乱数组，qsort的比较用过程
inline int CMP(const void* lhs, const void* rhs)
{
return *(const int*)lhs - *(const int*)rhs;
}
// 数组有序?
int IsOrdered(int* beg, int* end)
{
int attri;
int cmpVal;
if(beg >= end)
return 0;
if(end - beg <= 2)
return 1;

if(*beg < *(beg + 1))
attri = 1;
else
attri = 0;

cmpVal = *beg++;
while(++beg != end)
{
if(attri)
{
if(cmpVal > *beg)
return 0;
}else
{
if(cmpVal < *beg)
return 0;
}
}
return 1;
}
// 高层次打乱数组
void HighlyUnorderArray(int* beg, int* end)
{

int* mid = beg + (end - beg)/2;
int* folk;
if(!IsOrdered(beg, end))
qsort(beg, end - beg, sizeof(int), CMP);

if((mid - beg) & 1)
Swap(beg++, mid);
folk = beg + 2;
while(folk < mid)
{
Swap(beg++, folk++);
Swap(beg++, folk++);
}

folk = mid + 2;
while(folk < end)
{
Swap(folk, folk - 1);
folk += 2;
}
}
// 中序遍历结果输出到数组
void BSTInorderWalkToArray(BST* root, int** p)
{
if(root)
{
BSTInorderWalkToArray(root->lhs, p);
**p = root->data;
(*p)++;
BSTInorderWalkToArray(root->rhs, p);
}
}
// 平衡树，返回平衡好的新树
BST* BSTBalanceTree(BST* root)
{
int size = BSTGetSubtreeNodeNum(root);
int* a = (int*)malloc(sizeof(int) * size);
int* end = a;
BST* balancedTree;

BSTInorderWalkToArray(root, &end);
HighlyUnorderArray(a, end);
balancedTree = BSTBuildTree(a, end);
free(a);
return balancedTree;
}
int main()
{
int a[] = ;
int c[] = ;
BST* bstTree = BSTBuildTree(a, a + sizeof(a)/sizeof(a[0]));

BSTPreorderTraverse(bstTree);
putchar('n');
BSTInorderTraverse(bstTree);
putchar('n');
BSTPostorderTraverse(bstTree);
printf("nn");

BST* balancedTree = BSTBalanceTree(bstTree);
printf("%d %dn", BSTGetTreeHeight(bstTree), BSTGetTreeHeight(balancedTree));
BSTDeleteTree(bstTree);
BSTDeleteTree(balancedTree);
}

靠，缩进全被百度搞乱了，自己排版

　　#include
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 data 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 right, 0);
cout

昨天U盘上还在。。。。。。。擦，刚删除，三种都编好的

您好，看到您的问题一直是零回答问题且将要被新提的问题从问题列表中挤出，问题无人回答过期后会被扣分并且悬赏分也将被没收！所以我给你提几条建议： 一，您可以选择在正确的分类下去提问或者到与您问题相关专业网站论坛里去看看，这样知道你问题答案的人才会多一些，回答的人也会多些。当然，找老师帮忙是最简单有效的方法！ 二，您可以多认识一些知识丰富的网友，和曾经为你解答过问题的网友经常保持联系，遇到问题时可以直接向这些好友询问，他们会更加真诚热心为你寻找答案的。 三，很多时候该自己做的事还是必须有自己独立完成的，有的事还是须由自己的聪明才智来解决的，别人不可能代劳！就算别人给你代劳，最后也不属于你的，只有自己做了才是真正属于自己的，别人只能给你提供指导和建议，最终靠自己。所以，祝愿你可以凭借自己的努力找到最终自己想要的结果！你是最棒的！ 您可以不采纳我的答案，但请你一定采纳我的建议哦！ 虽然我的答案很可能不能解决你的问题，但一定可以使你更好地使用问问哦~~~
希望采纳

某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用( )存储方式最节省运算时间.(A)...已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x 的结点插入到表L中,使得L仍然有序