精华内容
下载资源
问答
  • if(root==null) {//空树高度为0 return 0; } int leftDepth=maxDepth1(root.left);//递归计算左子树高度 int rightDepth=maxDepth1(root.right);//递归计算右子树高度 return Math.max(leftDepth, ...

    一、二叉树最大深度(高度)

    //求二叉树最大深度/高度(DFS)
    	public int maxDepth1(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
    		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
    		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
    	}
    
    //求二叉树最大深度/高度(BFS)
    	public int maxDepth2(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		Queue<Node> queue=new LinkedList<>();
    		queue.offer(root);//将根结点入队列
    		int res=0;//保存二叉树的高度
    		while(!queue.isEmpty()) {//遍历每层
    			int size=queue.size();//当前层的结点数量
    			while(size>0) {
    				Node temp=queue.poll();
    				if(temp.left!=null) {//当前结点左节点存在入队列
    					queue.offer(temp.left);
    				}
    				if(temp.right!=null) {//当前结点右节点存在入队列
    					queue.offer(temp.right);
    				}
    				size--;
    			}
    			res++;//每遍历完一层,将层数加一
    		}
    		return res;
    	}
    

    二、二叉树结点个数

    //求二叉树的结点数(方法一)
    	public int nodeCount1(Node root) {
    		if(root==null) {
    			return 0;
    		}
    		return nodeCount1(root.left)+nodeCount1(root.right)+1;
    	}
    	
    //求二叉树的结点数(方法二)
    	public static int count2 = 0;// 记录结点个数
    	public int nodeCount2(Node root) {
    		//int res = 0;// 记录结点个数
    		if (root == null) {
    			return 0;
    		}
    		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
    		nodeCount2(root.left);
    		nodeCount2(root.right);
    		return count2;
    	}
    	
    // 求二叉树的结点数(方法三)
    	public int nodeCount3(Node root) {
    		int res = 0;// 记录结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			Node temp = stack.pop();
    			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
    			if (temp.left != null) {
    				stack.push(temp.left);
    			}
    			if (temp.right != null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    

    三、二叉树叶子结点个数

    //求二叉树的叶子数(方法一)
    	public int leafCount1(Node root){
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
    			return 1;
    		}
    		return leafCount1(root.left)+leafCount1(root.right);
    	}
    	
    //求二叉树的叶子数(方法二)
    	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外,否则每次遍历时重新进行函数体时有=又重新将count1置为零,下面的count2同理)
    	public int leafCount2(Node root) {
    		// int res=0;//记录叶子结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
    			count1++;
    		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
    			leafCount2(root.left);
    			leafCount2(root.right);
    		}
    		return count1;
    	}
    	
    //求二叉树的叶子数(方法三)
    	public int leafCount3(Node root) {
    		int res=0;//记录叶子结点的个数
    		if (root == null) {//空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack=new Stack<>();
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			Node temp=stack.pop();
    			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
    				res++;
    			}
    			if(temp.left!=null) {
    				stack.push(temp.left);
    			}
    			if(temp.right!=null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    

    四、二叉树第k层结点个数

    //求第k层结点个数
    	public int kLevelCount(Node root,int k) {
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(k==1) {//k==1即求根节点的个数,直接返回1
    			return 1;
    		}
    		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
    		
    	}
    

    五、完整代码实现

    package fighting;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class BinaryTree {
    	
    	public Node BuildTree() {//构造二叉树
    		Node A=new Node('A');
    		Node B=new Node('B');
            Node C=new Node('C');
            Node D=new Node('D');
            Node E=new Node('E');
            Node F=new Node('F');
            Node G=new Node('G');
            Node H=new Node('H');
            A.left=B;
            A.right=C;
            B.left=D;
            B.right=E;
            C.left=F;
            C.right=G;
            E.right=H;
            return A;
    	}
    	
    	//求二叉树最大深度/高度(DFS)
    	public int maxDepth1(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		int leftDepth=maxDepth1(root.left);//递归计算左子树高度
    		int rightDepth=maxDepth1(root.right);//递归计算右子树高度
    		return Math.max(leftDepth, rightDepth)+1;//取出左右子树最大值再加上根结点高度为1
    	}
    
    	//求二叉树最大深度/高度(BFS)
    	public int maxDepth2(Node root) {
    		if(root==null) {//空树高度为0
    			return 0;
    		}
    		Queue<Node> queue=new LinkedList<>();
    		queue.offer(root);//将根结点入队列
    		int res=0;//保存二叉树的高度
    		while(!queue.isEmpty()) {//遍历每层
    			int size=queue.size();//当前层的结点数量
    			while(size>0) {
    				Node temp=queue.poll();
    				if(temp.left!=null) {//当前结点左节点存在入队列
    					queue.offer(temp.left);
    				}
    				if(temp.right!=null) {//当前结点右节点存在入队列
    					queue.offer(temp.right);
    				}
    				size--;
    			}
    			res++;//每遍历完一层,将层数加一
    		}
    		return res;
    	}
    	
    	//求二叉树的叶子数(方法一)
    	public int leafCount1(Node root){
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(root.left==null&&root.right==null) {//没有左右子树即为叶子结点
    			return 1;
    		}
    		return leafCount1(root.left)+leafCount1(root.right);
    	}
    	
    	//求二叉树的叶子数(方法二)
    	public static int count1 = 0;// 记录叶子结点的个数(该count1定义必须放在函数体外,否则每次遍历时重新进行函数体时有=又重新将count1置为零,下面的count2同理)
    	public int leafCount2(Node root) {
    		// int res=0;//记录叶子结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		if (root.left == null && root.right == null) {// 没有左右子树即为叶子结点将count1加一
    			count1++;
    		} else {// 否则的话就继续遍历,继续找左右孩子均为空的结点
    			leafCount2(root.left);
    			leafCount2(root.right);
    		}
    		return count1;
    	}
    	
    	//求二叉树的叶子数(方法三)
    	public int leafCount3(Node root) {
    		int res=0;//记录叶子结点的个数
    		if (root == null) {//空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack=new Stack<>();
    		stack.push(root);
    		while(!stack.isEmpty()) {
    			Node temp=stack.pop();
    			if (temp.left == null && temp.right == null) {//没有左右子树即为叶子结点将res加一
    				res++;
    			}
    			if(temp.left!=null) {
    				stack.push(temp.left);
    			}
    			if(temp.right!=null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    	
    	
    	//求二叉树的结点数(方法一)
    	public int nodeCount1(Node root) {
    		if(root==null) {
    			return 0;
    		}
    		return nodeCount1(root.left)+nodeCount1(root.right)+1;
    	}
    	
    	//求二叉树的结点数(方法二)
    	public static int count2 = 0;// 记录结点个数
    	public int nodeCount2(Node root) {
    		//int res = 0;// 记录结点个数
    		if (root == null) {
    			return 0;
    		}
    		count2++;//在遍历时所有的结点都会访问到,每访问一个结点就将count2加一
    		nodeCount2(root.left);
    		nodeCount2(root.right);
    		return count2;
    	}
    	
    	// 求二叉树的结点数(方法三)
    	public int nodeCount3(Node root) {
    		int res = 0;// 记录结点的个数
    		if (root == null) {// 空树直接返回0
    			return 0;
    		}
    		Stack<Node> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()) {
    			Node temp = stack.pop();
    			res++;// 在遍历时所有的结点都会访问到,每访问一个结点就将res加一
    			if (temp.left != null) {
    				stack.push(temp.left);
    			}
    			if (temp.right != null) {
    				stack.push(temp.right);
    			}
    		}
    		return res;
    	}
    
    	//求第k层结点个数
    	public int kLevelCount(Node root,int k) {
    		if(root==null) {//空树直接返回0
    			return 0;
    		}
    		if(k==1) {//k==1即求根节点的个数,直接返回1
    			return 1;
    		}
    		return kLevelCount(root.left,k-1)+kLevelCount(root.right,k-1);//k层节点的个数=根节点左子树的k-1层节点个数+根节点右子树的k-1层节点个数
    		
    	}
    	public static void main(String[] args) {
    		BinaryTree binaryTree=new BinaryTree();
    		Node root=binaryTree.BuildTree();
    		System.out.println("二叉树的最大高度为(DFS):"+binaryTree.maxDepth1(root));//DFS求二叉树高度
    		System.out.println("二叉树的最大高度为(BFS):"+binaryTree.maxDepth2(root));//BFS求二叉树高度
    		System.out.println("二叉树结点的个数为(方法一):"+binaryTree.nodeCount1(root));
    		System.out.println("二叉树结点的个数为(方法二):"+binaryTree.nodeCount2(root));
    		System.out.println("二叉树结点的个数为(方法三):"+binaryTree.nodeCount3(root));
    		System.out.println("二叉树叶子结点的个数为(方法一):"+binaryTree.leafCount1(root));
    		System.out.println("二叉树叶子结点的个数为(方法二):"+binaryTree.leafCount2(root));
    		System.out.println("二叉树叶子结点的个数为(方法三):"+binaryTree.leafCount3(root));
    		System.out.printf("二叉树第%d层结点个数数为:%d",3,binaryTree.kLevelCount(root,3));
    	}
    }
    
    class Node{
    	char val;
    	Node left;
    	Node right;
    	public Node(char val) {//Node的构造函数
    		this.val=val;
    	}
    }
    

    运行结果:

    二叉树的最大高度为(DFS):4
    二叉树的最大高度为(BFS):4
    二叉树结点的个数为(方法一)8
    二叉树结点的个数为(方法二)8
    二叉树结点的个数为(方法三)8
    二叉树叶子结点的个数为(方法一)4
    二叉树叶子结点的个数为(方法二)4
    二叉树叶子结点的个数为(方法三)4
    二叉树第3层结点个数数为:4
    

    该实例的二叉树图如下所示:
    在这里插入图片描述

    展开全文
  • 设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为(),最小结点数为() 答案是(2^k+1)-1和k+1。我做出来的是(2^k)-1和k 求帮忙算一下哪个是对的,谢谢了
  • 二叉树的性质

    2020-05-28 17:04:40
    (2) 深度(高度为k的二叉树至多有2k-1(k>=1)个结点 (3) 对任意一颗二叉树BT,如果其叶子结点数为n0,度为2的结点数为n2,,则n0=n2=+1 以上三个性质是一般二叉树都具有的,为研究二叉树的其他性质,下面...

    (1) 在二叉树的第i层上至多有2i-1个结点(i>=1)
    (2) 深度(高度)为k的二叉树至多有2k-1(k>=1)个结点
    (3) 对任意一颗二叉树BT,如果其叶子结点个数为n0,度为2的结点个数为n2,,则n0=n2=+1
    以上三个性质是一般二叉树都具有的,为研究二叉树的其他性质,下面介绍两种特殊形式的二叉树,即完全二叉树和满二叉树
    1, 满二叉树指深度为k切有2k-1个结点的二叉树,称为满二叉树,特点是每层上的节点数都是最大节点数
    2, 完全二叉树是指深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树,特点是叶子结点只可能在层次最大的两层上出现,对任一结点,若其右分支下子孙的最大层次为L,则其左下分支子孙的最大层次必为L或L+1
    (4) 具有n个结点的完全二叉树的深度为:[log2n]+1
    (5) 如果对一颗有n个结点的完全二叉树的结点按层序编号,其中根结点为第一层,按层次从上到下,同层从左到右,则对任意编号为i(1<=i<=n)的结点有以下性质:
    1、 如果i=1,则结点i是二叉树的根,无双亲;如果i>1,则其双亲是[i/2]
    2、 如果2i>n,则结点i无左孩子,即该结为叶子结点;如果2i<=n,则其左孩子是2i
    3、 如果2i+1>n,则结点i无右 孩子;如果2i+1<=n,则其左孩子是2i+1

    展开全文
  • 二叉树的各种操作

    2019-09-27 12:09:31
    二叉树的操作实现 这里的二叉树全部都是用二叉链实现...求二叉树的高度 求二叉树元素的最大值 求二叉树结点 输出所有的叶子结点 求二叉树中结点值x的层 求二叉树第k层的结点 求第k层上叶子结点的个...

    二叉树的操作实现

    这里的二叉树全部都是用二叉链实现,算法都是一些简单的递归

    • 根据二叉树括号表示法字符串str生成对应的二叉树链式存储结构
    • 输出二叉树
    • 先序遍历、中序遍历、后序遍历
    • 销毁二叉树
    • 查找值为x的结点
    • 求二叉树的高度
    • 求二叉树元素的最大值
    • 求二叉树结点个数
    • 输出所有的叶子结点
    • 求二叉树中结点值x的层数
    • 求二叉树第k层的结点个数
    • 求第k层上叶子结点的个数
    • 求二叉树中所有单分支结点个数
    • 判断两棵树是否相似
    • 输出值为x的结点的所有祖先
    • 输出值为x的结点的所有子孙结点
    • 判断值为x的结点和值为y的结点是否为兄弟
    • 将二叉树b1复制到二叉树b2
    • 将二叉树的所有左右子树进行交换
    • 判断一颗二叉树是否是完全二叉树
      1 #include<stdio.h>
      2 #include<stdlib.h>
      3 
      4 typedef char ElemType;
      5 typedef struct node 
      6 {
      7     ElemType data;
      8     struct node *lchild;
      9     struct node *rchild;
     10 }BTNode;
     11 
     12 const int MaxSize = 100 + 10;    
     13 
     14 //根据二叉树括号表示法字符串str生成对应的二叉树链式存储结构
     15 void CreateBTree(BTNode * &b, char *str)
     16 {
     17     BTNode *St[MaxSize], *p;        //St作为顺序栈
     18     int top = -1, k,j = 0;            //top作为栈顶指针
     19     char ch;
     20     b = NULL;
     21     ch = str[j];
     22     while (ch != '\0')
     23     {
     24         switch (ch)
     25         {
     26         case '(':top++; St[top] = p; k = 1; break;        //开始处理左孩子结点
     27         case ')':top--; break;                            //栈顶结点的子树处理完毕
     28         case ',':k = 2; break;                            //开始处理右孩子结点
     29         default:
     30             p = (BTNode *)malloc(sizeof(BTNode));        //创建一个结点,由p指向它
     31             p->data = ch;
     32             p->lchild = p->rchild = NULL;                
     33             if (b == NULL)  b = p;                        //若尚未创建根节点
     34             else
     35             {
     36                 switch (k)
     37                 {
     38                 case 1:St[top]->lchild = p; break;
     39                 case 2:St[top]->rchild = p; break;
     40                 }
     41             }
     42         }
     43         j++;                                            //继续扫描str
     44         ch = str[j];
     45     }
     46 }
     47 
     48 //输出二叉树DispBTree(b)
     49 void DispBTree(BTNode *b)
     50 {
     51     if (b != NULL)
     52     {
     53         printf("%c", b->data);
     54         if (b->lchild != NULL || b->rchild != NULL)
     55         {
     56             printf("(");                            //有孩子结点时才输出“(”
     57             DispBTree(b->lchild);                    //递归处理左子树
     58             if (b->rchild != NULL)  printf(",");    //有右孩子结点时才输出“,”
     59             DispBTree(b->rchild);                    //递归处理右子树
     60             printf(")");                            //有孩子结点时才输出
     61         }
     62     }
     63 }
     64 
     65 //先序遍历
     66 void PreOrder(BTNode * b)
     67 {
     68     if (b != NULL)
     69     {
     70         printf("%c", b->data);
     71         PreOrder(b->lchild);
     72         PreOrder(b->rchild);
     73     }
     74 }
     75 //中序遍历
     76 void InOrder(BTNode * b)
     77 {
     78     if (b != NULL)
     79     {
     80         InOrder(b->lchild);
     81         printf("%c", b->data);
     82         InOrder(b->rchild);
     83     }
     84 }
     85 //后序遍历
     86 void PostOrder(BTNode * b)
     87 {
     88     if (b != NULL)
     89     {
     90         InOrder(b->lchild);
     91         InOrder(b->rchild);
     92         printf("%c", b->data);
     93     }
     94 }
     95 
     96 //销毁二叉树
     97 void DestroyBTree(BTNode *& b)
     98 {
     99     if (b != NULL)
    100     {
    101         DestroyBTree(b->lchild);
    102         DestroyBTree(b->rchild);
    103         free(b);
    104     }
    105 }
    106 
    107 
    108 //查找值为x的结点
    109 BTNode *FindNode(BTNode *b, ElemType x)
    110 {
    111     BTNode *p;
    112     if (b == NULL)  return NULL;
    113     else if (b->data == x)  return b;
    114     else
    115     {
    116         p = FindNode(b->lchild, x);
    117         if (p != NULL)  return p;
    118         else  return FindNode(b->rchild, x);
    119     }
    120 }
    121 
    122 //求二叉树的高度
    123 int BTHeight(BTNode *b)
    124 {
    125     int lchildh, rchildh;
    126     if (b == NULL)  return 0;
    127     else
    128     {
    129         lchildh = BTHeight(b->lchild);
    130         rchildh = BTHeight(b->rchild);
    131         return lchildh > rchildh ? (lchildh + 1) : (rchildh + 1);
    132     }
    133 }
    134 
    135 //求二叉树元素的最大值
    136 int BTMax(BTNode *b)
    137 {
    138     if (b == NULL)  return 0;
    139     else
    140     {
    141         int m1 = BTMax(b->lchild);
    142         int m2 = BTMax(b->rchild);
    143         int m3 = b->data;
    144         if (m1 > m2)  return m1 > m3 ? m1 : m3;
    145         else  return m2 > m3 ? m2 : m3;
    146     }
    147 }
    148 
    149 //求二叉树结点个数
    150 int BTNum(BTNode * b)
    151 {
    152     if (b == NULL)  return 0;
    153     else  return BTNum(b->lchild) + BTNum(b->rchild) + 1;
    154 }
    155 
    156 //输出所有的叶子结点
    157 void DispLeaf(BTNode *b)
    158 {
    159     if (b != NULL)
    160     {
    161         if (b->lchild == NULL && b->rchild == NULL)
    162             printf("%c", b->data);
    163         DispLeaf(b->lchild);
    164         DispLeaf(b->rchild);
    165     }
    166 }
    167 
    168 //求二叉树中结点值x的层数
    169 //返回0表示未找到,h初始置为0
    170 int BTLevel(BTNode *b, ElemType x, int h)
    171 {
    172     int level;
    173     if (b == NULL)  return 0;
    174     else if (b->data == x)  return h;
    175     else
    176     {
    177         level = BTLevel(b->lchild, x, h + 1);
    178         if (level != 0)  return level;
    179         else  return BTLevel(b->rchild, x, h + 1);
    180     }
    181 }
    182 
    183 //求二叉树第k层的结点个数
    184 //当前层数h初始置为0
    185 int BTKlevel(BTNode *b,int h, int k)
    186 {
    187     if (b == NULL)  return 0;
    188     else
    189     {
    190         if (h == k)  return 1;
    191         if (h < k)   return (BTKlevel(b->lchild, h + 1, k) + BTKlevel(b->rchild,h + 1,k));
    192     }
    193 }
    194 
    195 //求第k层上叶子结点的个数
    196 int BTKlevelLeaf(BTNode *b, int h, int k)
    197 {
    198     if (b == NULL)  return 0;
    199     else
    200     {
    201         if (h == k && b->lchild == NULL && b->rchild == NULL)  return 1;
    202         if (h < k)   return (BTKlevelLeaf(b->lchild, h + 1, k) + BTKlevelLeaf(b->rchild, h + 1, k));
    203     }
    204     return 0;                //其它情况返回0
    205 }
    206 
    207 //求二叉树中所有单分支结点个数
    208 int BTSingleSonNode(BTNode * b)
    209 {
    210     if (b == NULL)  return 0;
    211     else if ((b->lchild == NULL && b->rchild != NULL) || (b->lchild != NULL && b->rchild == NULL))  return BTSingleSonNode(b->lchild) + BTSingleSonNode(b->rchild) + 1;
    212     else  return BTSingleSonNode(b->lchild) + BTSingleSonNode(b->rchild);
    213 }
    214 
    215 //判断两棵树是否相似
    216 //形态一样,结点值可以不同
    217 bool BTLike(BTNode *b1, BTNode *b2)
    218 {
    219     bool flag1, flag2;
    220     if (b1 == NULL && b2 == NULL)  return true;
    221     else if (b1 == NULL || b2 == NULL)  return false;
    222     else
    223     {
    224         flag1 = BTLike(b1->lchild, b2->lchild);
    225         flag2 = BTLike(b1->rchild, b2->rchild);
    226         return flag1 && flag2;
    227     }
    228 }
    229 
    230 //输出值为x的结点的所有祖先
    231 //f(b,x)=true表示以结点b为根节点的二叉树包含x
    232 bool BTAncestor(BTNode *b, ElemType x)
    233 {
    234     if (b == NULL)  return false;
    235     else if ((b->lchild != NULL && b->lchild->data == x) || (b->rchild != NULL && b->rchild->data == x))
    236     {
    237         printf("%c", b->data);
    238         return true;
    239     }
    240     else
    241     {
    242         int flag1 = BTAncestor(b->lchild, x);
    243         int flag2 = BTAncestor(b->rchild, x);        //考虑到可能存在多个x,分开写
    244         if(flag1 || flag2)  printf("%c", b->data);
    245         return true;
    246     }
    247     return false;
    248 }
    249 
    250 //输出值为x的结点的所有子孙结点
    251 void BTChild(BTNode *b, ElemType x)
    252 {
    253     if (b != NULL)
    254     {
    255         if (b->data == x)
    256         {
    257             PreOrder(b->lchild);
    258             PreOrder(b->rchild);
    259         }
    260         else
    261         {
    262             BTChild(b->lchild,x);
    263             BTChild(b->rchild,x);
    264         }
    265     }
    266 }
    267 
    268 //判断值为x的结点和值为y的结点是否为兄弟
    269 bool BTBrother(BTNode *b, ElemType x, ElemType y)
    270 {
    271     if (b == NULL)  return false;
    272     else
    273     {
    274         if (b->lchild != NULL && b->rchild != NULL)
    275             if ((b->lchild->data == x && b->rchild->data == y) || (b->lchild->data == y && b->rchild->data == x))
    276                 return true;
    277         return BTBrother(b->lchild, x, y) || BTBrother(b->rchild, x, y);
    278     }
    279 }
    280 
    281 //将二叉树b1复制到二叉树b2
    282 void BTCopy(BTNode *b1, BTNode * &b2)
    283 {
    284     if (b1 == NULL)      b2 = NULL;
    285     else
    286     {
    287         b2 = (BTNode *)malloc(sizeof(BTNode));
    288         b2->data = b1->data;
    289         BTCopy(b1->lchild, b2->lchild);
    290         BTCopy(b1->rchild, b2->rchild);
    291     }
    292 }
    293 
    294 //将二叉树的所有左右子树进行交换
    295 void BTSwap(BTNode *b1, BTNode * &b2)
    296 {
    297     if (b1 == NULL)  b2 = NULL;
    298     else
    299     {
    300         b2 = (BTNode *)malloc(sizeof(BTNode));
    301         b2->data = b1->data;
    302         BTSwap(b1->rchild, b2->lchild);
    303         BTSwap(b1->lchild, b2->rchild);
    304     }
    305 }
    306 
    307 
    308 //判断一颗二叉树是否是完全二叉树
    309 //两条规则,违反任意一条均不是完全二叉树
    310 //1、某结点无左孩子,则一定没有右孩子
    311 //2、若某结点缺少左孩子或右孩子,则其所有后继(层次遍历的后继)一定无孩子
    312 bool BTComp(BTNode *b)
    313 {
    314     BTNode *Qu[MaxSize], *p;            //定义一个队列用于层次遍历
    315     int front = 0, rear = 0;            //环形队列的队头和队尾指针
    316     bool cm = true;                        //cm为真表示二叉树为完全二叉树
    317     bool flag = true;                    //flag为真表示所有结点到目前为止都有左右孩子
    318     if (b == NULL)  return true;
    319     rear++;
    320     Qu[rear] = b;                        //根结点入队
    321     while (front != rear)                //队列不为空
    322     {
    323         front = (front + 1) % MaxSize;
    324         p = Qu[front];                    //队首出队
    325         if (p->lchild == NULL)  
    326         {
    327             flag = false;
    328             if (p->rchild != NULL)        //没有左孩子,则一定没有右孩子
    329             {
    330                 cm = false;
    331                 break;
    332             }
    333         }
    334         else
    335         {
    336             if ((!flag))                //出现空缺少左孩子或右孩子之后,所有的结点均无孩子
    337             {
    338                 cm = false;
    339                 break;
    340             }
    341             rear = (rear + 1) % MaxSize;
    342             Qu[rear] = p->lchild;            //左孩子入队
    343             if (p->rchild == NULL)  flag = false;
    344             else
    345             {
    346                 rear = (rear + 1) % MaxSize;
    347                 Qu[rear] = p->rchild;        //右孩子入队
    348             }
    349         }
    350     }
    351     return cm;
    352 }
    353 
    354 int main()
    355 {
    356     BTNode *b1, *b2;
    357     char str1[] = "A(B(D(,G)),C(E(,G),F))";
    358     char str2[] = "A(B(D,D),C(E))";
    359     CreateBTree(b2,str2);
    360     printf("%d\n", BTComp(b2));
    361     return 0;
    362 }

     

     

    参考资料:《数据结构教程》李春葆等

    转载于:https://www.cnblogs.com/lfri/p/10256069.html

    展开全文
  • 二叉树 性质1:(高度/最大深度) 含有n个结点的二叉,其最大高度为n,最小高度为math.ceil(log2(n+1)) ...深度为k的二叉树,最多有2^k-1个结点 完全二叉树 性质1:(深度) 具有n个节点的完全二...

    二叉树

    性质1:(高度/最大深度)
    含有n个结点的二叉数,其最大高度为n,最小高度为math.ceil(log2(n+1))
    性质2:(度数为2和叶子结点关系)
    度数为2的结点=叶子结点数-1
    性质3:(单层最多结点)
    二叉树的第i层最多有2^(i-1)个结点(i>=1)
    性质4:(所有层最多结点)
    深度为k的二叉树,最多有2^k-1个结点
    

    完全二叉树

    性质1:(深度)
    具有n个节点的完全二叉树的深度为math.ceil(math.log2(n+1))
    性质2:(孩子结点)
    	前提:给完全二叉树从左至右依次编号1~n
    	.如果2i>n,则结点没有左孩子(叶子结点)
    	.如果2i+1>n,则结点没有右孩子
    	.结点i的左孩子编号为2i,右孩子编号为2i+1
    
    展开全文
  • 二叉树

    2018-09-04 16:43:47
    完全二叉树:高度为k的二叉树,除第k层外,其他层的结点最大,且第k层的结点都集中在该层最左边的位置上; 具有n个结点的完全二叉树,其深度为[log2 n]+1;满二叉树的深度为log2 (n+1)。 2、遍历二叉树 ...
  • 满二叉树是除了叶子结点外其他所有结点的度都为2,也就是说都有两个子树,若一颗满二叉树的高度为k,则它有2的k-1次方个结点 平衡二叉树:又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,...
  • 高度为k并且有2K+1-1个结点的二叉树 在满二叉树中,每层结点都达到最大数,即每层结点都是满的,因此称为满二叉树。 完全二叉树: 若在一颗满二叉树中,在最下层从最右侧起去掉相邻的若干叶子节点,得到的二叉树即...
  • 满二叉树:高度为h,结点数为2*h-1。 完全二叉树:高度为h,1~h-1层结点数满,第h层从右到左缺若干结点。若有N个结点,高度为log2N。 最小堆:在完全二叉树的基础上,所有的父结点都比子结点小。 最大堆:在完全...
  • 层次:节点的层次(level)从根开始定义起,根为第一层,根的孩子为第二层。 深度:树中结点的最大层次称为树的深度(depth)或高度。...2.深度为k的二叉树至多有(2^k)-1个结点。(等比数列公式) 3.对任何一课
  • 数据结构考试题型及说明 补考试卷闭卷 单项选择题每题2分共30分 1设根结点的高度为0则高度为k的二叉树的最大结点数为 A) k B) 2k-1C) 2k+1 -1 D) 2k-1 2任何一棵二叉树上都有 空链域 A. 不确定 B.2n+1 C. n+1 D. n 3...
  • 完全二叉树: 若设二叉树的深度h,除第h 层外,其它各层(1~h-1) 的结点数都达到最大,第h 层所有的结点都连续集中在最左边,这就是完全二叉树二叉树的基本操作:构造二叉树,前序遍历,中序遍历,后序遍历,求...
  • 深度为k的二叉树至多有2^k-1个结点(k>0) 对于任意一棵二叉树,如果其叶结点为N0,而度数为2的结点总数为N2,则N0=N2+1 具有n个结点的完全二叉树的深度必为 log2(n+1) 对完全二叉树,若从上至下、从左只右编号,...
  • 二叉树创建与遍历

    2017-10-16 19:45:37
    二叉树的创建定义:二叉树是每个节点最多有两个子树的树...2.完全二叉树:假设二叉树的高度为K,除第K层外,其他各层的节点都达到最大。也就是第一层到第K-1层为一个满二叉树。第K层有叶子节点,并且叶子结点
  • 【3】设根结点的高度为0,则高度为k的二叉树的最大结点数为2^(k+1)-1 【4】采用邻接表存储的图的深度优先遍历算法类似于二叉树的先序遍历。 【5】判定一个有向图是否存在回路,可以用DFS算法。 【6】哈夫曼树的根...
  • 二叉树介绍

    2011-07-26 23:10:34
    对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则no...完全二叉树:若设二叉树的高度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大,第h层从右向左连续缺若干结点。平衡二叉树:左右树都是平
  • 树和二叉树

    2019-11-16 20:48:31
    结点所在层数:根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有结点的最大层数,也称高度。 层序编号:将树中结点按照从上层到下层、同层从左到右的次序依次给...
  • 设只包含根结点的二叉树高度为0,则高度为k的二叉树最小结点数为k+1。 T 举例子即可证明正确 1-3 关于树和二叉树 二叉树是度为 2 的树。 F 二叉树的度是指树中所有结点的度数的最大值。二叉树的度小于等于2,因为...
  • JS–树、二叉树 一、树结构和特点 ...一个二叉树第 i 层的最大结点数为:2^(i-1), i >= 1; 深度为k的二叉树有最大结点总数为: 2^k - 1, k >= 1; 对任何非空二叉树 T,若n0表示叶结点的个数、n2是度
  • 第五章树和二叉树

    2019-12-02 19:44:24
    结点所在层数:根结点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有结点的最大层数,也称高度。 层序编号:将树中结点按照从上层到下层、同层从左到右的次序依次给他们...
  • 一个二叉树的数为k,节点总数为2^(k-1),则为满二叉树。 完全二叉树是由满二叉树而引出来的,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大(即1~h-1层为一个满二叉树),第 h 层...
  • 1满二叉树 ...也就是说,如果一个二叉树的数为K,且结点总数是(2^k) -1 ,则它就是满二叉树。 2 分析 我们知道满二叉树是三角形的比如如下,最后一层任何一个节点的高度都是高度。 ...
  • 最近复习一遍数据结构与算法,做一些笔记,大家可以一起复习。 一、树的一些容易混淆的定义: 结点层:根结点的层定义为1;根的孩子为第二层结点,...也就是说,如果一个二叉树的数为K,且结点总数是(2^k) -1 ,...
  • (2)结点的度:树中一个结点的孩子个称为该结点的度,树中结点的最大度数称为树的度。 (3)分支结点:度大于0的结点称为分支结点。 (4)结点的深度:从根节点开始自顶向下逐层累加的; 结点高度:从叶结点...
  • 结点所在的层数:根节点的层数为1;对其余任何结点,若某结点在第k层,则其孩子结点在第k+1层。 树的深度:树中所有节点的最大层数,也称高度。 树的访问:前序遍历,后序遍历,层序遍历 树的存储: 顺序存储: ...
  • 基本概述

    2015-08-27 13:30:21
    一个结点的度是指该结点的子树个,而树的度是树中所有结点的度的最大值,的层规定根结点为...在深度为k的二叉树中,结点总数最多为2k2^k-1,k>=1. 对任何非空的二叉树T,如果叶结点的个数为 n0n_0,而度为2的结点数为
  • 2020-08-25 16:19:57
    树 一个结点的子树个称为该结点的 度 一棵树的度是指该树种结点的最大度数 ...如果深度为k的二叉树有2^(k)-1个结点,则称此二叉树为满二叉树(满二叉树不存在度为1的结点); 若一颗二叉树至多只有最下..

空空如也

空空如也

1 2 3
收藏数 56
精华内容 22
关键字:

高度为k的二叉树的最大结点数为