堆如果用二叉链表表示成二叉树,用递归算法判断是否为堆？求思想求算法

编写一个递归算法，将二叉链表表示的二叉树，判断两个二叉树是否相同的算法~

判断二叉树是否为完全二叉树。完全二叉树的定义是，前n-1层都是满的，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的。以3层二叉树为例，以下情况为完全二叉树：[方法一]这个问题的描述已经提示了解法，采用广度优先遍历，从根节点开始，入队列，如果队列不为空，循环。遇到第一个没有左儿子或者右儿子的节点，设置标志位，如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树。这个方法需要遍历整棵树，复杂度为O(N)，N为节点的总数。//二叉树结点定义typedefstructNode{intdata;structNode*left;structNode*right;}Node;//实现广度遍历需要队列Queuequeue;//第n层最右节点标志boolleftMost=false;boolProcessChild(Node*child){if(child){if(!leftMost){queue.push(child);}else{returnfalse;}}else{leftMost=true;}returntrue;}boolIsCompleteBinaryTree(Node*root){//空树也是完全二叉树if(!root)returntrue;//首先根节点入队列queue.push(root);while(!queue.empty()){Node*node=queue.pop();//处理左节点if(!ProcessChild(node->left))returnfalse;//处理右节点if(!ProcessChild(node->right))returnfalse;}//广度优先遍历完毕，此乃完全二叉树returntrue;}[方法二]根据完全二叉树的定义，左边的深度>=右边的深度。从根节点开始，分别沿着最左最右分支下去，找到最左和最右的深度。如果左边比右边深1，再分别检查以左儿子和右儿子为根的两根树。有点递归的感觉了。[Tobecontinued]

