接上回，簡單的在螢幕上面顯示二叉樹。

方案

顯示效果設計

1、顯示結構采用滿二叉樹的結構來顯示，不管有多少節點，顯示結構隻和深度有關（沒有的節點，顯示空白） 2、顯示大小、間隔，以二叉樹最後一層為标準，不管二叉樹多深，最後一層相鄰兩個節點距離不變，該距離可定制 3、不同節點之間不應當重疊

實作關鍵步驟

1、該二叉樹的顯示和層數有關，層數約大，上層的間距越大，越小，下層的間距越小，不同層數的二叉樹的最終顯示，最後一層的間隔都是一樣的。實作：固定間隔，是以二叉樹的總寬度近視等于：間隔 * 最後一層的節點個數 2、坐标問題。 a、Y坐标位置：節點的深度可以作為印時的Y坐标 b、X坐标位置：由于二叉樹每個節點之間的距離都可以安排為上一層節點的1/2，而左右子節點到該節點的距離又相等。是以可以如下安排： X坐标： 1 1-1/2 1+1/2 1/2-1/4 1/2+1/4 3/2-1/4 3/2+1/4 3、列印。由于列印是按行的是以需要實作按層周遊，借助隊列可以實作按層列印僞代碼：首節點放入隊列 while（隊列不為空）彈出并列印目前節點左右孩子放入隊列

實作

1、相關定義

typedef struct BinNodetag
{
	BinNodetag* P;		//父節點
	BinNodetag* L;		//左孩子節點
	BinNodetag* R;		//右孩子節點
	unsigned int index; //節點索引
	void * data;		//節點資料
}BinNode;

/*****************************************************************
列印二叉樹使用的資料結構，用于儲存二叉樹節點資料和位置資訊，
depth：
	表示深度位置資訊，根節點為1，往下一層為2，按層+1增長
local：
	标示x軸位置資訊，根節點為機關1，
	其左孩子為1-1/2，右孩子為1+1/2。
	每層的loacl為其父節點的local +/- 0.5^depth
	eg:  node->L->local = node->local - (1 << depth)
*****************************************************************/
typedef struct PaintNodetag //
{
	unsigned int depth;		//Y軸資訊 
	float local;			//X軸資訊
	BinNode *node;			//目前節點
}PaintNode;

void PaintTree(BinNode *head); //顯示列印二叉樹

列印時按節點列印，借助列印節點來儲存列印資訊，用于分層列印

2、擷取深度資訊

void InWalk_info(BinNode *head, unsigned int *depth, unsigned int *num, unsigned int *max_depth)
{
	if (head == NULL)
	{
		return;
	}

	(*num)++;
	(*depth)++;

	*max_depth = *max_depth < *depth ? *depth : *max_depth;

	InWalk_info(head->L, depth, num, max_depth);
	InWalk_info(head->R, depth, num, max_depth);
	(*depth)--;
	
	return;
}

void Info(BinNode *head, unsigned int *depth, unsigned int *num)
{
	unsigned int temp_depth = 0;

	*num = 0;
	InWalk_info(head, &temp_depth, num, depth);
	return;
}

3、定義單個節點列印函數

#define PAINTGAP 2   //length for single word for painting in screen
/*************************單個節點列印函數************************************
local:x坐标
key:在該x出列印的數字
finishline：true表示換行
通路該函數類似于寫日志，local隻能遞增，沒有loacl的地方顯示空白，該函數有記憶性，
finishline換行時，内部x坐标清零
*****************************************************************************/
void Paint(unsigned int local, unsigned int key, bool finishline)
{
	static unsigned int index = 0;
	char DotNum[4] = "%xu";
	char DotSpace[4] = "%xs";

	DotNum[1] = PAINTGAP + '0';
	DotSpace[1] = PAINTGAP + '0';

	while (index < local)
	{
		printf_s(DotSpace, " ");
		index++;
	}

	if (finishline != true)
	{
		printf_s(DotNum, key);
		index++;
	}
	else
	{
		printf_s(DotSpace, "\n");

		index = 0;
	}
	
	return;
}

4、主函數

void PaintTree(BinNode *head)
{
	unsigned int depth = 0;
	unsigned int num = 0;
	unsigned int gap;

	PaintNode paint_node;	//save for paint format
	PaintNode *paint_dot;
	BinNode *node;
	
	if (head == NULL)
	{
		return;
	}
	Info(head, &depth, &num);
	_ASSERT(depth < 32);
	gap = (1 << (depth - 1)); //最大寬度（最後一個層的寬度）

	paint_node.depth = 1;
	paint_node.local = 1;
	paint_node.node = head;

	queue<PaintNode> paint_queue;
	paint_queue.push(paint_node);
	while (!paint_queue.empty())
	{
		paint_dot = &paint_queue.front();
		if (paint_dot->depth != paint_node.depth)
		{
			Paint(gap, 0, true);
		}
		
		Paint(paint_dot->local * gap, paint_dot->node->index, false);

		if (paint_dot->node->L != NULL)
		{
			paint_node.depth = paint_dot->depth + 1;
			paint_node.local = paint_dot->local - 1.0 / (1 << paint_dot->depth);
			paint_node.node = paint_dot->node->L;
			paint_queue.push(paint_node);
		}

		if (paint_dot->node->R != NULL)
		{
			paint_node.depth = paint_dot->depth + 1;
			paint_node.local = paint_dot->local + 1.0 / (1 << paint_dot->depth);
			paint_node.node = paint_dot->node->R;
			paint_queue.push(paint_node);
		}
		paint_node.depth = paint_dot->depth;

		paint_queue.pop();

	}

	Paint(gap, 0, true);

}

