知道的大牛告诉我吧！加30！

不是二叉数是二叉树

定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树

定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。

二叉树的定义

1.二叉树的递归定义
    　二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

2．二叉树的五种基本形态
    　二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
    二叉树的五种基本形态如下图所示。
　
3．二叉树不是树的特例
（1）二叉树与无序树不同
     二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
  　二叉树并非是树的特殊情形，它们是两种不同的数据结构。

（2）二叉树与度数为2的有序树不同
    在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。
  【例】下图中(a)和(b)是两棵不同的二叉树，它们同右图中的普通树(作为有序树或无序树)很相似，但却不等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。
　　　　　　
  　二叉树并非是树的特殊情形，它们是两种不同的数据结构。

二叉树简单来说就是一棵最多有两个孩子的树，孩子间有左右之分

1. 编写一个判断给定二叉树是不是完全二叉树的函数？
2。编写一个判断给定二叉树是不是一个平衡二叉树的函数？
3。实现将一个二叉树的各个接点的左右子树都交换的函数？

--------------------------------------------------------------------------------

3、
template <typename _Ty>
struct BiTNode
{
BiTNode * left, right;
_Ty data;
BiTNode(const _Ty& _data):left(0), right(0), data(_data){}
void Swap()
{
left->Swap();
right->Swap();
BiTNode * tmp = left;
left = right;
right = tmp;
}
};
前面两个，俺找到定义了再说^_^

--------------------------------------------------------------------------------

如果说完全二叉树是指两个节点都存在的，那么简单：
template <typename _Ty>
struct BiTNode
{
BiTNode * left, right;
_Ty data;
BiTNode(const _Ty& _data):left(0), right(0), data(_data){}
bool Complete()
{
return (left && right) ? true : false;
}
};

--------------------------------------------------------------------------------

如果下面的东西可以作为“完全二叉树”定义
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
那么。。。
等等，这里有个完全二叉树的判定：
http://www.16167.com/bbs/printthread.php?threadid=1546

--------------------------------------------------------------------------------

晕，不让连续恢复。俺完美废人屹立不倒！

--------------------------------------------------------------------------------

上面那个蝎子还是我，嘿嘿。
懂行的帮忙看看下面的代码是不是够判断。
template <typename _Ty>
struct BiTNode
{
BiTNode * left, right;
_Ty data;
BiTNode(const _Ty& _data):left(0), right(0), data(_data){}
bool Complete()
{
if (left)
return left->Complete();
else
return right ? false : true;
}
};
另外实在没找到“平衡二叉树”的定义。。。俺不是学这个的，手里没有书。

--------------------------------------------------------------------------------

楼主要是给分，不用给天蝎，给俺就 OK 了，哈哈

--------------------------------------------------------------------------------

平衡二叉树:每个节点的左 右子树高度相差不超过1
判断给定二叉树是不是一个平衡二叉树的函数:
bool decide(Node* head) {
Node *stack[MAXNUM], *p= head, *bp= p;
int top= 0;
bool retV= true;
while (p|| top) {
if (p) {
if (math.abs(p->left->getHeight()- p->right->getHeight())> 1) {
retV= false; break;
} //getHeight()略
stack[++top]= p;
bp= p;
p= p->left;
}
else { //p=NULL
p= stack[top--];
bp= p;
p= p->right;
}
}
return retV;
}

--------------------------------------------------------------------------------

to Wolf0403(完美废人):
你的方法还是解决不了
我有一个方法，不过不是很好，请高人指正
BiTNode　的定义就省了
bool BiTNode::Complete()
{
queue<BiTNode *> nodequeue;
BiTNode * p;
nodequeue.push(this);
while(!nodequeue.empty())
{
p=nodequeue.pop();
if(p->left==NULL || p->right==NULL) break;
nodequeue.push(p->left);
nodequeue.push(p->right);
}
if(!nodequeue.empty()) return false;
if(p->left==NULL && p->right!=NULL) return false;
return true;
}

--------------------------------------------------------------------------------

谢谢！
我再看看，测试以下！

--------------------------------------------------------------------------------

ding !!!

--------------------------------------------------------------------------------

光顶干什么？说结果啊

二叉树：1.二叉树的递归定义
    　二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

2．二叉树的五种基本形态
    　二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
    二叉树的五种基本形态如下图所示。
　
3．二叉树不是树的特例
（1）二叉树与无序树不同
     二叉树中，每个结点最多只能有两棵子树，并且有左右之分。
  　二叉树并非是树的特殊情形，它们是两种不同的数据结构。

（2）二叉树与度数为2的有序树不同
    在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。