void Main(){BNode node = new BNode(){value = "1",lNode = new BNode(){value = "1-1"},rNode = new BNode(){value = "1-2",lNode = new BNode() {value = "1-2-1",rNode = new BNode() {value = "1-2-1-2"}},rNode = new BNode() {value = "1-2-2"}}};BNode clone = Clone(node); }BNode Clone(BNode source) {Stack stack = new Stack();stack.Push(source);BNode dest = new BNode();Stack stackDest = new Stack();stackDest.Push(dest);while (stack.Count>0) {//复制节点的值BNode s = stack.Peek();BNode d = stackDest.Peek();d.value = s.value;if (s.lNode != null) { //寻找左子树 作为下一个结点stack.Push(s.lNode);d.lNode = new BNode();stackDest.Push(d.lNode);} else if (s.rNode != null) { //没有就找右子树stack.Push(s.rNode);d.rNode = new BNode();stackDest.Push(d.rNode);} else { //全没有 跳转到父结点的右子树while (true) {stack.Pop();stackDest.Pop();if (stack.Count <= 0) break;BNode p = stack.Peek();if (p.rNode == s) { //已经使用过右结点 向上继续回溯s = p;}else if (p.rNode != null) {stack.Push(p.rNode);d = stackDest.Peek();d.rNode = new BNode();stackDest.Push(d.rNode);break;} else s=p;}}}return dest;}// Define other methods and classes hereclass BNode {public object value;public BNode lNode;public BNode rNode;}
算法思想的话就是构建两个栈用于回溯父结点...
其实递归算法隐藏了栈而已... 手动把这个栈构建出来就算成功了...
以上是一段C#代码示例 java代码应该复制粘贴就能用 C或者C++的话把BNode写成指针就可以使用...

堆的判定条件为，对于队中的任意子树其根元素和其左右孩子元素之间的关系需要符合堆的定义，例如大顶堆需要保证根结点的值大于等于其左右孩子的值，小顶堆则反之。
算法如下：
1. 指定一个树的根结点，判断根结点与左孩子以及右孩子的关系是否满足堆的要求。
2. 若不满足则返回不是堆
3. 若满足则递归的遍历左子树和右子树重复1的步骤，直到整个树被遍历完成。
例如判断大顶堆，实现如下：
1. 调用方法heapJudge(&root); //参数为二叉树的根节点
2. heapJudge方法实现如下
bool heapJudge(TreeNode *root)
{
bool bReturnLeft = false;
bool bReturnRight = false;
if (root == null) //为空返回true，说明到此为止依然是符合堆的条件的
{
return true;
}
//左节点的数据大于根结点数据说明不是大顶堆返回false
if ((root->left != null) && (root->data < root->left->data))
{
return false;
}
//右节点的数据大于根结点数据说明不是大顶堆返回false
if ((root->right != null) && (root->data < root->right->data))
{
return false;
}
//遍历左子树
bReturnLeft = heapJudge(root->left);
//遍历右子树
bReturnRight = heapJudge(root->right);
//返回两个子树的结果，其中有一个不符合则说明不是堆
return (bReturnLeft&&bReturnRight);
}

---

湖南省18999874589： 堆如果用二叉链表表示成二叉树,用递归算法判断是否为堆?求思想求算法 - ？
冀航化痰： 堆的判定条件为,对于队中的任意子树其根元素和其左右孩子元素之间的关系需要符合堆的定义,例如大顶堆需要保证根结点的值大于等于其左右孩子的值,小顶堆则反之.算法如下:1. 指定一个树的根结点,判断根结点与左孩子以及右孩子的...

湖南省18999874589： 以二叉链表为存储结构,构造一棵二叉树,用递归算法查找给定结点及其孩子结点、双亲结点(急用) - ？
冀航化痰： 左孩子 全部小于其根节点 右孩子全部大于根结点 所以 4 1 7 1 3 0 80 0 2 0 0 0 0 00代表无 然后中序遍历之:1 1 2 3 4 7 8 符合其定义 OVER

湖南省18999874589： 用二叉链表存储结构表示下图所示二叉树的,并用递归方法输出三种遍历结果.？
冀航化痰： //上机题3,已在VC下调试成功. #include&lt;stdio.h&gt; #include&lt;malloc.h&gt; #define MAXSIZE 30 typedef struct bnode{ char data; struct bnode *lchild,*rchild; }Bnode,*BTree; typedef BTree DataType; typedef struct{ DataType data[MAXSIZE]; ...

湖南省18999874589： 设某二叉树数据元素类型为整型,以二叉链表为存储结构.试编程实现: ⑴ 生成一棵二叉树. ⑵ 用递归算法、 - ？
冀航化痰： 前几天也做了个这样的数据结构作业! 你看看 你能不能用上!#include ＂stdafx.h＂#include ＂stdlib.h＂#include ＂stdio.h＂ typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; ...

湖南省18999874589： 假设二叉树以二叉链表作为存储结构,试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊 - ？
冀航化痰： typedef struct BiTNode {TElemType data;struct BiTNode *lchild ; //左孩子指针 struct BiTNode *rchild;// 右孩子指针 } BiTNode, *BiTree; void CountLeaf (BiTree T, int& count){ if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 ...

湖南省18999874589： 用二叉链表作为存储结构,建立二叉树,对二叉树进行前序、中序、后序遍历,在对建立的二叉树进行中序线索 - ？
冀航化痰： typedef struct{ int item; *BiTree left; *BiTree right; }BiTree; 以上是二叉树的定义.前序:a_view(BiTree* t){ if(t == NULL) return; view(t->item); a_view(left); a_view(right); } 中序:a_view(BiTree* t){ if(t == NULL) return; a_view(left); view(t->item); a_...

湖南省18999874589： 以二叉链表作存储结构,编写二叉树深度的递归算法(c++语言) - ？
冀航化痰： 给你一个完整的例子吧.学习一下#include <stdio.h> #include <malloc.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAX(a,b) (a>b?a:b)typedef char TElemType; typedef int Status;//二叉树的二叉链表存...

湖南省18999874589： 若二叉树采用二叉链表存储结构,试编写中序遍历二叉树的递归算法 - ？
冀航化痰： , int& count) { //递归方法,if ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; CountLeaf( T->lchild, count); // 统计左子树中叶子结点个数 CountLeaf( T->rchild, count); // 统计右子树中叶子结点个数 } }---------- 非递归,就是采用前序/中序/后序遍历所...

湖南省18999874589： 数据结构 计算结点所在层次 - ？
冀航化痰： #include <iostream.h> #include <limits.h> typedef struct tag_node {int data;//数据域struct tag_node *lchild;//左链指针,指向左子女struct tag_node *rchild;//右链指针,指向右子女 }BinTreeNode;int max(int a,int b) {return a>b ? a : b; }int ...

湖南省18999874589： 设一棵二叉树以二叉链表为储存结构,设计一个递归算法将所有结点的左右子树互换 - ？
冀航化痰： //我做了一个程序,可以实现二叉树的左右子树的交换功能,#include<iostream.h>/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型,可以根据需要修改 typedef struct node *pointer; // 定义二叉...