急急急!!!二叉排序树的建立中序遍历时总是遍历不了！！！在线等,谢谢

Question

代码如下:#include<iostream.h>
struct bitree
{
int data;
bitree *lChild,*rChild;
};
int nCountNode = 0;
bitree *root;
bitree *Creat(int n)//创建二叉排序树,反复调用Insert函数
{
inline void Insert(bitree *BST,int x);
int x;
bitree *BST = NULL;
for(int i = 1;i<=n;i++)
{
cout<<"第"<<i<<"个:"<<endl;
cin>>x;
Insert(BST,x);
}
return BST;
}
void Insert(bitree *BST,int x)//插入
{
if(BST == NULL)
{
bitree *p = new bitree;
p->data = x;
p->lChild = NULL;
p->rChild = NULL;
BST = p;
}
else if(BST->data >= x)
{
Insert(BST->lChild,x);
}
else
{
Insert(BST->rChild,x);
}
}
void MidOrder(bitree *BST)//中序遍历
{
bitree *p = BST;
bitree *q[100];
int top = 0;
while(p != NULL || top > 0)
{
while(p != NULL)
{
q[++top] = p;
cout<<p->data<<" ";
p = p->lChild;
}
p = q[top--];
p = p->rChild;
}
}void main()
{ cout<<"请输入结点数目:"<<endl;
cin>>nCountNode;
cout<<"请输入"<<nCountNode<<"个结点"<<endl;
root = Creat(nCountNode);
cout<<"中序遍历:"<<endl;
MidOrder(root);
cout<<endl;
}

Answer 1

Bitree的代码怎么就这么少啊？

Answer 2

http://www.yonjie.com/mladmin123456/SouthidcEditor/Include/4408281-29529.html

Answer 3

函数void Insert(bitree *BST,int x)//插入 
就错了
构建不了树

Answer 4

#pragma once#include "resource.h"struct bitree
{
int data;
bitree *lChild,*rChild;
};bitree *Creat(int n);//创建二叉排序树,反复调用Insert函数
void Insert(bitree **BST,int x);
void MidOrder(bitree *BST);// Test.cpp : Defines the entry point for the console application.
//#include "stdafx.h"
#include "Test.h"#ifdef _DEBUG
#define new DEBUG_NEW
#endif
// The one and only application objectCWinApp theApp;
int nCountNode = 0;
bitree *root;using namespace std;int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
int nRetCode = 0; // initialize MFC and print and error on failure
if (!AfxWinInit(::GetModuleHandle(NULL), NULL, ::GetCommandLine(), 0))
{
// TODO: change error code to suit your needs
_tprintf(_T("Fatal Error: MFC initialization failed\n"));
nRetCode = 1;
}
else
{
// TODO: code your application's behavior here.
cout <<"请输入结点数目:" <<endl;
cin>>nCountNode;
cout <<"请输入" <<nCountNode <<"个结点" <<endl;
root = Creat(nCountNode);
cout <<"中序遍历:" <<endl;
MidOrder(root);
cout <<endl;
} return nRetCode;
}
bitree *Creat(int n)//创建二叉排序树,反复调用Insert函数
{
//  inline void Insert(bitree *BST,int x);
int x;
bitree *BST = NULL;
for(int i = 1;i <=n;i++)
{
cout <<"第" <<i <<"个:" <<endl;
cin>>x;
Insert(&BST,x);
}
return BST;
}
void Insert(bitree **BST,int x)//插入
{
if(*BST == NULL)
{
//  bitree *p = new bitree;
//  p->data = x;
//  p->lChild = NULL;
//  p->rChild = NULL;
*BST = new bitree;
(*BST)->data = x;
(*BST)->lChild = NULL;
(*BST)->rChild = NULL;
}
else if((*BST)->data >= x)
{
Insert(&(*BST)->lChild,x);
}
else
{
Insert(&(*BST)->rChild,x);
}
}
void MidOrder(bitree *BST)//中序遍历
{
bitree *p = BST;
bitree *q[100];
int top = 0;
while(p != NULL || top > 0)
{
while(p != NULL)
{
q[++top] = p;
cout <<p->data <<" ";
p = p->lChild;
}
p = q[top--];
p = p->rChild;
}
}

Answer 5

楼主的用法是
void Insert(bitree *BST,int x)
{
}
这时BST是个局部的指针，不能和
函数bitree *Creat(int n)中的BST衔接故二叉树没有创建起来

Answer 6

