给定一组数划平衡二叉树,结果是否唯一

给定结点数的平衡二叉树的高度是唯一的吗？为什么~

给定结点数的平衡二叉树的高度相来应该是唯一的，平衡嘛，任何一个节点两个子树的高度都相差不过1嘛……平衡二叉树的结点中需要新加一个元素表示它的平衡因子用于旋转平衡，二叉排序树并不需要这玩意儿。

平衡二叉树旋转的结果不是唯一的，具体见下面分析：
插入序列：12, 4, 1, 7, 8, 10, 9, 2, 11, 6, 5
1、先插入12成为根
2、插入4在12的左子树，没有旋转
3、插入1在4的左子树，以4为中心向右单旋转，结果如下：
4
/ \
1 12
4、插入7在12的左子树，没有旋转
5、插入8在7的右子树，以8开始先左后右双旋转，结果如下：
4
/ \
1 8
/ \
7 12
6、插入10在12左子树，以8为中心开始向左单旋转，结果如下：
8
/ \
4 12
/ \ /
1 7 10
7、插入9在10 的左子树，以10为中心向右单旋转，结果如下：
8
/ \
4 10
/ \ / \
1 7 9 12
8、插入2在1的右子树，没有旋转
9、插入11在12 的左子树，没有旋转
10、插入6在7的左子树，没有旋转
11、插入5在6的左子树，以6为中心向右单旋转，结果如下：
8
/ \
4 10
/ \ / \
1 6 9 12
\ / \ /
2 5 7 11
平衡二叉树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法)，且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树，反之则不一定。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。

单独的某个输入关键字序列如果没有删除，则自然结果唯一
如果没有限定关键字集合的次序，则结果不唯一，比如1、2、3、4
按1, 2, 3, 4输入次序构建的则右子树高度为2，根为2
按4, 3, 2, 1输入次序构建的则左子树高度为2，根为3

---

盐田区19418234909： 给定结点数的平衡二叉树的高度是唯一的吗?为什么 - ？
竹廖狗皮： 给定结点数的平衡二叉树的高度相来应该是唯一的,平衡嘛,任何一个节点两个子树的高度都相差不过1嘛……平衡二叉树的结点中需要新加一个元素表示它的平衡因子用于旋转平衡,二叉排序树并不需要这玩意儿.

盐田区19418234909： 平衡二叉树的判定 - ？
竹廖狗皮： 先根据结果建立一个相应的二叉树..然后用下面的函数应该可以了!!!int depth_bt(struct tree *t) /*求二叉树深度*/ { if(t==NULL) return 0; return 1+max(depth_bt(t->lchild),depth_bt(t->rchild)); } int balance(struct tree *t) /*递归[判断是不是平衡二叉树*...

盐田区19418234909： 给定一组整数,要求利用数组把这组数保存起来,再利用指针实现对数组中的数循环移动.假定共有n个整数,则要使前面各数顺序向后移m个位置,并使最后m各数变为最前面的m各数. - ？
竹廖狗皮： 这题目发的....格式乱啊,OJ的吧. #include<stdio.h> #include<stdlib.h> main() { int n,m; int *a; int i,j,t; scanf(＂%d%d＂, &n, &m); a = (int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf(＂%d＂, &a[i]); for(i=0;i<m;i++){//r_shift t = a[n-1]; for(j=n-1;j...

盐田区19418234909： 试写一个判别给定二叉树是否为二叉排序树的程序! - ？
竹廖狗皮： static boolean IsSearchTree(Bitree *t){ if(!t) //空二叉树情况 return true; else if(!(t.lchild)&&!(t.rchild)) //左右子树都...

盐田区19418234909： 试写一个判别给定二叉树是否为二叉排序树的程序! - ？
竹廖狗皮： 给你一个测试代码. vc下通过.#include #include struct node { node(int i):data(i),left(null),right(null){} int data; node *left; //左孩子结点 node *right; //右孩子结点 void inorder(node *root) //中序遍历,符合升序输出 { if(root!=null) { inorder(root->left...

盐田区19418234909： 什么是平衡二叉树呢,给定二叉树根节点root, 编程判断一个二叉树是否为平衡二叉树 - ？
竹廖狗皮： 平衡二叉树 :首先要求是一棵二叉排序树,然后要求每个结点的平衡因子(左子树高度减右子树高度)在1,0,-1之间.给定二叉树根节点root, 编程判断一个二叉树是否为平衡二叉树 算法思路:按照某种遍历规则遍历二叉树,在遍历的过程中,检查根是不是大于左子树(不空时)的根而且小于右子树(不空时)的根,并计算左右子树高度之差是在在1,0,-1之间.如果所有结点都满足这两条件则为平衡二叉树

盐田区19418234909： C语言,给定一组值,建立一棵二叉树,求二叉树的数深 - ？
竹廖狗皮： #include <stdio.h> #include <stdlib.h>struct BiTreeNode { char data; struct BiTreeNode *rchild; struct BiTreeNode *lchild; };void Create(struct BiTreeNode *&Tnode) //先序创建2叉链表 { char ch; scanf(＂%c＂,&ch); if(ch=='#') { Tnode=NULL; } else {...

盐田区19418234909： 给定一组关键字K={4,5,2,3,6,1},试按二叉排序树生成规则画出这棵二叉排序树,并说明用这组关键字以不同的次序输入后建立起来的二叉排序树是否相同?当以中序遍历这些二叉排序树时,其遍历序列是否相 - ？
竹廖狗皮： 4,5,2和3,6,1

盐田区19418234909： 设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树 - ？
竹廖狗皮： 设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树 夫曼树的构造: (1)根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空; (2)在F中...

盐田区19418234909： 简述哈夫曼树的性质.？
竹廖狗皮： 哈 夫 曼 树 2.9 二叉树的应用2.9.1 哈夫曼树及应用 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用.结点之间的路径长度:从一个结点到另一...