使用上面設計提到的方法得到每個節點的坐标值，再使用總長度*坐标值将其離散化，就可以得到離散的位置，然後按照節點為機關進行列印即可。其中周遊使用分層周遊的方式。

5、結果展示

a、不同深度的二叉樹

二叉樹基本操作(二) -----顯示方案實作

b、删除二叉樹節點驗證

二叉樹基本操作(二) -----顯示方案實作

6、附錄

測試用例搬運

#include "Factory_BinTree.h"
void test1()
{
	BinNode  *head = NULL;
	BinNode  *node;

	node = Creat(16);
	Insert(&head, node);

	node = Creat(8);
	Insert(&head, node);
	node = Creat(24);
	Insert(&head, node);
	node = Creat(4);
	Insert(&head, node);
	node = Creat(12);
	Insert(&head, node);
	node = Creat(16);
	Insert(&head, node);
	node = Creat(32);
	Insert(&head, node);
	node = Creat(28);
	Insert(&head, node);
	node = Creat(2);
	Insert(&head, node);
	node = Creat(6);
	Insert(&head, node);
	node = Creat(10);
	Insert(&head, node);
	node = Creat(14);
	Insert(&head, node);
	node = Creat(15);
	Insert(&head, node);
	node = Creat(13);
	Insert(&head, node);
	node = Creat(11);
	Insert(&head, node);
	node = Creat(9);
	Insert(&head, node);
	node = Creat(7);
	Insert(&head, node);
	node = Creat(5);
	Insert(&head, node);
	node = Creat(1);
	Insert(&head, node);

	PaintTree(head);
	Destory(head);
	return;
}

void test2()
{
	BinNode  *head = NULL;
	BinNode  *node;
	BinNode  *nodeDelet;
	node = Creat(16);
	Insert(&head, node);

	node = Creat(8);
	Insert(&head, node);
	//delet node
	nodeDelet = node;

	node = Creat(24);
	Insert(&head, node);
	node = Creat(4);
	Insert(&head, node);
	node = Creat(12);
	Insert(&head, node);

	node = Creat(16);
	Insert(&head, node);
	node = Creat(32);
	Insert(&head, node);
	node = Creat(28);
	Insert(&head, node);
	node = Creat(2);
	Insert(&head, node);
	node = Creat(6);
	Insert(&head, node);
	node = Creat(10);
	Insert(&head, node);
	node = Creat(14);
	Insert(&head, node);
	node = Creat(15);
	Insert(&head, node);
	node = Creat(13);
	Insert(&head, node);
	node = Creat(11);
	Insert(&head, node);
	node = Creat(9);
	Insert(&head, node);
	node = Creat(7);
	Insert(&head, node);
	node = Creat(5);
	Insert(&head, node);
	node = Creat(1);
	Insert(&head, node);


	Delete(head, nodeDelet);
	PaintTree(head);
	Destory(head);
}

void test3()
{
	BinNode  *head = NULL;
	BinNode  *node;

	node = Creat(16);
	Insert(&head, node);

	node = Creat(8);
	Insert(&head, node);


	node = Creat(24);
	Insert(&head, node);
	node = Creat(4);
	Insert(&head, node);

	node = Creat(12);
	Insert(&head, node);


	node = Creat(16);
	Insert(&head, node);
	node = Creat(32);
	Insert(&head, node);
	PaintTree(head);
	Destory(head);
	return;
}
void main()
{

	printf("******************************************************\n"
		"這是三層完整結構\n"
		"******************************************************\n");
	test3();
	printf("******************************************************\n"
		"這是五層不完整結構\n"
		"******************************************************\n");
	test1();


	//删除二叉樹節點
	/*
	printf("******************************************************\n"
		"删除節點前\n"
		"******************************************************\n");
	test1();
	printf("******************************************************\n"
		"删除節點8\n"
		"******************************************************\n");
	test2();
	*/
	return;
}

二叉樹基本操作(二) -----顯示方案實作

方案

顯示效果設計

實作關鍵步驟

實作

1、相關定義

2、擷取深度資訊

3、定義單個節點列印函數

4、主函數

5、結果展示

6、附錄

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希