我这个是平衡二叉树的，希望对你有用。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
int flag = FALSE;
struct element {
int key;
};
struct tree_node {
tree_node *left_child;
tree_node *right_child;
element data;
int bf;
};
void left_rotation(tree_node *&parent)
{
tree_node *child = parent->left_child;
if(child->bf == 1) {
parent->left_child = child->right_child;
child->right_child = parent;
parent->bf = 0;
parent = child;
} else {
tree_node *grand_child = child->right_child;
parent->left_child = grand_child->right_child;
child->right_child = grand_child->left_child;
grand_child->right_child = parent;
grand_child->left_child = child;
switch(grand_child->bf) {
case 0:         parent->bf = child->bf = 0;
break;
case 1:         parent->bf = -1;
child->bf = 0;
break;
case -1:        parent->bf = 0;
child->bf = 1; 
}
parent = grand_child;
}
parent->bf = 0;
}
void right_rotation(tree_node *&parent)
{
tree_node *child = parent->right_child;
if(child->bf == -1) {
parent->right_child = child->left_child;
child->left_child = parent;
parent->bf = 0;
parent = child;
} else {
tree_node *grand_child = child->left_child;
parent->right_child = grand_child->left_child;
child->left_child = grand_child->right_child;
grand_child->right_child = child;
grand_child->left_child = parent;
switch(grand_child->bf) {
case 0:         parent->bf = child->bf = 0;
break;
case -1:        parent->bf = 1;
child->bf = 0;
break;
case 1:         parent->bf = 0;
child->bf = -1;
}
parent = grand_child;
}
parent->bf = 0;
}
void avl_insert(tree_node *&parent, element x, int &unbalanced)
{
if(parent == NULL) {
parent = (tree_node*)malloc(sizeof(tree_node));
parent->left_child = parent->right_child = NULL;
parent->data = x;
parent->bf = 0;
unbalanced = TRUE;
} else if(x.key < parent->data.key) {
avl_insert(parent->left_child, x, unbalanced);
if(unbalanced) {
switch(parent->bf) {
case 0:         parent->bf = 1;
break;
case -1:        parent->bf = 0;
unbalanced = FALSE;
break;
case 1:         left_rotation(parent);
unbalanced = FALSE;
}
}
} else if(x.key > parent->data.key) {
avl_insert(parent->right_child, x, unbalanced);
if(unbalanced) {
switch(parent->bf) {
case 0:         parent->bf = -1;
break;
case 1:         parent->bf = 0;
unbalanced = FALSE;
break;
case -1:        right_rotation(parent);
unbalanced = FALSE;
}
}
} else {
unbalanced = FALSE;
}
}
void swap(tree_node *p, tree_node *q)
{
element temp = p->data;
p->data = q->data;
q->data = temp;
}
void avl_del(tree_node *&parent, element x, int &unbalanced)
{
if(parent->data.key == x.key) {
unbalanced = TRUE;
if(!parent->right_child && !parent->left_child) {
parent = NULL;
} else if(parent->right_child && !parent->left_child) {
parent = parent->right_child;
} else if(parent->left_child && !parent->right_child) {
parent = parent->left_child;
} else if(parent->left_child && parent->right_child) {
tree_node *p = parent;
p = p->right_child;
while(p->left_child) {
p = p->left_child;
}
swap(parent, p);
avl_del(parent->right_child, x, unbalanced);
}
} else if(x.key > parent->data.key) {
if(!parent->right_child) return;
avl_del(parent->right_child, x, unbalanced);
if(unbalanced) {
switch(parent->bf) {
case 0:         parent->bf = 1;
unbalanced = FALSE;
break;
case -1:        parent->bf = 0;
unbalanced = FALSE;
break;
case 1:         left_rotation(parent);
}
}
} else if(x.key < parent->data.key) {
if(!parent->left_child) return;
avl_del(parent->left_child, x, unbalanced);
if(unbalanced) {
switch(parent->bf) {
case 0:         parent->bf = -1;
unbalanced = FALSE;
break;
case 1:         parent->bf = 0;
unbalanced = FALSE;
break;
case -1:                right_rotation(parent);
}
}
}
}
void inorder(tree_node*);
int depth(tree_node*);
int main()
{
tree_node *root = NULL;
int tmp;
cin>>tmp;
while(tmp!=-1000) {
element data;
data.key = tmp;
avl_insert(root, data, flag);
cin>>tmp;
}
inorder(root);
printf("\n");
int depleft = depth(root->left_child);
int depright = depth(root->right_child);
printf("%d\n", depleft);
printf("%d\n", depright);
element data;
data.key = 92;
avl_del(root, data, flag);
inorder(root);
printf("\n");
        //PostOrderFree(root);
return 0;
}
int depth(tree_node *root)
{
if(root == NULL) return 1;
else {
int rcd = depth(root->right_child);
int lcd = depth(root->left_child);
if(lcd > rcd) return lcd + 1;
else return rcd + 1;
}
}
struct stack {
tree_node *data[1024];
int top;
};
void initstack(stack *s)
{
s->top = -1;
}
void pushstack(stack *s, tree_node *p)
{
if(s->top >= 1024) {
printf("stack full\n");
exit(1);
}
s->data[++s->top] = p;
}
void popstack(stack *s, tree_node *&p)
{
if(s->top == -1) {
printf("stack empty\n");
exit(1);
}
p = s->data[s->top--];
}
void inorder(tree_node *root)
{
if(root)
{
inorder(root->left_child);
                printf("%d",root->data.key);
inorder(root->right_child);
}
}
void PostOrderFree(tree_node *root)
{
if(root)
{
PostOrderFree(root->left_child);
PostOrderFree(root->right_child);
free(root);
}
}

