任意一个有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的二叉树,已知它有[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]个叶子节点,试证明非叶子节点中有[tex=3.0x1.357]6wOxI7kRdeTWx9DEyQ5iyA==[/tex]个节点的度为[tex=0.5x1.0]8C7DKsr6nhrfCdsmGxO88g==[/tex],其余的节点的度为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]。

2022-05-30

任意一个有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的二叉树,已知它有[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]个叶子节点,试证明非叶子节点中有[tex=3.0x1.357]6wOxI7kRdeTWx9DEyQ5iyA==[/tex]个节点的度为[tex=0.5x1.0]8C7DKsr6nhrfCdsmGxO88g==[/tex],其余的节点的度为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]。

答案：

证明:设[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]为二叉树中度为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex]的节点数[tex=1.071x1.0]84E9TDHma8A5q+BT5d2u8Q==[/tex]为度为[tex=0.5x1.0]8C7DKsr6nhrfCdsmGxO88g==[/tex]的节点数,则总的节点数为:[tex=5.714x1.143]e31Q4ODrmtncWkxLvzi0sFrYnGx8LN6pal+00ttJtNA=[/tex]再看二叉树中分支数,除根节点外,其余节点都有一个分支进人,设 [tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex] 为分支数,则有：[tex=3.429x1.143]EeK2eT5Lgcfl+H3PgRT/DQ==[/tex]由于这些分支是由度为[tex=0.5x1.0]oYgVDn+QZqcDCRxqEZwM2A==[/tex] 和[tex=0.5x1.0]8C7DKsr6nhrfCdsmGxO88g==[/tex] 的节点发出的,所以又有:[tex=4.571x1.214]Pr+zscZoSP1lofDAAFuGsVCdqvsxkLZerFQCD3VVYFI=[/tex]由以上两式可得：[tex=5.857x1.214]kabp675NZ5IxoQhVPhbbZe2/XI0Kt9+uBT/BaXqXs9U=[/tex]再结合前式得:[tex=9.571x1.214]G2L6wdFMMijFAyKyZFUDi02+gEWBHFWZwCb9DbrCVwCzVUAk4UdThVcg/XCMPFG9[/tex]由此推出: [tex=3.929x1.214]vusAiuQmlOLTR2tIStF5/w==[/tex] 。

举一反三

内容

0
已知一棵高度为[tex=0.571x1.0]CQkpoDeAAI+5FKIfe1wVCA==[/tex]的具有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的二叉树,按顺序方式存储。[tex=1.286x1.286]L2wDOzgYxc8wTRuuJ9JxnQ==[/tex]编写用先序遍历二叉树中节点的递归和非递归算法。[tex=1.286x1.286]1sS1+frJ13DTELUDtuP36w==[/tex]编写将二叉树中最大序号叶子节点的祖先节点全部打印输出的算法。
1
假设二叉树采用二叉链存储结构存储。编写·个算法﹐给出二叉树中﹒个非根节点(由指针[tex=0.571x1.0]QcnBkHbntawstmyl7KNMng==[/tex]所指),求它的兄弟节点(用指针[tex=0.5x1.0]NSsYk+dfiqXGkmCPT5DyRg==[/tex]指向之﹔若没有兄弟节点,则[tex=0.5x1.0]NSsYk+dfiqXGkmCPT5DyRg==[/tex]为空)。
2
在高度为[tex=0.643x1.0]8+M7OwdUGZPUoOQAaQHP2A==[/tex]含[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个节点的二叉排序树上查找--个关键字最多比较次数为。
3
若电力系统有[tex=0.643x0.786]SBMIs+VUk7//BOpfqlQl0w==[/tex]个独立节点，则可以列出( )个节点电压方程。
4
设森林[tex=0.643x1.0]0WA5oCO54gKWR/jKi5M2Zw==[/tex]对应的二叉树为 [tex=0.786x1.0]ri6gmnf1+J9dGqG5/1sV6A==[/tex], 它有[tex=0.929x0.786]D9maNLyVVGrC3QbL9jjRWg==[/tex]个节点, [tex=0.786x1.0]sHo1pKm+gjxjcUAJjHrarQ==[/tex] 的根为 [tex=1.5x1.0]XAcplTBG86CTUCPYjBdnoQ==[/tex] 的右子树节点个数为[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex],森林 [tex=0.643x1.0]0WA5oCO54gKWR/jKi5M2Zw==[/tex] 中第一棵树的节点个数是多少?