Answer 7

好了的，
按你的意思改的，
不过，不建议你这样做。
VC6 下调试 通过，
有任何 问题 ，短消息我。
代码如下：#include <iostream.h> 
#include "stdio.h"
struct bitree 
{ 
int data; 
bitree *lChild,*rChild; 
}; 
int nCountNode = 0; 
bitree *root = NULL;  //maple_zhj:声明为NULLbitree *Creat(int n)
{ 
inline void Insert(bitree **BST,int x); 
int x; 
bitree *BST = NULL; 
for(int i = 1;i <=n;i++) 
{ 
cout <<"第" <<i <<"个:" <<endl; 
cin>>x; 
BST=root; ///maple_zhj:加上这行，用于保存 头指针地址
Insert(&BST,x); ////maple_zhj:  &BST 传入 指针的内存地址
} 
return BST; 
} 
void Insert(bitree **BST,int x)
{ 
if(*BST == NULL) 
{ 
bitree *p = new bitree; 
p->data = x; 
p->lChild = NULL; 
p->rChild = NULL; 
*BST = p; 
if(root==NULL) //maple_zhj:如果头指针是空
root = *BST; //则第一次创建的结构体的地址 赋值给 头指针
} 
else if((*BST)->data >= x) //maple_zhj:二级指针 取一次值，变为一级指针，再取 结构体中的Data
{ 
Insert(&((*BST)->lChild),x); //maple_zhj:二级转一级指针，取到左儿子，
//maple_zhj:再将左儿子指针地址 作为参数传入
} 
else 
{ 
Insert(&((*BST)->rChild),x); //maple_zhj:二级转一级指针，取到左儿子，
//maple_zhj:再将左儿子指针地址 作为参数传入
} 
} 
void MidOrder(bitree *BST)
{
if(BST!=NULL)
{
MidOrder(BST->lChild); //maple_zhj: 左递归
cout <<BST->data; //输出
MidOrder(BST->rChild); //maple_zhj: 右递归
}
} void main() 
{ 

cout <<"请输入结点数目:" <<endl; 
cin>>nCountNode; 
cout <<"请输入" <<nCountNode <<"个结点" <<endl; 
root = Creat(nCountNode); 
cout <<"中序遍历:" <<endl; 
MidOrder(root); 
cout <<endl;  getchar();} 

Answer 8

bitree *Creat(int n) //创建二叉排序树,反复调用Insert函数
{
  inline void Insert(bitree *BST, int x);
  int x;
  bitree *BST = NULL;
  for (int i = 1;i <= n;i++) {
    cout < < "第" < < i < < "个:" < < endl;
    cin >> x;
    Insert(&BST, x);
  }
  return BST;
}
//传递指针的指针,在函数里分配的空间才能对外面的指针有效
void Insert(bitree **BST, int x) //插入
{
  if (BST == NULL) {
    bitree *p = new bitree;
    p->data = x;
    p->lChild = NULL;
    p->rChild = NULL;
    *BST = p;
  }
  else if (*BST->data >= x) {
    Insert(*BST->lChild, x);
  }
  else {
    Insert(*BST->rChild, x);
  }
}
-----------------------
如:
void a(int *i){
  i=new int;
  *i=10;
}
int main(){
  int *ii=NULL;
  a(ii);//这里,你不要以为ii以分配了内存,并且数据为10;事实上,ii还是NULL;至于函数a(ii)里面分配的空间,并没释放
}void a(int **i){
  *i=new int;
  **i=10;
}
int main(){
  int *ii=NULL;
  a(&ii);//这样,ii才分配了内存,并且数据为10
}